Am effizientesten Sortieralgorithmus für viele identische Schlüssel?

stimmen
8

Was ist der effizienteste Algorithmus für die in einem Array identische Elemente zusammen gruppiert, mit dem folgenden:

  1. Fast alle Artikel mehrfach dupliziert.
  2. Die Elemente sind nicht notwendigerweise ganze Zahlen oder irgendetwas anderes, das in ähnlicher Weise einfach. Der Bereich der Tasten ist nicht einmal gut definiert, geschweige denn klein. In der Tat können die Schlüssel beliebig structs sein. Dies schließt aus den einfachstenen Formen der Art zählen.
  3. Wir kümmern uns sowohl um asymptotisch und nicht-asymptotischen Eigenschaften und n manchmal klein sein kann. Wenn jedoch n klein ist, ist die Leistung immer noch wichtig, da diese Funktion in einer Schleife auf Millionen von kleinen Datenmengen mehr Millionen Mal aufgerufen werden kann. Dies schließt jede teure Hash-Funktion oder eine komplexe Datenstruktur, die viele Speicherzuordnungen durchführen muss.
  4. Die Daten können so lange in beliebiger Reihenfolge sortiert werden, da alle identischen Elemente zusammen gruppiert sind.

Wenn dies verwirrend ist, hier ist ein Beispiel, vorausgesetzt, eine solche Funktion ist groupIdentical genannt:

uint[] foo = [1,2,3,2,1,5,4,5];
uint[] bar = groupIdentical(foo);
// One possibile correct value for bar:
// bar == [2,2,1,1,3,4,5,5].
// Another possible correct answer:
// bar == [1,1,2,2,5,5,4,3].

Doch als Erinnerung, können wir nicht davon ausgehen, dass die Daten als ganze Zahlen zusammengesetzt sind.

Edit: Danke für die Antworten. Mein Hauptproblem war mit Hashing, dass Hash-Tabellen Speicherzuordnungen führen häufig zu. Was ich am Ende war dabei meine eigene Hash-Tabelle zu schreiben, das eine Region allocator verwendet, die ich um hatte, um dieses Problem zu bekommen. Funktioniert gut.

Veröffentlicht am 09/12/2008 um 22:00
quelle vom benutzer
In anderen Sprachen...                            


9 antworten

stimmen
10

Ich glaube, Sie könnten nur die Objekte, hash, da wirkliche Reihenfolge spielt keine Rolle, nur die Gruppierung. Identische Objekte werden bis gruppiert in dem gleichen Eimer beenden. Dies wird unter der Annahme, dass jede Art Sie in seinen eigenen Hash-Funktion interessiert hat, oder Sie können Ihre eigenen definieren und Überlastung (jede Art als Parameter an eine andere hashCode Funktionsdefinition nehmen).

Um Kollisionen über Datentypen zu vermeiden (so Strings in dem gleichen Eimer am Ende nicht als verdoppelt, für ein Beispiel), dann würden Sie brauchen, um den Datentyp in den Hash zu kodieren. So zum Beispiel, wenn Sie eine 32-Bit-Hash haben, vielleicht die ersten 5 Bits könnten den Datentyp kodieren, so dass Sie 32 verschiedene Typen in der gleichen Hash-Karte haben.

EDIT: Lassen Sie mich nur hinzufügen, dass der Grund, dass ich eine benutzerdefinierte Hashzuordnung was darauf hindeutet, ist, weil ich nicht von einem weiß, dass genug von seiner internen Implementierung macht für Sie die Werte aus jedem Eimer zu bekommen. Es könnte eine solche Implementierung sein, dass ich nicht weiß, von. Es gibt eine Menge Dinge, die ich nicht kenne. :)

Beantwortet am 09/12/2008 um 22:04
quelle vom benutzer

stimmen
4

Das Zauberwort Sie hier suchen ist multiset (oder Beutel ). Es ist nicht wirklich eine Art überhaupt, da Sie nicht über die Reihenfolge ist egal, solange Sie alle Elemente mit gleichen Schlüssel haben zusammen gruppiert. Es gibt mehrere Dosen-Implementierungen zur Verfügung, abhängig von der Sprache , die Sie verwenden, aber in der Regel über die gehasht Version asymptotisch optimal ist, glaube ich: insert()ist konstante Zeit, da Sie einen Hash in berechnen kann O (1) und hängen Sie kollidieren Einsätze eine Liste in O (1) Zeit; Sie können ein Element aus der Bins in abrufen O (1) Zeit, greifen Sie nur die ersten in dem Behälter; und Sie können daher alle von ihnen in sammeln O (n) Zeit, da Sie abrufen nElemente mit O (1) für jedes Element.

Beantwortet am 09/12/2008 um 23:17
quelle vom benutzer

stimmen
3

