Was wäre der effizienteste Weg, n kleinste Zahlen aus einer Sequenz zu nehmen,
%Vor%Ich möchte 2 kleinste aus der Sequenz basierend auf dem ersten Element nehmen,
%Vor%Zur Zeit sortiere ich die ganze Liste und nehme dann die ersten n Einträge, aber das ist wahrscheinlich nicht der effizienteste Weg, es ist eine große Liste und ich muss das oft machen.
Die Freude von Clojure , Kapitel 6.4 beschreibt einen faulen Sortieralgorithmus. Die Schönheit des faulen Sortierens ist, dass es nur so viel Arbeit wie notwendig, um die ersten x-Werte zu finden. Wenn also x & lt; & lt; n Dieser Algorithmus ist O (n). Hier ist eine modifizierte Version dieses Algorithmus.
%Vor%Wie bereits erwähnt, können Sie mit dem Median-of-Median-Algorithmus das k-te kleinste Element in linearer Zeit auswählen und dann in linearer Zeit partitionieren. Dadurch erhalten Sie die k kleinsten Elemente in O (n). Die Elemente werden jedoch unsortiert sein. Wenn Sie also die k kleinsten Elemente sortieren wollen, kostet das ein anderes O (klogk).
Ein paar wichtige Hinweise:
Zunächst einmal, obwohl die Komplexität O (n) ist, sind kleine Konstanten nicht garantiert und Sie könnten minimale Verbesserung finden, besonders wenn Ihr n relativ klein ist. Es gibt zufällige lineare Auswahlalgorithmen, die in besseren tatsächlichen Zeiten laufen (normalerweise ist die erwartete Laufzeit O (n) mit schlimmeren schlimmsten Fällen, aber sie haben kleinere Konstanten als die deterministischen).
Warum können Sie das Array nicht sortierbar verwalten? Das wäre wahrscheinlich viel leistungsfähiger. Sie müssten einfach jedes Element an der richtigen Stelle einfügen, die O (logn) kostet, aber das kleinste gefundene wäre dann O (1) (oder O (k), wenn Sie das Array neu aufbauen müssen).
>Wenn Sie sich gegen die obige Anmerkung entscheiden, dann ist es eine Alternative, das Array nach jeder solchen Prozedur sortiert zu halten, in O (1) am Ende des Arrays einzufügen und dann jedes Mal eine "merge sort" auszuführen Zeit, die Sie brauchen, um die k kleinsten Elemente zu finden. I.e. Sie sortieren nur die neuen und fügen sie dann in linearer Zeit zusammen. Das würde also O (mlogm + n) kosten, wobei m die Anzahl der seit der letzten Sortierung hinzugefügten Elemente ist.
Wenn n klein ist, können Sie eine zweite Liste der Größe n erstellen, die Sie sortiert halten, sodass Sie immer schnell auf die größte in dieser Liste zugreifen können. iteriere durch die große Liste und prüfe, ob jeder kleiner als der größte in der kleinen Liste ist; Wenn ja, füge es in die kleine Liste ein ... die kleine Liste ist voll, höre die älteste auf.
Wenn n kleiner als 3 oder 4 ist, kannst du es einfach brutal erzwingen. Wenn n größer sein kann, sollten Sie eine binäre Suche durchführen, um den Einfügepunkt für jede zu finden. Wenn n sehr groß sein kann, kann ein anderer Mechanismus in Ordnung sein.