Vergleiche zwei etwas große Objekte auf Gleichheit

8

Ich muss zwei größere Objekte auf Gleichheit vergleichen.

Eigenschaften der Objekte:

  1. Enthalten alle ihre Mitglieder nach Wert (also keine Hinweise zu folgen).
  2. Sie enthalten auch einige stl::array .
  3. Sie enthalten einige andere Objekte, für die 1 und 2 gelten.
  4. Die Größe ist bis zu mehreren kB.
  5. Einige der members unterscheiden sich wahrscheinlicher als andere und führen daher zu einem schnelleren Abbruch der Vergleichsoperation, wenn sie zuerst verglichen werden.
  6. Die Objekte ändern sich nicht. Grundsätzlich ist der Algorithmus nur um zu zählen, wie viele Objekte gleich sind. Jedes Objekt wird nur einmal mit mehreren "Master" -Objekten verglichen.

Wie vergleichen Sie diese Objekte am besten? Ich sehe drei Möglichkeiten:

  1. Verwenden Sie einfach plain, nicht überladen operator== .
  2. Überladen Sie == und führen Sie einen Mitglieder-für-Mitglieder-Vergleich durch, beginnend mit Mitgliedern, die sich wahrscheinlich unterscheiden.
  3. Überladen Sie == und zeigen Sie das Objekt als einfaches Bytefeld an und vergleichen Sie Wort für Wort.

Einige Gedanken:
Option 1 scheint gut zu sein, weil dies den geringsten Arbeitsaufwand (und Möglichkeiten zur Einführung von Fehlern) bedeutet.
Option 2 scheint gut, weil ich die Heuristik ausnutzen kann, über welche Elemente sich am wahrscheinlichsten unterscheiden. Aber vielleicht ist es immer noch langsamer, weil das integrierte == der Option 1 lächerlich schnell ist.
Option 3 scheint am besten "low-level" optimiert zu sein, aber das ist es, was der Compiler wahrscheinlich auch für Option 1 tut.

Also sind die Fragen :

  • Gibt es einen bekannten besten Weg, um die Aufgabe zu lösen?
  • Ist eine der Optionen ein absolutes No-Go?
  • Muss ich etwas anderes in Erwägung ziehen?
Michael 28.04.2015, 10:45
quelle

2 Antworten

2

Eine gute Frage.

Wenn Sie eine Heuristik darüber haben, welche Mitglieder sich wahrscheinlich unterscheiden, verwenden Sie sie. Das Überladen von operator == und das Überprüfen verdächtiger Mitglieder scheint also eine gute Idee zu sein.

Über byteweisen Vergleich (aka memcmp und Freunde) - kann aufgrund der Strukturelementausrichtung problematisch sein. I.e. Der Compiler fügt manchmal "leere Leerzeichen" in Ihr Strukturlayout ein, so dass jedes Mitglied eine Ausrichtung benötigt. Diese sind nicht initialisiert und enthalten normalerweise Müll.

Dies kann durch explizite Nullinitialisierung Ihres gesamten Objekts gelöst werden. Aber ich sehe keinen Vorteil von memcmp gegen automatische operator == , was ein Mitgliedervergleich ist. Es kann wahrscheinlich eine gewisse Code-Größe speichern (ein einzelner Aufruf von memcpy gegenüber expliziten Lesevorgängen und Vergleichen), aus der Performance-Perspektive scheint dies jedoch ziemlich ähnlich zu sein.

    
valdo 28.04.2015, 11:14
quelle
4

Standard == ist schnell für kleine Objekte, aber wenn Sie große Datenelemente zum Vergleichen haben, versuchen Sie, einige Optimierungen zu finden, die über die gespeicherten Daten und die Art ihrer Aktualisierung nachdenken und einen überladenen == Vergleichsoperator "intelligenter" definieren "als der Standard.

Wie bereits erwähnt, ist die Option 3 falsch, da die Felder im Allgemeinen gepolstert werden, um die Datenausrichtung zu berücksichtigen. Aus Gründen der Optimierung werden die hinzugefügten Bytes nicht auf 0 initialisiert (vielleicht in der DEBUG-Version) ).

Ich kann Ihnen vorschlagen, die Option zu untersuchen, den Scheck in zwei Phasen aufzuteilen:

  • erste Stufe, erstellen Sie eine Art von kleinen & amp; schnelles Mitglied, das den Status der Instanz "komprimiert" (denke wie ein Hash); Dieses Feld könnte jedes Mal aktualisiert werden, wenn sich ein großes Feld ändert, zum Beispiel die Elemente des stl-arrays. Dann überprüfen Sie häufig geänderte Felder und diesen "komprimieren" Status zuerst, um einen konservativen Vergleich zu machen (zum Beispiel die Summe aller int im Array, oder vielleicht der xor)
  • zweite Stufe, verwenden Sie einen tiefen Test für jedes Mitglied. Dies ist die langsamste, aber vollständigste Prüfung, wird aber wahrscheinlich nur manchmal aktiviert.
Mouze 28.04.2015 10:59
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Unterschied zwischen isObservable und isSubscribable