Schnellster Weg, um die größten X-Nummern aus einer sehr großen unsortierten Liste zu erhalten?

Question

Ich versuche, die oberste sagen, 100 Punkte aus einer Liste von Punkten, die von meinem Programm generiert werden. Leider ist die Liste riesig (in der Größenordnung von Millionen bis Milliarden), so dass das Sortieren ein zeitintensiver Teil des Programms ist.

Was ist der beste Weg, um die Top 100 Punkte zu sortieren? Die einzigen beiden Methoden, die ich mir vorstellen kann, sind entweder zuerst alle Partituren zu einem riesigen Array zu generieren und dann zu sortieren und die Top 100 zu nehmen. Oder zweitens X Nummer der Partitur zu generieren, sie zu sortieren und die Spitze abzuschneiden 100 Punkte setzen dann fort, mehr Punkte zu erzeugen, sie der gekürzten Liste hinzuzufügen und sie dann wieder zu sortieren.

Wie auch immer ich es tue, es dauert noch mehr Zeit, als ich möchte, irgendwelche Ideen, wie es auf eine noch effizientere Art und Weise zu tun? (Ich habe noch nie zuvor Programmierkurse belegt, vielleicht wissen diejenigen von Ihnen, die einen Doktortitel haben, über effiziente Algorithmen, um das zu tun, zumindest hoffe ich darauf).

Schließlich, was ist der Sortieralgorithmus von der Standardfunktion sort() in C++?

Danke,

-Faken

Edit: Nur für jeden, der neugierig ist ...

ich einige Zeit Studien über die zuvor und nach und hier sind die Ergebnisse:

altes Programm (Preforms nach jeder Außenschleifeniteration Sortieren):

top 100 scores: 147 seconds 
top 10 scores: 147 seconds 
top 1 scores: 146 seconds 
Sorting disabled: 55 seconds 

neues Programm (Tracking von nur Spitzenwert der Implementierung und Verwendung der Standardsortierfunktion):

top 100 scores: 350 seconds <-- hmm...worse than before 
top 10 scores: 103 seconds 
top 1 scores: 69 seconds 
Sorting disabled: 51 seconds 

neue Rewrite (Optimierungen in Daten gespeichert, handgeschriebener Sortier-Algorithmus):

top 100 scores: 71 seconds <-- Very nice! 
top 10 scores: 52 seconds 
top 1 scores: 51 seconds 
Sorting disabled: 50 seconds 

auf einem Kern Fertig 2 , 1,6 GHz ... Ich kann nicht warten, bis mein Kern i7 860 ankommt ...

Es gibt eine Menge anderer, noch aggressiverer Optimierungen für mich (hauptsächlich im Bereich der Reduzierung der Iterationen) run), aber wie es jetzt steht, ist die Geschwindigkeit mehr als g Oh genug, ich könnte mich nicht einmal darum kümmern, diese Algorithmus-Optimierungen zu erarbeiten.

Danke an eveyrone für ihre Eingabe!

Answer 1

1. nehmen Sie die ersten 100 Bewertungen, und sortieren Sie sie in einem Array.
2. die nächste Kerbe, und einschub sortiert sie in die Anordnung (bei dem „kleinen“ Ende ausgehend)
3. den 101st Wert fallen
4. mit dem nächsten Wert weiter, bei 2 bis
getan

Im Laufe der Zeit wird die Liste mehr und mehr dem 100 größten Wert ähneln. Daher finden Sie öfter, dass die Einfügesortierung sofort abgebrochen wird. Der neue Wert ist kleiner als der kleinste Wert der Kandidaten für die obersten 100.

Answer 2

Sie wollen die absolut größten X-Nummern, also ich vermute, Sie wollen keine Art von Heuristik. Wie unsortiert ist die Liste? Wenn es ziemlich zufällig ist, ist deine beste Wette wirklich, nur eine schnelle Sortierung auf der ganzen Liste zu machen und die besten X-Ergebnisse zu holen.

