Nehmen wir an, ich habe die folgenden zwei Sequenzen:
%Vor%Der erste ist der Index, nach dem der zweite sortiert werden soll. Meine derzeitige Lösung besteht darin, den Index zu durchlaufen und eine neue Sequenz mit den gefundenen Elementen aus der unsortierten Sequenz zu konstruieren.
%Vor%Aber diese Lösung scheint mir sehr ineffizient und fehleranfällig zu sein. Bei jeder Iteration wird die gesamte unsortierte Sequenz durchsucht. Und wenn der Index und die unsortierte Liste nicht synchron sind, wird entweder ein Fehler ausgelöst oder ein Element wird weggelassen. In beiden Fällen sollten die nicht synchronisierten Elemente an die geordnete Sequenz angehängt werden.
Gibt es eine effizientere und solidere Lösung für dieses Problem? Oder gibt es einen Sortieralgorithmus, der in dieses Paradigma passt?
Hinweis : Dies ist ein konstruiertes Beispiel. In Wirklichkeit möchte ich eine Liste von Mongodb-Dokumenten nach einer geordneten Liste von Dokument-IDs sortieren.
Update 1
Ich habe die Antwort von Marius Danila ausgewählt, weil es die schnellste und skalierbarste Lösung für mein Problem ist. Es kommt nicht mit einer nicht synchronisierten Artikellösung, aber dies könnte leicht implementiert werden.
Also hier ist die aktualisierte Lösung:
%Vor%Update 2
Der von Bask.cc vorgeschlagene Ansatz scheint die richtige Antwort zu sein. Es berücksichtigt auch nicht das Problem nicht synchron, aber dies kann auch einfach implementiert werden.
%Vor%Warum möchten Sie die Sammlung sortieren, wenn Sie die Indexsammlung bereits sortiert haben? Sie können einfach Karte
verwendenBetreffend & gt; In Wirklichkeit würde ich gerne eine Liste von Mongodb-Dokumenten nach einer geordneten Liste von Dokument-IDs sortieren.
%Vor%Dies entspricht möglicherweise nicht genau Ihrem Anwendungsfall, aber Googler finden das möglicherweise nützlich:
%Vor%Ich kenne die Sprache, die Sie verwenden, nicht. Aber unabhängig von der Sprache hätte ich so das Problem gelöst.
Erstellen Sie aus der ersten Liste (hier "index") eine Hash-Tabelle, die den Schlüssel als Dokument-ID und den Wert als Position des Dokuments in der sortierten Reihenfolge verwendet.
Wenn ich nun die Liste der Dokumente durchblättere, würde ich die Hash-Tabelle mit der Dokument-ID suchen und dann die Position in der sortierten Reihenfolge erhalten. Dann würde ich diese erhaltene Reihenfolge verwenden, um in einem vorher zugewiesenen Speicher zu sortieren.
Hinweis: Wenn die Anzahl der Dokumente klein ist, können Sie anstelle einer Hashtabelle eine vorab zugeordnete Tabelle verwenden und sie direkt mit der Dokument-ID indizieren.
Flat Das Mappen des Index über die unsortierte Liste scheint eine sicherere Version zu sein (wenn der Index nicht gefunden wird, wird er einfach gelöscht, da find ein None zurückgibt):
Es muss immer noch die unsortierte Liste durchlaufen (schlimmstenfalls ist dies O (n ^ 2)). Bei Ihrem Beispiel bin ich mir nicht sicher, ob es eine effizientere Lösung gibt.
In diesem Fall können Sie zip-sort-unzip verwenden:
(unsorted zip index).sortWith(_._2 < _._2).unzip._1
Btw, wenn du kannst, wäre eine bessere Lösung, die Liste auf der db-Seite zu sortieren, indem du $ orderBy .
Ok.
Fangen wir von vorne an.
Neben der Tatsache, dass Sie die unsorted -Liste jedes Mal erneut scannen, erstellt das Seq -Objekt standardmäßig eine List -Auflistung. In foldLeft hängt also jedes Mal ein Element am Ende der Liste an, und dies ist eine Operation O(N^2) .
Eine Verbesserung wäre
%Vor% Aber das ist immer noch ein O(N^2) -Algorithmus. Wir können es besser machen.
Die folgende Sortierfunktion sollte funktionieren:
%Vor% Die Funktion sortiert eine Liste von Elementen unsorted nach einer Reihe von Indizes index , wobei die Funktion key verwendet wird, um die ID aus den Objekten zu extrahieren, die Sie sortieren möchten.
Zeile 1 erstellt einen umgekehrten Index - jede Objekt-ID wird auf ihre endgültige Position abgebildet.
Zeile 2 weist das Array zu, das die sortierte Sequenz enthält. Wir verwenden ein Array, da wir eine konstante zufällige Positionssatzleistung benötigen.
Die Schleife, die in Zeile 3 beginnt, durchläuft die Sequenz der unsortierten Elemente und platziert jedes Element in seiner beabsichtigten Position mit dem positionMapping reverse index
Zeile 6 gibt das implizit konvertierte Array mit dem Seq wrapper in ein WrappedArray zurück.
Da unser reverser Index ein unveränderbarer HashMap ist, sollte die Suche für reguläre Fälle konstant sein. Die Erstellung des tatsächlichen Rückwärtsindexes dauert O(N_Index) time wobei N_Index die Größe der Indexsequenz ist. Das Durchlaufen der unsortierten Sequenz dauert O(N_Unsorted) time wobei N_Unsorted die Größe der unsortierten Sequenz ist.
Die Komplexität ist also O(max(N_Index, N_Unsorted)) , was meiner Meinung nach das Beste ist, was Sie unter diesen Umständen tun können.
Für Ihr spezielles Beispiel würden Sie die Funktion wie folgt aufrufen:
%Vor%Für den wirklichen Fall wäre es wahrscheinlich so:
%Vor% Das Beste, was ich tun kann, ist ein Map aus den unsortierten Daten zu erstellen, und Kartensuchen (im Grunde die von einem früheren Poster vorgeschlagene Hashtabelle) zu verwenden. Der Code sieht folgendermaßen aus:
Oder, wenn es eine Möglichkeit gibt, dass Hash nicht möglich ist:
%Vor% Es ist O(n) in time *, aber Sie tauschen Zeit für Speicherplatz aus, da O(n) Leerzeichen verwendet wird.
Für eine etwas anspruchsvollere Version, die fehlende Werte behandelt, versuchen Sie:
%Vor%Wenn es sich in erster Linie um eine MongoDB-Datenbank handelt, können Sie Dokumente möglicherweise besser direkt aus der Datenbank nach Index abrufen, etwa so:
%Vor% * technisch ist es O(n log n) , da Scalas standardmäßige unveränderliche Karte O(log n) ist, aber Sie könnten immer eine veränderbare Karte verwenden, die O(1)