Was der effizienteste Algorithmus zum Gruppieren identischer Elemente in einem Array ist, ist Folgendes zu beachten:
Wenn das verwirrend ist, ist hier ein Beispiel, vorausgesetzt, eine solche Funktion heißt groupIdentical:
%Vor%Als Erinnerung können wir jedoch nicht annehmen, dass die Daten als Ganzzahlen zusammengesetzt sind.
Bearbeiten: Danke für die Antworten. Mein Hauptproblem beim Hashing war, dass Hash-Tabellen häufig Speicherzuweisungen durchführen. Am Ende habe ich meine eigene Hash-Tabelle geschrieben, die einen Regionallocator verwendet, den ich hatte, um dieses Problem zu umgehen. Funktioniert gut.
Ich denke, du könntest die Objekte einfach hashen, da die richtige Reihenfolge keine Rolle spielt, nur die Gruppierung. Identische Objekte werden im selben Bucket gruppiert. Dies setzt voraus, dass jeder Typ, an dem Sie interessiert sind, eine eigene Hash-Funktion hat, oder Sie können Ihre eigenen definieren und überladen (wobei jeder Typ als Parameter für eine andere hashCode-Funktionsdefinition verwendet wird).
Um Kollisionen zwischen Datentypen zu vermeiden (damit Strings nicht in einem einzigen Bucket enden, wie in einem Beispiel), müssten Sie den Datentyp in den Hash codieren. Wenn Sie zum Beispiel einen 32-Bit-Hash haben, könnten die ersten 5 Bits den Datentyp möglicherweise verschlüsseln, so dass Sie 32 verschiedene Typen in derselben Hash-Map haben können.
BEARBEITEN: Lassen Sie mich nur hinzufügen, dass der Grund, dass ich eine benutzerdefinierte Hash-Map vorschlage, ist, weil ich keine von denen kenne, die genug ihrer internen Implementierung für Sie freigibt, um die Werte aus jedem Bucket zu erhalten. Es könnte eine solche Implementierung geben, von der ich nichts weiß. Es gibt viele Dinge, die ich nicht kenne. :)
Das Zauberwort, nach dem Sie suchen, ist multiset (oder Tasche ). Es ist nicht wirklich eine Art überhaupt, da Sie sich nicht um die Reihenfolge kümmern, solange Sie alle Elemente mit gleichen Schlüsseln gruppiert haben. Abhängig von der Sprache, die Sie verwenden, gibt es mehrere vordefinierte Implementierungen, aber im Allgemeinen ist die obige Hashversion asymptotisch optimal. Ich glaube: insert() ist eine konstante Zeit, da Sie einen Hash in O (1 ) und fügen Sie kollidierende Einfügungen an eine Liste in O (1) Zeit an; Sie können ein Element aus den Bins in O (1) Zeit abrufen, Sie greifen einfach den ersten in den Bin; und Sie können daher alle in O (n) Zeit sammeln, da Sie n Elemente mit O (1) für jedes Element abrufen.
Ein galoppierender Mergesort, wie zB die integrierte Python-Sortierung (vgl. timsort ) , hat eine gute erwartete Leistung, wenn große Läufe von bereits sortierten Daten (wie in Ihrem Beispiel, identische Objekte) - Sie überspringen O (log (N)) Arbeit pro Zusammenführung. Sie können auch einen Mergesort über mehrere CPUs und Festplatten verteilen, wenn Ihre Datenmenge extrem groß ist (dies wird als "externe" Sortierung bezeichnet). Es ist jedoch der schlechteste Fall O (Nlog (N)).
Die einzigen Arten, die schneller sind als Nlog (N), zählen Sortierungen, die eine gemeinsame Eigenschaft der Schlüssel ausnutzen. Um eine lineare Zeitsortierung (Hash-Tabelle oder Radix / Bucket-Sortierung) zu verwenden, müssen Sie die Struktur mit einer Hash-Funktion versehen, um eine Art numerischen Schlüssel zu generieren.
Radix sort führt mehrere Durchläufe durch die Schlüssel durch, so dass die erwartete Zeit länger ist als eine Hashtabellen-Methode; und da Sie sich nicht um die lexikographische Ordnung kümmern, klingt die Hash-Tabellen-Lösung für Sie besser, wenn Sie es sich leisten können, die Schlüssel zu hashen.
3-Wege-QuickSort funktioniert sehr gut, wenn eine große Anzahl von Duplikaten vorhanden ist.
Ich denke, das Hashing in Buckets wäre die beste Lösung, wenn man annimmt, dass es einen Hash gibt, der operator = mapping (0.0 könnte nicht auf dasselbe -0.0 hacken, aber sie könnten "gleich" sein). Unter der Annahme, dass Sie nur einen Gleich- und Kleiner-als-Operator haben, könnten Sie einen rudimentären Schnellsortieralgorithmus implementieren, bei dem das erste Element als Drehpunkt ausgewählt wird und weniger als in einer Gruppe und größer als in einer anderen Gruppe gesetzt und dann wiederholt wird der Prozess für jede Gruppe.
Ein einfacher Algorithmus mit der Ausführungsreihenfolge von O (n (n-1) / 2) ist wie folgt:
Tags und Links algorithm optimization performance sorting hash