Gibt es eine Möglichkeit, zwei Speicherblöcke zu vergleichen und zu wissen, an welchem Punkt sie sich unterscheiden (memcmp() erfüllt diese Anforderung nicht)? Ich möchte keine kostspieligen Schleifen machen. Danke im Voraus.Speichervergleich (mit Differenzposition)
Grüße, Neo_b
Im Vergleich zu was auch immer Sie tun, eine Schleife ist billig: (! Oder Festplatte) die großen Kosten, die Daten aus dem RAM in erster Linie werden das Abrufen.
Sie können Schleifen mit Speichervergleich von mehr als ein paar Bytes nicht vermeiden. Schreiben Sie den Algorithmus so, wie Sie es sich vorstellen können. Es ist einfach genug und Sie werden überrascht sein, wie gut der Compiler diesen Code optimiert.
std::mismatch wird das für Sie in Verbindung tun std::distance.
Sie haben angenommen, dass er den STL-Iterator verwendet, und außerdem muss er wissen, an welcher Stelle sich der Speicher unterscheidet. – Doomsday
Ich hatte Std :: Equal zuerst, was offensichtlich falsch war, also habe ich es korrigiert. Algorithmen funktionieren sehr gut mit Zeigern sowie mit (vollen) Iteratoren. –
@Doomsday: 'char *' * ist * ein Iterator-Typ und 'Mismatch' gibt zwei Iteratoren zurück, die auf den Unterschied zeigen. +1 – Potatoswatter
memcmp macht einfach eine "teure Schleife", Byte für Byte. Zum Beispiel, hier ist die Implementierung von Microsoft:
EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0) {
v = *(p1++) - *(p2++);
}
return v;
}
Die meisten anderen Implementierungen tun genau die gleiche Sache. Für Ihre Bedürfnisse könnten Sie so etwas tun:
long my_memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
long pos = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0)
{
v = *(p1++) - *(p2++);
if (v == 0)
pos++;
else
break;
}
return pos;
}
Byte-pro-Byte ist in der Tat teuer. 32-Bit-Int-Operationen können sogar schneller als ihre 8-Bit-Gegenstücke sein. – mvds
Ich habe meine eigene Implementierung erstellt (ich dachte, ich könnte sie irgendwann durch etwas anderes ersetzen). Meine Bedürfnisse erfordern bis zu 10 000 000 Iterationen. Das System friert manchmal ein, aber es funktioniert. Außerdem wird angegeben, wie viele Bytes nach einem ersten Nicht-Übereinstimmungsvorkommen nicht übereinstimmen. –
@Neo_b: 10 Millionen Iterationen sind nicht so viel - die meisten Systeme werden das in einer viertel Sekunde oder weniger tun. Ich würde Ihr Eingabepufferschema betrachten oder darüber nachdenken, wie Sie dieses Problem angehen. Wenn Sie zum Beispiel nach Strings suchen, wird der Boyer Moore-Algorithmus wahrscheinlich besser als alles andere hier sein. –
Sie werden immer eine Schleife benötigen. Aber Sie könnten Benchmarks durchführen, wenn das Schleifen um 4 Byte (in Int * umgewandelt) oder um 8 Byte (uint64_t oder long long int) schneller ist als die naive Lösung pro Byte.
Noch besser, abhängig von der Länge (sagen wir> 1kb) könnten Sie die Schleife ausrollen, was bedeutet, dass Sie z. pro 8 int/uint64_t und bei einer Nichtübereinstimmung das erste abweichende Byte lokalisieren.
uint64_t *bigsteps1 = (uint64_t*)m1;
uint64_t *bigsteps2 = (uint64_t*)m2;
int steps = min(m1_len,m2_len)/sizeof(uint64_t);
int i;
for (i=0; i<steps; i+=8)
{
if (bigsteps1[i] != bigsteps2[i]
|| bigsteps1[i+1] != bigsteps2[i+1]
/// ....
|| bigsteps1[i+7] != bigsteps2[i+7]) break;
}
// i<steps tells if we found a difference
// end game is trivial, left as an excercise to the reader.
Die Schleife entrollen kann auch nach hinten losgehen, denn Sie haben alle diese + N Dinge drin und die i + = 8 als auch. Benchmark um sicher zu sein.
ps überprüfen auch Speicherausrichtung: dies, wenn schnellste sein wird m1&0xff == m2&0xff == 0
Danke für den Rat, ich werde es sicherlich implementieren, obwohl ich nicht ganz sicher bin, was m1 & 0xff == m2 & 0xff == 0 tun soll, von dem, was ich weiß m1 & 0xff == m1, ist das nicht korrekt? –
Dies wird in einigen Fällen schneller sein, aber es könnte zu einigen Problemen kommen. Zuallererst hängt es davon ab, dass Ihre Plattform für 64-Bit-Ganzzahlen die gleiche Ausrichtung hat wie für Zeichen, was oft nicht der Fall ist. (Niemand sagt, dass die Basis des Zeichenarrays auf einer 8-Byte-Grenze liegen muss.) Zweitens wird ein eingebauter intrinsischer oder Assembler wahrscheinlich schneller sein. Auf x86 macht das Problem der Speicherausrichtung die Dinge nur langsamer, und auf anderen Architekturen wird der Prozessor einen Interrupt auslösen. –
@Neo_b: 'm1 & 0xff == 0' ist ein Test, wenn die Adresse' m1' mit '00' endet. @Billy: Natürlich musst du bei diesen Optimierungen ein wenig mit den Grenzen herumspielen, also bis zum ersten ausgerichteten Block, den du langsam testest, dann teste so viele Blöcke wie möglich schnell und teste den Rest langsam. (Wie gesagt, diese Dinge funktionieren nur dann positiv, wenn die Blöcke groß genug sind) Ein eingebauter intrinsischer oder Assembler wird wahrscheinlich schneller sein * wenn er existiert * was ich denke, ist nicht der Fall für das vorliegende Problem. – mvds
Wenn es eine bessere Art und Weise zu vergleichen, zwei Speicherblöcke, würde memcmp, das zu tun neu implementiert werden.
Nachdem das oft gesagt wird, hat memcmp eine portable Standardimplementierung in der Standard-C-Bibliothek, aber es wird oft vom Compiler selbst als eingebaute Funktion implementiert. Diese eingebaute Funktion sollte in hohem Maße für die Zielarchitektur optimiert sein. Nehmen Sie die Bibliotheksimplementierung mit einer Prise Salz.
siehe auch http://stackoverflow.com/questions/855895/intrinsic-memcmp über per-cpu optimierte memcmp-Implementierungen. Wenn Sie die CPU kennen, können Sie eine der gcc __builtin_memcmp() Funktionen auf Ihre Bedürfnisse abstimmen. – mvds
Beachten Sie, dass alles, was Sie hier haben, als Schleife * irgendwo * implementiert wird - es gibt keinen magischen Weg, um das zu tun, was Sie hier ohne einen wollen. –