Wie finde ich effizient die n kleinsten Elemente in einer Liste?

Das Finden der n kleinsten Elemente in einem list<float> kann durch Sortieren der Liste und Auswählen der n kleinsten Elemente erfolgen. Aber es kann auch effizienter mit Haufen getan werden. Ich habe mehrere Implementierungen von Heaps für F # gefunden, aber keine Beispiele, wie sie für diesen Zweck verwendet werden können. Meine zwei Stolpersteine waren:Wie finde ich effizient die n kleinsten Elemente in einer Liste?

1) Ich konnte keinen Weg finden, einen Haufen von einer Liste zu schaffen. Alle Implementierungen, die ich gesehen habe, bieten eine Möglichkeit, einen leeren Heap zu erstellen und haben eine insert Methode. Soll ich einen leeren Heap erstellen und Elemente einzeln einfügen? Das sieht langsam aus, was den Zweck zunichte machen würde.

2) Keine Umsetzung ein nLargest oder nSmallest Verfahren wie zum Beispiel des Python-Code:

from heapq import nlargest 
lst = [9,1,6,4,2,8,3,7,5] 
nlargest(3, lst) # Gives [9,8,7]

Gibt es eine einfache Möglichkeit, dieses Problem zu lösen?

Quelle

2017-05-02 Soldalma

Wenn Sie ein Array haben, können Sie ein Array in O (N) Zeit zu häufen , aber der Typ F # 'list' ist eine Datenstruktur mit verknüpften Listen, für die der Heap-Algorithmus O (N^2) Zeit wäre, da das Heap-Verfahren auf O (1) wahlfreiem Zugriff durch den Index zu seinem Array beruht. Ihre zwei Optionen sind also: 1) wandeln Sie Ihre Liste in ein Array (eine O (N) -Operation) um und haufen Sie sie (eine zweite O (N) -Operation), dann erhalten Sie die 3 kleinsten Elemente (3 O (log N) -Operationen) . Oder 2) sortiere einfach die Liste (O (N log N)) und nimm dann die 3 ersten Elemente daraus (3 O (1) -Operationen). Wenn Sie nicht erwarten, dass Ihre Liste riesig ist, würde ich sagen, machen Sie sich keine Sorgen: einfach sortieren. – rmunn

@rmunn Danke. Aber nur für den Fall, wie würde ich das Array häufen und die kleinsten Elemente bekommen? – Soldalma

Siehe https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/DemoHeapify.pdf für eine visuelle Demo und http://www.cs.toronto.edu/~krueger/cscB63h/w07/ Vorträge/Tut02.txt für einige Pseudocode. Kurz gesagt, fangen Sie mit dem Array an, und stellen Sie vom letzten Element bis zum ersten sicher, dass es kleiner ist als seine beiden Heap-Child-Elemente. Wenn nicht, vertauschen Sie es mit dem kleineren Kind und wiederholen Sie diesen Vorgang beim kleineren Kind. Und da die rechte Hälfte des Arrays keine Heap-Kinder hat, können Sie tatsächlich bei 'array.Length/2' beginnen und zu Index 0 gehen.Die Analyse des Algorithmus hat gezeigt, dass dies eine O (N) -Zeit benötigt. – rmunn

wie ein Array in ein binäres heap neu zu ordnen:

in der Mitte des Arrays starten und rückwärts zu bewegen, sichten jedes Element nach unten in der Halde. Angenommen, Sie haben ein Array a mit der Länge n. Im Folgenden wird es tun:

for i = n/2 downto 0 
    siftDown(i);

Und die siftDown Methode:

siftDown(int index) 
{ 
    while (index < n/2) 
    { 
     // find the smallest child 
     int ixChild = (ix * 2) + 1; 
     if (ixChild < n-1 && a[ixChild] > n[ixChild + 1]) 
     { 
      ixChild = ixChild + 1; 
     } 
     // if the item is <= the smallest child, we're done 
     if (a[i] < a[ixChild]) break; 

     // otherwise, swap with the smallest child 
     swap(i, ixChild); 

     // and do it again 
     i = ixChild; 
    } 
}

Eine andere Möglichkeit, die k kleinsten Elemente in einer Liste auszuwählen, ist Quickselect zu verwenden, die im Grunde ist das Quicksort Aufteilungsverfahren. Dies hat den Vorteil, dass sie O (n) ist, was normalerweise schneller ist als die Verwendung eines Heaps. Wenn der Algorithmus abgeschlossen ist, befinden sich die kleinsten Elemente an der Vorderseite des Arrays, aber sie sind nicht sortiert.

Schließlich können Sie einen Pairing heap anstelle eines binären Heap verwenden, wenn Sie die Heap-Auswahlmethode verwenden möchten. Pairing-Heap hat O (1) einfügen und O (log n) entfernen. Außerdem sollte es in F # aus dem Beispiel auf der Wikipedia-Seite ziemlich einfach zu implementieren sein.

Quelle

2017-05-02 12:19:29

Beachten Sie, dass Sie nicht wirklich einen Heap dafür verwenden müssen. Siehe z. B. Jon Skeet's old post zum Implementieren einer schnellen Sortierung, um die sortierte Sequenz zu erhalten, ohne die gesamte Arbeit im Voraus auszuführen. (Leider gibt es einige unabhängige Exposition in der Post, denn es ist nur ein Teil einer langen Reihe LINQ-to-Objekte wieder zu implementieren)

Quelle

2017-05-02 13:05:27 kvb

Wie finde ich effizient die n kleinsten Elemente in einer Liste?

Antwort

Verwandte Themen