Erzeugen einer ganzen Zahl, die nicht unter den vier Milliarden gegebenen Einsen ist

Question

Ich habe diese Frage im Vorstellungsgespräch gestellt bekommen:

Geben Sie einen Algorithmus für eine Eingabedatei mit vier Milliarden ganzen Zahlen an, um eine ganze Zahl zu erzeugen, die nicht in der Datei enthalten ist. Angenommen, Sie haben 1 GB Speicher. Erläutern Sie anschließend, was Sie tun würden, wenn Sie nur 10 MB Speicherplatz hätten.

Meine Analyse:

Die Größe der Datei beträgt 4×10 9 ×4 Bytes = 16 GB.

Wir können eine externe Sortierung vornehmen und kennen so den Bereich der ganzen Zahlen.

Meine Frage ist, was ist der beste Weg, um die fehlende ganze Zahl in der sortierten große ganze Zahl Sätze zu erkennen?

Mein Verständnis (nachdem ich alle Antworten gelesen habe):

Angenommen, es handelt sich um 32-Bit-Ganzzahlen, dann gibt es 2 32 \= 4*10 9 verschiedene ganze Zahlen.

Fall 1: wir haben 1 GB = 1 * 10 9 * 8 Bits = 8 Milliarden Bits Speicher.

Lösung:

Wenn wir ein Bit verwenden, das eine eindeutige ganze Zahl repräsentiert, reicht das aus und wir brauchen keine Sortierung.

Umsetzung:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Fall 2: 10 MB Speicher = 10 * 10 6 * 8 Bits = 80 Millionen Bits

Lösung:

Für alle möglichen 16-Bit-Präfixe gibt es 2 16 Anzahl von Ganzzahlen = 65536, wir brauchen 2 16 * 4 * 8 = 2 Millionen Bits. Wir müssen 65536 Buckets bilden. Für jeden Bucket benötigen wir 4 Bytes, die alle Möglichkeiten enthalten, da im schlimmsten Fall alle 4 Milliarden ganzen Zahlen zum selben Bucket gehören.

1. Erstellen Sie den Zähler für jeden Eimer beim ersten Durchlauf durch die Datei.
2. Scanne die Eimer und finde den ersten, der weniger als 65536 Treffer hat.
3. Erstellen Sie neue Buckets, deren hohe 16-Bit-Präfixe wir in Schritt 2 gefunden haben durch zweiten Durchlauf der Datei
4. Scannen Sie die in Schritt 3 erstellten Eimer und suchen Sie den ersten Eimer, der nicht einen Treffer hat.

Der Code ist dem obigen sehr ähnlich.

Schlussfolgerung: Wir verringern den Speicherplatz durch Erhöhung des Dateidurchlaufs.

---

Eine Klarstellung für diejenigen, die zu spät kommen: Die Frage, so wie sie gestellt wurde, besagt nicht, dass es genau eine ganze Zahl gibt, die nicht in der Datei enthalten ist - zumindest interpretieren die meisten Leute sie nicht so. Viele Kommentare im Kommentar-Thread sind über diese Variante der Aufgabe. Leider ist die Bemerkung, dass eingeführt wurde später von seinem Verfasser gelöscht, so dass es jetzt so aussieht, als hätten die verwaisten Antworten darauf einfach alles missverstanden. Das ist sehr verwirrend, tut mir leid.

Answer 1

Wenn es sich um 32-Bit-Ganzzahlen handelt (wahrscheinlich durch die Auswahl von ~4 Milliarden Zahlen nahe 2 32 ), wird Ihre Liste mit 4 Milliarden Zahlen höchstens 93 % der möglichen ganzen Zahlen umfassen (4 * 10 9 / (2 32 ) ). Wenn Sie also ein Bit-Array von 2 erstellen 32 Bits, wobei jedes Bit auf Null initialisiert ist (was 2 Sekunden in Anspruch nimmt) 29 Bytes ~ 500 MB RAM; zur Erinnerung: ein Byte = 2 3 Bits = 8 Bits), lesen Sie durch Ihre Integer-Liste und setzen Sie für jedes int das entsprechende Bit-Array-Element von 0 auf 1; und lesen Sie dann durch Ihr Bit-Array und geben Sie das erste Bit zurück, das noch 0 ist.