Eine galoppierende mergesort, wie Python eingebauten in Art (vgl Timsort ), hat eine gute erwarteten Leistung bei großen Auflagen von bereits sortierten Daten (wie in Ihrem Beispiel identische Objekte) - Sie werden O (log überspringen ( N)) Arbeit pro merge. Sie können auch eine mergesort über mehrere CPUs und Festplatten verteilen, wenn Ihr Dataset extrem groß ist (dies ist eine „externe“ Art genannt). Allerdings wird es schlimmsten Fall O (Nlog (N)) sein.

Die einzigen Arten, die schneller sind als Nlog (N) zählen Sorten, die einige gemeinsame Eigenschaft des Schlüssels nutzen. Um eine lineare Zeit sortieren (Hash-Tabelle oder radix / Bucketsort) zu verwenden, müssen Sie die Struktur des Hash eine Art von numerischen Schlüssel zu erzeugen.

Radixsort werden mehrere Durchgänge durch die Tasten machen, so die erwartete Zeit, die länger ist als eine Hash-Tabelle Ansatz; und, da Sie kümmern sich nicht um lexikographische Ordnung, die Hash-Tabelle Lösung klingt besser für Sie, wenn Sie sich leisten können, um die Schlüssel Hash.

Beantwortet am 09/12/2008 um 22:10
quelle vom benutzer

stimmen
1

Ich denke, dass in Eimer Hashing die beste Lösung wäre, unter der Annahme, dass es ein Hash, den Operator bewahrt = Mapping (0.0 möglicherweise nicht auf dasselbe Hash -0,0, aber sie können „gleich“ sein). Vorausgesetzt, dass Sie nur eine gleiche haben, und weniger als Betreiber, könnte man einen rudimentären Schnellsortieralgorithmus der Kommissionierung das erste Elements als Dreh implementieren und setzt die weniger als in einer Gruppe, und größer ist als in einer anderen Gruppe, und dann Wiederholen der Prozess für jede Gruppe.

Beantwortet am 09/12/2008 um 22:16
quelle vom benutzer

stimmen
1

3-Wege - QuickSort funktioniert sehr gut , wenn es große Anzahl von Duplikaten.

Beantwortet am 09/12/2008 um 22:14
quelle vom benutzer

stimmen
0

Einfacher Algorithmus mit Leistung Größenordnung von O (n (n-1) / 2) ist wie folgt:

  1. Es sei angenommen, Eingangsarray benannt als Eingang aufweist Größe wie n.
  2. Vergeben Sie einen Speicher für die Rückkehr Array mit derselben Größe wie Ergebnis benannt
  3. Vergeben Sie einen Speicher für Boolesche Array mit gleicher Größe benannt als Besucht und setzen alle als falsch Hotel Esperance
  4. Es sei angenommen, gibt es eine gleiche Funktion mit dem Namen als wahr Equals zurück, wenn beide Werte gleich sonst falsch sind.
  5. Es sei angenommen, Array-Index geht von 1 bis n
  6. Bitte beachten Sie Pseudo-C-Code unten:
function groupIdentical(Input) 
{
    k=1;
    for i=1 to n 
    {
        Visited[i]=false ;
    }

    for i=1 to n
    {
        if( !Visited(i) )
        {   
            Result[k++]=Input[i];
            for j= (i+1) to n
            {
                if( Equals(i,j) )
                {
                    Result[k++]=Input[j];
                    Visited[j]=true;
                }   
            }
        }
    }
    return Result;
}
Beantwortet am 10/12/2008 um 08:16
quelle vom benutzer

stimmen
0

Vielleicht ein R + B oder AVL-Baum? Dann wieder - es wäre noch letztlich O (NlogN) sein. Es könnte aber auch Heapsort verwenden - wird nicht schlechter und keine zusätzliche Speichernutzung sein ...

Beantwortet am 09/12/2008 um 22:36
quelle vom benutzer

stimmen
0

Ich denke, dass da Sie beliebige Objekte haben, die Sie nicht wollen, um zu viel zu kopieren, müssen Sie nur Verweise oder Zeiger für die Sortierung verwendet werden können, und, falls erforderlich, anschließend die Objekte, um kopieren.

Beantwortet am 09/12/2008 um 22:19
quelle vom benutzer

stimmen
0

Wenn Sie den Bereich der möglichen Werte kennen, und es ist klein, könnten Sie tun: (pseudo-ish-Code)

uint[] bucket = new int[10];
foreach(uint val in foo) {
    ++bucket[val];
}

uint bar_i = 0;
uint[] bar = new int[foo.length];
foreach(int val = 0; val < 10; val++) {
    uint occurrences = bucket[val];
    for(int i=0; i < occurrences; i++) {
        bar[bar_i++] = val;
    }
}
Beantwortet am 09/12/2008 um 22:16
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more