algorithm - zahlen - wie viele nullen hat eine quadrilliarde




Finden Sie die hundert größten Zahlen in einer Datei von einer Milliarde (10)

  1. Unter der Annahme, dass 1 Rechnung + 100.000 Zahlen in den Speicher passen, ist der beste Sortieralgorithmus Heap-Sortierung. Bilden Sie einen Haufen und erhalten Sie die ersten 100 Zahlen. Komplexität o (nlogn + 100 (zum Abrufen der ersten 100 Zahlen))

    Verbesserung der Lösung

    Teilen Sie die Implementierung auf zwei Heap (so dass die Einfügung weniger komplex ist) und beim Holen der ersten 100 Elemente imperial Merge-Algorithmus.

Ich ging heute zu einem Interview und wurde diese Frage gestellt:

Angenommen, Sie haben eine Milliarde Ganzzahlen, die in einer Festplattendatei unsortiert sind. Wie würden Sie die größten hundert Zahlen ermitteln?

Ich bin mir nicht einmal sicher, wo ich mit dieser Frage anfangen würde. Was ist der effizienteste Prozess, um das richtige Ergebnis zu erhalten? Muss ich die Datei hundert Mal durchgehen, um die höchste Nummer zu finden, die noch nicht in meiner Liste enthalten ist, oder gibt es einen besseren Weg?


Behalte ein festes Array von 100 ganzen Zahlen. Initialisiere sie zu einem Int.MinValue. Wenn Sie von 1 Milliarde Ganzzahlen lesen, vergleichen Sie sie mit den Zahlen in der ersten Zelle des Arrays (Index 0). Wenn größer, dann gehe zum nächsten. Wenn Sie größer sind, bewegen Sie sich nach oben, bis Sie das Ende oder einen kleineren Wert erreichen. Speichern Sie dann den Wert im Index und verschieben Sie alle Werte in den vorherigen Zellen um eine Zelle nach unten ... tun Sie dies und Sie werden 100 max ganze Zahlen finden.


Erstelle ein Array von 100 Zahlen, die alle -2 ^ 31 sind.

Überprüfen Sie, ob die erste von der Festplatte gelesene Nummer größer als die erste in der Liste ist. Wenn dies der Fall ist, kopieren Sie das Array nach unten und aktualisieren Sie es auf die neue Nummer. Wenn nicht, überprüfen Sie die nächste in der 100 und so weiter.

Wenn Sie alle 1 Milliarde Ziffern gelesen haben, sollten Sie die höchsten 100 im Array haben.

Job erledigt.


Es gibt viele clevere Ansätze (wie die Priority-Queue-Lösungen), aber eines der einfachsten Dinge, die Sie tun können, kann auch schnell und effizient sein.

Wenn Sie das oberste k von n , beachten Sie:

allocate an array of k ints
while more input
  perform insertion sort of next value into the array

Das klingt vielleicht absurd simpel. Man könnte erwarten, dass dies O(n^2) , aber es ist nur O(k*n) , und wenn k viel kleiner ist als n (wie in der Problemaussage postuliert), nähert es sich O(n) .

Sie könnten argumentieren, dass der konstante Faktor zu hoch ist, da es im Durchschnitt viele k/2 Vergleiche und Bewegungen pro Eingabe gibt. Die meisten Werte werden jedoch beim ersten Vergleich trivialerweise mit dem k ten bisher größten Wert abgelehnt. Wenn Sie eine Milliarde Eingänge haben, ist wahrscheinlich nur ein kleiner Bruchteil größer als der 100ste.

(Sie könnten eine Worst-Case-Eingabe verwenden, bei der jeder Wert größer ist als sein Vorgänger, was k Vergleiche und Verschiebungen für jede Eingabe erfordert. Aber das ist im Wesentlichen eine sortierte Eingabe und die Problemaussage besagt, dass die Eingabe unsortiert ist.)

Selbst die Verbesserung der Binärsuche (um den Einfügepunkt zu finden) schneidet nur die Vergleiche auf ceil(log_2(k)) , und wenn Sie nicht speziell einen zusätzlichen Vergleich mit dem k ten-fernen durchführen, sind Sie viel weniger wahrscheinlich die triviale Ablehnung der überwiegenden Mehrheit der Eingaben. Und es reduziert nicht die Anzahl der Züge, die Sie benötigen. Angesichts von Caching-Schemata und Verzweigungsvorhersage ist es nicht wahrscheinlich, dass es wesentlich schneller als 7 aufeinanderfolgende Vergleiche und dann 50 aufeinanderfolgende Schritte ist, 50 Vergleiche und Verschiebungen in Folge durchzuführen. Das ist der Grund, warum viele Systemtypen Quicksort zugunsten der Einfügesortierung für kleine Größen aufgeben.