Wenn Sie Ergebnisse während der Listengenerierung filtern können, ist das viel besser. Speichern Sie nur X-Werte und vergleichen Sie sie jedes Mal, wenn Sie einen neuen Wert erhalten, mit diesen X-Werten. Wenn es weniger als alle von ihnen ist, wirf es weg. Wenn es größer als einer von ihnen ist, werfen Sie den neuen kleinsten Wert aus.

Wenn X klein genug ist, können Sie Ihre Liste der X-Werte sogar so sortieren, dass Sie Ihre neue Zahl mit einer sortierten Liste von Werten vergleichen. Sie können dann eine O (1) -Prüfung durchführen, um zu sehen, ob der neue Wert vorhanden ist kleiner als der Rest und schmeißt es raus. Andernfalls kann eine schnelle binäre Suche finden, wohin der neue Wert in der Liste geht, und dann können Sie den ersten Wert des Arrays wegwerfen (unter der Annahme, dass das erste Element das kleinste Element ist).

Answer 3

Platzieren Sie die Daten in einer ausgewogenen Baumstruktur (wahrscheinlich Red-Bla ck Baum), der die Sortierung an Ort und Stelle tut. Insertionen sollten O (lg n) sein. Das Ergreifen der höchsten x-Werte sollte ebenfalls O (lg n) sein.

Sie können den Baum von Zeit zu Zeit beschneiden, wenn Sie feststellen, dass Sie irgendwann Optimierungen benötigen.

Answer 4

Wenn Sie nur den Wert der Top 100 Scores (und keine damit verbundenen Daten) melden müssen, und wenn Sie wissen, dass die Scores alle in einem endlichen Bereich wie [0,100] liegen, dann ist dies ein einfacher Weg es ist mit "zählende Sortierung" ...

Grundsätzlich erstellen Sie ein Array, das alle möglichen Werte darstellt (zB ein Array der Größe 101, wenn die Werte zwischen 0 und 100 liegen können), und initialisieren Sie alle Elemente des Arrays mit ein Wert von 0. Dann iteriere durch die Liste der Punkte und inkrementiere den entsprechenden Eintrag in der Liste der erreichten Punkte. Das heißt, kompilieren Sie die Anzahl der Male, die jedes Ergebnis in dem Bereich erreicht worden ist. Wenn Sie dann vom Ende des Arrays bis zum Anfang des Arrays arbeiten, können Sie den oberen X-Score auswählen. Hier ist ein Pseudo-Code:

 
    let type Score be an integer ranging from 0 to 100, inclusive. 
    let scores be an array of Score objects 
    let scorerange be an array of integers of size 101. 

    for i in [0,100] 
     set scorerange[i] = 0 

    for each score in scores 
     set scorerange[score] = scorerange[score] + 1 

    let top be the number of top scores to report 
    let idx be an integer initialized to the end of scorerange (i.e. 100) 

    while (top > 0) and (idx>=0): 
     if scorerange[idx] > 0: 
       report "There are " scorerange[idx] " scores with value " idx 
       top = top - scorerange[idx] 
     idx = idx - 1; 

Answer 5

Deklarieren Sie ein Array, wo Sie die 100 besten Ergebnisse setzen können. Durchlaufen Sie die riesige Liste und prüfen Sie, ob jedes Element in die Top 100 eingefügt werden kann. Verwenden Sie eine einfache Einfügesortierung, um ein Element zur obersten Liste hinzuzufügen.