Für den Fall, dass Sie weniger RAM haben (~10 MB), muss diese Lösung leicht modifiziert werden. 10 MB ~ 83886080 Bits sind immer noch genug, um ein Bit-Array für alle Zahlen zwischen 0 und 83886079 zu erstellen. Man könnte also die Liste der Ints durchlesen und nur die Zahlen, die zwischen 0 und 83886079 liegen, in das Bit-Array aufnehmen. Wenn die Zahlen zufällig verteilt sind; mit überwältigender Wahrscheinlichkeit (sie unterscheiden sich zu 100% um etwa 10 -2592069 ) finden Sie ein fehlendes int). Wenn Sie nur die Zahlen 1 bis 2048 wählen (mit nur 256 Byte RAM), finden Sie in einem überwältigenden Prozentsatz (99,99999999999999999999999999999999999999999999999999999999999999999999999999999999999995 %) der Fälle eine fehlende Zahl.

Aber nehmen wir mal an, Sie hätten statt 4 Milliarden Zahlen nur etwa 2 32 - 1 Zahlen und weniger als 10 MB RAM; daher besteht bei jedem kleinen Bereich von Ints nur eine geringe Wahrscheinlichkeit, dass die Zahl nicht enthalten ist.

Wenn man sicher sein kann, dass jeder Wert in der Liste eindeutig ist, kann man die Zahlen addieren und die Summe mit einer fehlenden Zahl abziehen, um die volle Summe zu erhalten (½) (2 32 ) (2 32 - 1) = 9223372034707292160, um den fehlenden Wert zu finden. Wenn jedoch ein int zweimal vorkommt, schlägt diese Methode fehl.

Aber man kann immer teilen und erobern. Eine naive Methode wäre, das Array durchzulesen und die Anzahl der Zahlen zu zählen, die sich in der ersten Hälfte befinden (0 bis 2 31 -1) und zweite Hälfte (2 31 , 2 32 ). Wähle dann den Bereich mit weniger Zahlen und wiederhole die Teilung dieses Bereichs in zwei Hälften. (Angenommen, es gäbe zwei Zahlen weniger in (2 31 , 2 32 ), dann würde Ihre nächste Suche die Zahlen im Bereich (2 31 , 3*2 30 -1), (3*2 30 , 2 32 ). Wiederholen Sie dies so lange, bis Sie einen Bereich mit Nullzahlen gefunden haben, und Sie haben Ihre Antwort. Dies sollte O(lg N) ~ 32 Lesevorgänge durch das Array erfordern.

Diese Methode war ineffizient. Wir verwenden in jedem Schritt nur zwei Ganzzahlen (oder etwa 8 Byte RAM mit einer 4-Byte-(32-Bit-)Ganzzahl). Eine bessere Methode wäre, in sqrt(2) zu unterteilen 32 ) = 2 16 \= 65536 Bins mit jeweils 65536 Nummern in einem Bin. Jedes Bin benötigt 4 Bytes, um seine Anzahl zu speichern, also braucht man 2 18 Bytes = 256 kB. Bin 0 ist also (0 bis 65535=2 16 -1), Feld 1 ist (2 16 \=65536 bis 2*2 16 -1=131071), Feld 2 ist (2*2 16 \=131072 bis 3*2 16 -1=196607). In Python hätten Sie etwas wie:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Lesen Sie die ~4 Milliarden Integer-Liste und zählen Sie, wie viele Ints in jede der 2 Kategorien fallen. 16 bins und finden Sie ein unvollständiges_bin, das nicht alle 65536 Zahlen enthält. Dann lesen Sie die 4-Milliarden-Integer-Liste erneut durch, aber dieses Mal bemerken Sie nur, wenn Integer in diesem Bereich liegen, und flippen ein bisschen, wenn Sie sie finden.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

Answer 2

Warum sollte man es so kompliziert machen? Sie fragen nach einer ganzen Zahl, die nicht in der Datei vorhanden ist?