Bedenken Sie auch, dass dies fast keinen zusätzlichen Speicher erfordert und dass der Algorithmus äußerst cachefreundlich ist (was für einen Heap oder eine Prioritätswarteschlange möglicherweise nicht zutrifft), und es ist trivial, ohne Fehler zu schreiben.

Der Prozess des Lesens der Datei ist wahrscheinlich der größte Engpass, so dass die wirklichen Leistungssteigerungen wahrscheinlich darin bestehen, eine einfache Lösung für die Auswahl zu finden. Sie können sich darauf konzentrieren, eine gute Pufferungsstrategie zur Minimierung der E / A zu finden.

Wenn k beliebig groß sein kann und sich n nähert, dann ist es sinnvoll, eine Prioritätswarteschlange oder eine andere, intelligentere Datenstruktur in Betracht zu ziehen. Eine andere Option wäre, die Eingabe in mehrere Teile aufzuteilen, sie jeweils parallel zu sortieren und dann zusammenzuführen.


Hier ist ein Python-Code, der den oben von ferdinand beyer vorgeschlagenen Algorithmus implementiert. Im Wesentlichen ist es ein Heap, der einzige Unterschied ist, dass die Löschung mit der Einfügeoperation zusammengeführt wurde

import random
import math

class myds:
""" implement a heap to find k greatest numbers out of all that are provided"""
k = 0
getnext = None
heap = []

def __init__(self, k, getnext ):
    """ k is the number of integers to return, getnext is a function that is called to get the next number, it returns a string to signal end of stream """
    assert k>0
    self.k = k
    self.getnext = getnext


def housekeeping_bubbleup(self, index):
    if index == 0:
        return()

    parent_index = int(math.floor((index-1)/2))
    if self.heap[parent_index] > self.heap[index]:
        self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
    self.housekeeping_bubbleup(parent_index)
    return()

def insertonly_level2(self, n):
    self.heap.append(n)
    #pdb.set_trace()
    self.housekeeping_bubbleup(len(self.heap)-1)

def insertonly_level1(self, n):
    """ runs first k times only, can be as slow as i want """
    if len(self.heap) == 0:
        self.heap.append(n)
        return()
    elif n > self.heap[0]:
        self.insertonly_level2(n)
    else:
        return()

def housekeeping_bubbledown(self, index, length):
    child_index_l = 2*index+1
    child_index_r = 2*index+2
    child_index = None
    if child_index_l >= length and child_index_r >= length: # No child
        return()
    elif child_index_r >= length: #only left child
        if self.heap[child_index_l] < self.heap[index]: # If the child is smaller
            child_index = child_index_l
        else:
            return()
    else: #both child
        if self.heap[ child_index_r] < self.heap[ child_index_l]:
            child_index = child_index_r
        else:
            child_index = child_index_l

    self.heap[index], self.heap[ child_index] = self.heap[child_index], self.heap[index]
    self.housekeeping_bubbledown(child_index, length)
    return()

def insertdelete_level1(self, n):
    self.heap[0] = n
    self.housekeeping_bubbledown(0, len(self.heap))
    return()

def insert_to_myds(self,  n ):
    if len(self.heap) < self.k:
        self.insertonly_level1(n)
    elif n > self.heap[0]:
        #pdb.set_trace()
        self.insertdelete_level1(n)
    else:
        return()

def run(self ):
    for n in self.getnext:
        self.insert_to_myds(n)
        print(self.heap)
        #            import pdb; pdb.set_trace()
    return(self.heap)

def createinput(n):
    input_arr = range(n)
    random.shuffle(input_arr)
    f = file('input', 'w')
    for value in input_arr:
        f.write(str(value))
        f.write('\n')

input_arr = []
with open('input') as f:
    input_arr = [int(x) for x in f]
myds_object = myds(4, iter(input_arr))
output = myds_object.run()
print output

Hier ist eine andere Lösung (über einen Äon später, ich habe keine Schande Entschuldigung!) Basierend auf dem zweiten von @paxdiablo zur Verfügung gestellt. Die Grundidee ist, dass Sie nur dann eine andere K-Zahl lesen sollten, wenn sie größer als das Minimum ist, das Sie bereits haben, und dass Sortieren nicht wirklich notwendig ist:

