Ich habe eine Sammlung von ungefähr hundert sortierten vector<int> s Obwohl die meisten Vektoren eine kleine Anzahl von ganzen Zahlen in ihnen haben, enthalten einige der Vektoren eine große (& gt; 10K) von ihnen (daher die Vektoren don haben Sie nicht unbedingt die gleiche Größe).
Was ich gerne machen würde, würde im Wesentlichen die kleinste bis größte Ganzzahl durchlaufen, die in all diesen sortierten Vektoren enthalten sind.
Eine Möglichkeit wäre, alle diese sortierten Vektoren in einen sortierten Vektor & amp; einfach iterieren. Also,
Frage 1: Was ist der schnellste Weg, sortierte Vektoren in einen sortierten Vektor zu integrieren?
Ich bin mir sicher, dass es auf der anderen Seite schnellere / cleverere Möglichkeiten gibt, dies zu erreichen, ohne dass & amp; das Ganze neu sortieren - vielleicht die kleinste ganze Zahl iterativ aus dieser Sammlung von sortierten Vektoren herausholen; ohne sie zuerst zu verschmelzen .. so:
Frage 2: Was ist der beste Weg, um das kleinste Element aus einem Haufen von sortierten vector<int> zu knacken?
Basierend auf den Antworten unten und den Kommentaren zu der Frage habe ich einen Ansatz implementiert, bei dem ich eine Prioritätswarteschlange von Iteratoren für die sortierten Vektoren erzeuge. Ich bin mir nicht sicher, ob dies leistungsfähig ist, aber es scheint sehr speichereffizient zu sein. Ich halte die Frage noch offen, da ich mir nicht sicher bin, ob wir den schnellsten Weg gefunden haben.
%Vor% Eine Option ist die Verwendung eines std :: priority queue , um einen Heap von Iteratoren zu erhalten, in denen die Iteratoren platzen up the heap abhängig von den Werten, auf die sie zeigen.
Sie könnten auch erwägen, wiederholte Anwendungen von std :: inplace_merge zu verwenden. Dies würde bedeuten, dass alle Daten in einem großen Vektor angehängt werden und die Offsets, an denen jeder einzelne sortierte Block beginnt und endet, gespeichert werden und diese in inplace_merge übergeben werden. Dies wäre wahrscheinlich schneller als die Heap-Lösung, obwohl ich grundsätzlich denke, dass die Komplexität äquivalent ist.
Update: Ich habe den zweiten Algorithmus implementiert, den ich gerade beschrieben habe. Wiederholt einen Mergesort an Ort und Stelle. Dieser Code befindet sich auf ideone .
Dies funktioniert, indem zuerst alle sortierten Listen zu einer langen Liste zusammengefügt werden. Wenn es drei Quellenlisten gibt, bedeutet dies, dass es vier "Offsets" gibt, die vier Punkte in der vollständigen Liste sind, zwischen denen die Elemente sortiert sind. Der Algorithmus wird dann drei von diesen auf einmal abziehen, wobei die zwei entsprechenden benachbarten sortierten Listen zu einer sortierten Liste zusammengeführt werden und sich dann zwei dieser drei Offsets merken, die in den new_offsets verwendet werden.
Dies wird in einer Schleife wiederholt, wobei Paare benachbarter sortierter Bereiche zusammengeführt werden, bis nur noch ein sortierter Bereich übrig bleibt.
Letztendlich denke ich, dass der beste Algorithmus das Zusammenführen der kürzesten Paare benachbarter Bereiche zuerst beinhalten würde.
%Vor%Das erste, was mir in den Sinn kommt, ist eine Heap-Struktur mit Iteratoren für jeden Vektor, geordnet nach dem Wert, auf den sie gerade zeigen. (Jeder Eintrag müsste natürlich auch den End-Iterator enthalten)
Das aktuelle Element befindet sich im Stammverzeichnis des Heapspeichers, und um fortzuschreiten, müssen Sie es einfach auffüllen oder den Schlüssel erhöhen. (Letzteres könnte man tun, indem man knallt, inkrementiert und dann drückt)
Ich glaube, das sollte asymptotische Komplexität haben O(E log M) Dabei ist E die Gesamtzahl der Elemente und M die Anzahl der Vektoren.
Wenn Sie wirklich alles aus den Vektoren herausholen, könnten Sie einen Haufen Zeiger auf Ihre Vektoren machen, Sie könnten sie auch als Haufen behandeln, um die Leistungseinbuße des Löschens von der Vorderseite eines Vektors zu vermeiden. (oder du könntest zuerst alles in deque s kopieren)
Wenn Sie alle Paare zusammenführen, haben Sie die gleiche asymptotische Komplexität, wenn Sie bei der Reihenfolge vorsichtig sind. Wenn Sie alle Vektoren in einem vollständigen, ausgeglichenen Binärbaum anordnen, dann paarweise zusammenführen, wenn Sie den Baum hinaufgehen, wird jedes Element log M mal kopiert, was auch zu einem O(E log M) -Algorithmus führt.
Um die tatsächliche Effizienz zu erhöhen, sollten Sie statt der Baumstruktur die kleinsten zwei Vektoren wiederholt zusammenführen, bis Sie nur noch eine übrig haben. (wieder, Zeiger auf die Vektoren in einem Haufen zu setzen ist der Weg zu gehen, aber diesmal nach Länge geordnet)
(wirklich, Sie möchten nach "Kosten zu kopieren" anstelle von Länge bestellen. Eine zusätzliche Sache für bestimmte Werttypen zu optimieren)
Wenn ich raten müsste, wäre der schnellste Weg, die zweite Idee zu verwenden, aber mit einer N-stufigen Verschmelzung anstelle einer paarweisen Verschmelzung, für ein geeignetes N (was ich denke, wird entweder eine kleine Konstante sein, oder ungefähr die Quadratwurzel der Anzahl von Vektoren), und führe die N-fache Zusammenführung unter Verwendung des obigen ersten Algorithmus durch, um den Inhalt von N Vektoren gleichzeitig aufzuzählen.
Ich habe den hier angegebenen Algorithmus benutzt und ein wenig abstrahiert; Umwandlung in Vorlagen Ich habe diese Version in VS2010 codiert und eine Lambda-Funktion anstelle des Funktors verwendet. Ich weiß nicht, ob das in irgendeiner Weise "besser" ist als die vorherige Version, aber vielleicht wird es jemandem nützlich sein?
%Vor% Der Algorithmus priority_queue_sort::value_vectors sortiert Vektoren, die nur Werte enthalten; während priority_queue_sort::pair_vectors Vektoren sortiert, die Paare von Daten gemäß dem ersten Datenelement enthalten. Hoffe jemand kann das irgendwann nutzen: -)
Tags und Links mergesort c++ vector sorting processing-efficiency