Nach den angegebenen Regeln müssen Sie nur die größte Ganzzahl speichern, die Sie bisher in der Datei angetroffen haben. Wenn die gesamte Datei gelesen wurde, geben Sie eine Zahl zurück, die um 1 größer ist als diese.

Es besteht keine Gefahr, auf maxint oder ähnliches zu stoßen, da es nach den Regeln keine Beschränkung für die Größe der Ganzzahl oder die vom Algorithmus zurückgegebene Zahl gibt.

Answer 3

Dies kann mit einer Variante der binären Suche auf sehr kleinem Raum gelöst werden.

1. Beginnen Sie mit dem zulässigen Zahlenbereich, 0 a 4294967295 .

2. Berechnen Sie den Mittelwert.

3. Schleife durch die Datei, wobei gezählt wird, wie viele Zahlen gleich, kleiner oder größer als der Mittelwert waren.

4. Wenn keine Zahlen gleich sind, bist du fertig. Die Zahl in der Mitte ist die Antwort.

5. Andernfalls wählen Sie den Bereich mit den wenigsten Zahlen und wiederholen Schritt 2 mit diesem neuen Bereich.

Dies erfordert bis zu 32 lineare Scans durch die Datei, aber es werden nur wenige Bytes Speicher für die Speicherung des Bereichs und der Zählungen benötigt.

Dies ist im Wesentlichen dasselbe wie Henning's Lösung mit dem Unterschied, dass es zwei Bins anstelle von 16k verwendet.

Answer 4

EDIT Ok, das war nicht ganz durchdacht, da es davon ausgeht, dass die ganzen Zahlen in der Datei einer statischen Verteilung folgen. Offensichtlich müssen sie das nicht, aber selbst dann sollte man dies versuchen:

---

Es gibt 4,3 Milliarden 32-Bit-Ganzzahlen. Wir wissen nicht, wie sie in der Datei verteilt sind, aber der ungünstigste Fall ist derjenige mit der höchsten Shannon-Entropie: eine Gleichverteilung. In diesem Fall ist die Wahrscheinlichkeit, dass eine beliebige ganze Zahl nicht in der Datei vorkommt

( (2³²-1)/2³² ) .4

Je niedriger die Shannon-Entropie ist, desto höher ist diese Wahrscheinlichkeit im Durchschnitt, aber selbst für diesen schlimmsten Fall haben wir eine Chance von 90 %, nach 5 Versuchen mit zufälligen ganzen Zahlen eine nicht vorkommende Zahl zu finden. Erzeugen Sie einfach solche Zahlen mit einem Pseudozufallsgenerator und speichern Sie sie in einer Liste. Lesen Sie dann eine Zahl nach der anderen und vergleichen Sie sie mit allen Ihren Vermutungen. Wenn es eine Übereinstimmung gibt, entfernen Sie diesen Listeneintrag. Nachdem Sie die gesamte Datei durchgelesen haben, haben Sie wahrscheinlich mehr als eine Vermutung übrig. Verwenden Sie eine davon. In dem seltenen Fall (10 % selbst im schlimmsten Fall), dass keine Vermutung übrig bleibt, erhalten Sie eine neue Reihe von zufälligen ganzen Zahlen, vielleicht diesmal mehr (10->99 %).

Speicherverbrauch: ein paar Dutzend Bytes, Komplexität: O(n), Overhead: vernachlässigbar, da die meiste Zeit ohnehin mit den unvermeidlichen Festplattenzugriffen verbracht wird, anstatt Ints zu vergleichen.

---

Der tatsächlich schlimmste Fall, wenn wir pas eine statische Verteilung annehmen, ist, dass jede ganze Zahl maximal einmal vorkommt, weil dann nur 1 - 4000000000/2³² 6% aller ganzen Zahlen nicht in der Datei vorkommen. Man braucht also etwas mehr Schätzungen, aber das kostet immer noch nicht viel Speicher.

Answer 5

Wenn eine ganze Zahl aus dem Bereich [0, 2^] fehlt x - 1] dann einfach xor sie alle zusammen. Zum Beispiel:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Ich weiß, dass dies keine Antwort auf die Frage ist genau aber es ist eine gute Antwort auf eine sehr ähnliche Frage).