// your variables
n = 100
k = a number > n and << 1 billion
create array1[n], array2[k]

read first n numbers into array2
find minimum and maximum of array2 
while more numbers:
  if number > maximum:
    store in array1
    if array1 is full: // I don't need contents of array2 anymore
       array2 = array1
       array1 = []
  else if number > minimum:
    store in array2
    if array2 is full:
       x = n - array1.count()
       find the x largest numbers of array2 and discard the rest
       find minimum and maximum of array2
  else:
    discard the number
endwhile

// Finally
x = n - array1.count()
find the x largest numbers of array2 and discard the rest
return merge array1 and array2 

Der kritische Schritt ist die Funktion zum Finden der größten x Zahlen in Array2. Aber Sie können die Tatsache nutzen, dass Sie das Minimum und Maximum kennen, um die Funktion zum Finden der größten x Zahlen in Array2 zu beschleunigen.

Tatsächlich gibt es viele mögliche Optimierungen, da Sie es nicht wirklich sortieren müssen, Sie brauchen nur die x größten Zahlen.

Wenn k groß genug ist und Sie genug Speicher haben, können Sie es sogar in einen rekursiven Algorithmus umwandeln, um die n größten Zahlen zu finden.

Wenn die Zahlen bereits sortiert sind (in beliebiger Reihenfolge), ist der Algorithmus schließlich O (n).

Offensichtlich ist dies nur theoretisch, weil Sie in der Praxis Standardsortieralgorithmen verwenden würden und der Flaschenhals wahrscheinlich das IO wäre.


Ich denke, jemand hätte jetzt eine Prioritätswarteschlange erwähnen sollen. Sie müssen nur die aktuellen Top-100-Nummern behalten, wissen, was die niedrigste ist und in der Lage sein, diese durch eine höhere Zahl zu ersetzen. Das ist es, was eine Prioritätswarteschlange für Sie tut - einige Implementierungen können die Liste sortieren, aber es ist nicht erforderlich.


Ich glaube, der schnellste Weg dazu ist die Verwendung einer sehr großen Bitmap, um aufzuzeichnen, welche Zahlen vorhanden sind. Um eine 32-Bit-Ganzzahl darzustellen, müßte dies 2 ^ 32/8 Bytes sein, was ungefähr = 536 MB ist. Durchsuche die Ganzzahlen, indem du einfach das entsprechende Bit in der Bitmap setzt. Dann suche nach den höchsten 100 Einträgen.

Hinweis: das findet die höchsten 100 Nummern nicht die höchsten 100 Instanzen einer Nummer, wenn Sie den Unterschied sehen.

Diese Art von Ansatz wird in dem sehr guten Buch Programming Pearls diskutiert, das Ihr Interviewer vielleicht gelesen hat!


Offensichtlich möchten die Interviewer, dass Sie auf zwei wichtige Fakten hinweisen:

  • Sie können nicht die ganze Liste der ganzen Zahlen im Speicher lesen, da sie zu groß ist. Also müssen Sie es nacheinander lesen.
  • Sie benötigen eine effiziente Datenstruktur für die 100 größten Elemente. Diese Datenstruktur muss die folgenden Operationen unterstützen:
    • Get-Size : Holt die Anzahl der Werte im Container.
    • Find-Min : Ermitteln Sie den kleinsten Wert.
    • Delete-Min : Entferne den kleinsten Wert, um ihn durch einen neuen, größeren Wert zu ersetzen.
    • Insert : Fügen Sie ein anderes Element in den Container ein.

Ein Informatikprofessor würde erwarten, dass Sie einen Heap (Min-Heap) empfehlen, indem er die Anforderungen an die Datenstruktur bewertet, da er genau die Operationen unterstützt, die wir hier benötigen.

Zum Beispiel sind für Fibonacci-Heaps die Operationen Get-Size , Find-Min und Insert alle O(1) und Delete-Min ist O(log n) (mit n <= 100 in diesem Fall).

In der Praxis könnten Sie eine Prioritätswarteschlange aus der Standardbibliothek Ihrer bevorzugten Sprache verwenden (z. B. priority_queue aus #include <queue> in C ++), die normalerweise mit einem Heap implementiert wird.


Wenn Sie die Statistik der 100. Ordnung mit Schnellsortierung finden, wird sie im Durchschnitt O (Milliarde) funktionieren. Aber ich bezweifle, dass mit solchen Zahlen und aufgrund des für diesen Ansatz benötigten Direktzugriffs es schneller sein wird, als O (Milliarde log (100)).







sorting