Ich habe eine Schleife mit folgender Struktur:
Meine Schleife soll viele Male aufgerufen werden (es ist die Hauptschleife meines Programms), und ich möchte, dass der zweite Schritt so schnell wie möglich ist.
Die naive Implementierung für den zweiten Schritt wäre memcmp :
Können Sie sich einen schnelleren Weg vorstellen? Ein paar Dinge:
Hier sind ein paar Gedanken, die ich hatte:
memcmp durchführen. xor ) aller meiner Lookup-Arrays berechnen und ein eingebautes PCMPGT verwenden. Wie in Wie können mehr als zwei Zahlen parallel verglichen werden? . Ich weiß, dass SSE4.2 hier verfügbar ist. Glauben Sie, dass die Vektorisierung / sse hier eine gute Idee ist? Wenn ja, was ist Ihrer Meinung nach der beste Ansatz? Ich möchte sagen, dass dies keine frühzeitige Optimierung ist, aber Leistung ist hier entscheidend, ich brauche die äußere Schleife, um so schnell wie möglich zu sein. Danke
EDIT1: Es sieht aus wie Ссылка liefert einige interessante Gedanken dazu. Binäre Suche in einer Liste von long scheint der Weg zu gehen ..
Die optimale Lösung hängt davon ab, wie viele Arrays übereinstimmen, wie groß die Arrays sind und wie oft sie sich ändern. Ich würde versuchen, die Vergleiche überhaupt zu vermeiden.
Unter der Annahme, dass sich die Liste der zu vergleichenden Arrays nicht häufig ändert und Sie viele solcher Arrays haben, würde ich für jedes Array einen Hash erstellen. Wenn Sie dann zum Vergleich kommen, hashen Sie das, was Sie testen. Dann müssen Sie nur die Hashwerte vergleichen. Mit einem Hash wie SHA256 können Sie sich darauf sowohl als positiver als auch als negativer Indikator verlassen (d. H. Die übereinstimmenden Hashes reichen aus, um zu sagen, dass die Arrays übereinstimmen und die nicht übereinstimmenden Hashes ausreichen, um zu sagen, dass die Arrays unterschiedlich sind). Dies würde sehr gut funktionieren, wenn Sie (sagen wir) 1.000.000 Arrays zum Vergleich hätten, gegen die sich kaum jemals etwas ändert, da die Berechnung des Hash schneller als 1.000.000 Array-Vergleiche wäre.
Wenn Ihre Anzahl an Arrays etwas kleiner ist, sollten Sie einen schnelleren nicht-kryptographischen Hash berücksichtigen. Zum Beispiel würde ein "Hash", der einfach die Bytes in einem Array-Modul 256 summierte (dies ist ein schrecklicher Hash, und Sie können viel besser machen), würde die Notwendigkeit eliminieren, 255/256 des Ziel-Array-Raums zu vergleichen. Sie können dann nur diejenigen vergleichen, bei denen der so genannte "Hash" übereinstimmt. Es gibt bekannte Hash-ähnliche Dinge wie CRC-32, die schnell berechnet werden können.
In jedem Fall können Sie dann nach Hash (Modulo X) suchen, um zu bestimmen, welche Arrays tatsächlich verglichen werden sollen.
Sie schlagen vor, k ist klein, N ist moderat (d. h. etwa 1000). Ich rate Geschwindigkeit dreht sich um Speicher-Cache. Kein Zugriff auf 1.000 kleine Arrays wird hier sehr hilfreich sein.
All das ist nutzlos, wenn sich die Arrays mit einer ähnlichen Häufigkeit wie der Vergleich ändern.
Addition (unter der Annahme, dass Sie 64 Bytes oder ähnliches betrachten). Ich würde in eine sehr schnelle nicht-kryptografische Hash-Funktion schauen. Schauen Sie sich zum Beispiel Folgendes an: Ссылка
Es sieht nach 3-4 Befehlen pro 32-Bit-Wort aus, um den Hash zu generieren. Sie könnten dann das Ergebnis auf (sagen wir) 12 Bits für eine Hash-Tabelle mit 4096 Einträgen mit sehr wenigen Kollisionen abschneiden (jeder Bucket wird mit den Zielarrays verknüpft). Das bedeutet, dass Sie etwa 30 Anweisungen zum Berechnen des Hashs, dann eine Anweisung pro Bucket-Eintrag (erwarteter Wert 1) zum Suchen des Listenelements und dann einen manuellen Vergleich pro erwartetem Treffer (das zwischen 0 und 1 liegen würde) betrachten würden. Anstatt also 1000 Arrays zu vergleichen, würden Sie zwischen 0 und 1 Arrays vergleichen und einen Hash generieren. Wenn Sie 999 Arrays in 30-isen Anweisungen nicht vergleichen können (ich vermute nicht!), Ist das natürlich ein Gewinn.
Wir können davon ausgehen, dass meine Sachen in 64Bit oder sogar 32Bit passen. Wenn es war nicht, ich könnte es hacken, damit es könnte. Aber jetzt, was ist der schnellste Weg? zu finden, ob mein Hash in der Liste der vorberechneten Hashes existiert?
Das ist eine Art Meta-Antwort, aber ... wenn Ihre Frage darauf hinausläuft: Wie kann ich effizient herausfinden, ob eine bestimmte 32-Bit-Nummer in einer Liste anderer 32-Bit-Nummern existiert? Das ist ein Problem IP-Router arbeiten ständig, daher lohnt es sich, in die Netzwerkliteratur zu schauen, um zu sehen, ob es etwas gibt, das Sie von ihren Algorithmen anpassen können. z.B. siehe Ссылка
(Obwohl ich vermute, dass sie für das Durchsuchen einer größeren Anzahl von Elementen als Ihr Anwendungsfall optimiert sind.)
können Sie ein XOR anstelle von Memcmp tun?
oder cachulieren Sie den Hash jedes Elements im Array und sortieren Sie ihn nach dem Hash
aber hash wird mehr Zeit brauchen, wenn Sie nicht einen schnelleren hash erstellen können