So etwas wie diese (C# -Code, aber Sie erhalten die Idee):

Score[] toplist = new Score[100]; 
int size = 0; 
foreach (Score score in hugeList) { 
    int pos = size; 
    while (pos > 0 && toplist[pos - 1] < score) { 
     pos--; 
     if (pos < 99) toplist[pos + 1] = toplist[pos]; 
    } 
    if (size < 100) size++; 
    if (pos < size) toplist[pos] = score; 
} 

ich es auf meinem Computer getestet (Code 2 Duo 2,54 MHz Win 7 x64) und ich kann in 100.000.000 Artikel bearbeiten 369 ms.

Answer 6

Sie können dies in O (n) Zeit, ohne Sortierung, mit einem Haufen:

#!/usr/bin/python 

import heapq 

def top_n(l, n): 
    top_n = [] 

    smallest = None 

    for elem in l: 
     if len(top_n) < n: 
      top_n.append(elem) 
      if len(top_n) == n: 
       heapq.heapify(top_n) 
       smallest = heapq.nsmallest(1, top_n)[0] 
     else: 
      if elem > smallest: 
       heapq.heapreplace(top_n, elem) 
       smallest = heapq.nsmallest(1, top_n)[0] 

    return sorted(top_n) 


def random_ints(n): 
    import random 
    for i in range(0, n): 
     yield random.randint(0, 10000) 

print top_n(random_ints(1000000), 100) 

Zeiten auf meinem Rechner (Core2 Q6600, Linux, Python 2.6, gemessen mit bash time builtin):

• 100000 Elemente: 0,29 Sekunden
• 1000000 Elemente: 2,8 Sekunden
• 10000000 Elemente: 25.
2 Sekunden

Bearbeiten/Zusatz: In C++ können Sie std::priority_queue in der gleichen Weise verwenden, wie Python heapq Modul hier verwendet wird. Sie möchten die std::greater Sortierung anstelle der Standard std::less verwenden, so dass die top() Elementfunktion das kleinste Element anstelle der größten Element zurückgibt. Die C++ - Prioritätswarteschlange hat nicht den Gegenwert heapreplace, der das oberste Element durch ein neues Element ersetzt. Stattdessen möchten Sie pop das oberste (kleinste) Element und dann push den neu gesehenen Wert angeben. Ansonsten übersetzt der Algorithmus ziemlich sauber von Python nach C++.

Answer 7

Sie können wie folgt es in Haskell tun:

largest100 xs = take 100 $ sortBy (flip compare) xs 

Das sieht aus wie es alle Zahlen sortiert in absteigender Reihenfolge (die „Flip vergleichen“ Bit kehrt die Argumente der Standardvergleichsfunktion), und dann kehrt die ersten 100 Einträge aus der Liste. Aber Haskell wird langsam ausgewertet, so dass die sortBy-Funktion gerade genug sortiert, um die ersten 100 Zahlen in der Liste zu finden, und dann stoppt.

Puristen werden feststellen, dass Sie auch die Funktion schreiben konnte als

largest100 = take 100 . sortBy (flip compare) 

Dies ist nur das Gleiche bedeutet, sondern zeigt die Haskell-Stil eine neue Funktion aus den Bausteinen anderer Funktionen anstatt Gabe Komponieren Variablen um den Ort herum.

Answer 8

Ich beantwortete diese Frage als Antwort auf eine Interviewfrage im Jahr 2008. Ich implementierte eine templatized priority queue in C#.

using System; 
using System.Collections.Generic; 
using System.Text; 

namespace CompanyTest 
{ 
    // Based on pre-generics C# implementation at 
    //  http://www.boyet.com/Articles/WritingapriorityqueueinC.html 
    // and wikipedia article 
    //  http://en.wikipedia.org/wiki/Binary_heap 
    class PriorityQueue<T> 
    { 
     struct Pair 
     { 
      T val; 
      int priority; 
      public Pair(T v, int p) 
      { 
       this.val = v; 
       this.priority = p; 
      } 
      public T Val { get { return this.val; } } 
      public int Priority { get { return this.priority; } } 
     } 
     #region Private members 
     private System.Collections.Generic.List<Pair> array = new System.Collections.Generic.List<Pair>(); 
     #endregion 
     #region Constructor 
     public PriorityQueue() 
     { 
     } 
     #endregion 
     #region Public methods 
     public void Enqueue(T val, int priority) 
     { 
      Pair p = new Pair(val, priority); 
      array.Add(p); 
      bubbleUp(array.Count - 1); 
     } 
     public T Dequeue() 
     { 
      if (array.Count <= 0) 
       throw new System.InvalidOperationException("Queue is empty"); 
      else 
      { 
       Pair result = array[0]; 
       array[0] = array[array.Count - 1]; 
       array.RemoveAt(array.Count - 1); 
       if (array.Count > 0) 
        trickleDown(0); 
       return result.Val; 
      } 
     } 
     #endregion 
     #region Private methods 
     private static int ParentOf(int index) 
     { 
      return (index - 1)/2; 
     } 
     private static int LeftChildOf(int index) 
     { 
      return (index * 2) + 1; 
     } 
     private static bool ParentIsLowerPriority(Pair parent, Pair item) 
     { 
      return (parent.Priority < item.Priority); 
     } 
     // Move high priority items from bottom up the heap 
     private void bubbleUp(int index) 
     { 
      Pair item = array[index]; 
      int parent = ParentOf(index); 
      while ((index > 0) && ParentIsLowerPriority(array[parent], item)) 
      { 
       // Parent is lower priority -- move it down 
       array[index] = array[parent]; 
       index = parent; 
       parent = ParentOf(index); 
      } 
      // Write the item once in its correct place 
      array[index] = item; 
     } 
     // Push low priority items from the top of the down 
     private void trickleDown(int index) 
     { 
      Pair item = array[index]; 
      int child = LeftChildOf(index); 
      while (child < array.Count) 
      { 
       bool rightChildExists = ((child + 1) < array.Count); 
       if (rightChildExists) 
       { 
        bool rightChildIsHigherPriority = (array[child].Priority < array[child + 1].Priority); 
        if (rightChildIsHigherPriority) 
         child++; 
       } 
       // array[child] points at higher priority sibling -- move it up 
       array[index] = array[child]; 
       index = child; 
       child = LeftChildOf(index); 
      } 
      // Put the former root in its correct place 
      array[index] = item; 
      bubbleUp(index); 
     } 
     #endregion 
    } 
} 

Answer 9

Hier ist die 'natürliche' C++ Art und Weise, dies zu tun:

std::vector<Score> v; 
// fill in v 
std::partial_sort(v.begin(), v.begin() + 100, v.end(), std::greater<Score>()); 
std::sort(v.begin(), v.begin() + 100); 

Dies ist linear in der Anzahl der Partituren.

Der von std :: sort verwendete Algorithmus ist nicht durch den Standard spezifiziert, aber libstdC++ (von g ++ verwendet) verwendet einen "adaptiven Introsort", der im Wesentlichen ein Median-von-3-Quicksort bis zu einem bestimmten Level ist, gefolgt von einer Einfügesortierung.

Answer 10

Da Geschwindigkeit ist hier von wesentlicher Bedeutung, und 40.000 möglichen Highscore-Werte ist vollständig von jedem der heutigen Computer gewartet werden kann, würde ich auf Bucket Sortierung für Einfachheit zurückgreifen. Meine Vermutung ist, dass einen der bisher vorgeschlagenen Algorithmen übertreffen würde. Der Nachteil ist, dass Sie eine obere Grenze für die Highscore-Werte festlegen müssen. So

, nehmen wir an, Ihre max Highscore-Wert ist 40.000:

Machen Sie ein Array von 40.000 Einträgen. Wiederhole deine Highscore-Werte. Jedes Mal, wenn du auf Highscore x stößt, erhöhe dein Array [x] um eins. Danach müssen Sie nur die obersten Einträge in Ihrem Array zählen, bis Sie 100 gezählte Highscores erreicht haben.

Answer 11

Median of medians algorithm.