Generieren Sie eine Ganzzahl, die nicht zu den vier Milliarden gehört

691

Ich habe diese Interviewfrage erhalten:

Geben Sie bei einer Eingabedatei mit vier Milliarden Ganzzahlen einen Algorithmus zum Generieren einer Ganzzahl an, die nicht in der Datei enthalten ist. Angenommen, Sie haben 1 GB Speicher. Folgen Sie Ihren Anweisungen, wenn Sie nur 10 MB Arbeitsspeicher haben.

Meine Analyse:

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

Wir können extern sortieren und so den Bereich der ganzen Zahlen kennen.

Meine Frage ist, wie man die fehlende Ganzzahl in den sortierten großen Ganzzahlensätzen am besten erkennt.

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 Ganzzahlen.

Fall 1: Wir haben 1 GB = 1 * 10 9 * 8 Bit = 8 Milliarden Bit Speicher.

Lösung:

Wenn wir ein Bit verwenden, das eine bestimmte Ganzzahl darstellt, reicht dies aus. Wir brauchen keine Sortierung.

Implementierung:

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 Bit = 80 Millionen Bit

Lösung:

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

  1. Erstellen Sie den Zähler jedes Buckets durch den ersten Durchgang durch die Datei.
  2. Scannen Sie die Eimer und finden Sie den ersten, der weniger als 65536 Treffer hat.
  3. Erstellen Sie neue Buckets, deren hohe 16-Bit-Präfixe in Schritt 2 bis zum zweiten Durchgang der Datei gefunden werden
  4. Scannen Sie die in Schritt 3 eingebauten Eimer und finden Sie den ersten Eimer, der keinen Treffer hat.

Der Code ist dem obigen sehr ähnlich.

Fazit: Wir verringern den Speicher durch Erhöhen des Dateipasses.


Eine Klarstellung für Verspätete: Die gestellte Frage besagt nicht, dass genau eine Ganzzahl nicht in der Datei enthalten ist - zumindest interpretieren die meisten Leute sie nicht so. Viele Kommentare im Kommentarthread beziehen sich jedoch auf diese Variation der Aufgabe. Leider wurde der Kommentar, der ihn in den Kommentarthread eingeführt hat, später von seinem Autor gelöscht. Jetzt sieht es so aus, als hätten die verwaisten Antworten darauf einfach alles falsch verstanden. Es ist sehr verwirrend, sorry.

SecureFish
quelle
32
@ Trashgod, falsch. Für 4294967295 eindeutige Ganzzahlen bleibt 1 Ganzzahl übrig. Um es zu finden, sollten Sie alle ganzen Zahlen summieren und von der vorberechneten Summe aller möglichen ganzen Zahlen subtrahieren.
Nakilon
58
Dies ist die zweite "Perle" aus "Programming Pearls", und ich würde vorschlagen, dass Sie die gesamte Diskussion im Buch lesen. Siehe books.google.com/…
Alok Singhal
8
@ Richard ein 64-Bit-Int wäre mehr als groß genug.
Cftarnas
79
int getMissingNumber(File inputFile) { return 4; }( Referenz )
Johnny
14
Es spielt keine Rolle, dass Sie nicht die Summe aller Ganzzahlen von 1 bis 2 ^ 32 speichern können, da der Ganzzahltyp in Sprachen wie C / C ++ IMMER Eigenschaften wie Assoziativität und Kommunikativität beibehält. Dies bedeutet, dass, obwohl die Summe nicht die richtige Antwort ist, wenn Sie die erwartete Summe mit Überlauf, die tatsächliche Summe mit Überlauf berechnen und dann subtrahieren, das Ergebnis immer noch korrekt ist (vorausgesetzt, es selbst läuft nicht über).
Tag dreht sich

Antworten:

529

Angenommen, "Ganzzahl" bedeutet 32 ​​Bit : 10 MB Speicherplatz sind mehr als genug, um zu zählen, wie viele Zahlen in der Eingabedatei mit einem bestimmten 16-Bit-Präfix für alle möglichen 16-Bit-Präfixe in einem Durchgang vorhanden sind Eingabedatei. Mindestens einer der Eimer wurde weniger als 2 16 Mal getroffen. Führen Sie einen zweiten Durchgang durch, um herauszufinden, welche der möglichen Nummern in diesem Bucket bereits verwendet werden.

Wenn es mehr als 32 Bit bedeutet, aber immer noch eine begrenzte Größe hat : Gehen Sie wie oben beschrieben vor und ignorieren Sie alle Eingabenummern, die zufällig außerhalb des 32-Bit-Bereichs (vorzeichenbehaftet oder vorzeichenlos; Ihrer Wahl) liegen.

Wenn "Ganzzahl" eine mathematische Ganzzahl bedeutet : Lesen Sie die Eingabe einmal durch und verfolgen Sie die größte Zahlenlänge der längsten Zahl, die Sie jemals gesehen haben. Wenn Sie fertig sind, geben Sie das Maximum plus eins als Zufallszahl mit einer weiteren Ziffer aus. (Eine der Zahlen in der Datei kann ein Bignum sein, für dessen genaue Darstellung mehr als 10 MB erforderlich sind. Wenn es sich bei der Eingabe jedoch um eine Datei handelt, können Sie zumindest die Länge von allem darstellen, was in die Datei passt.)

hmakholm hat Monica verlassen
quelle
24
Perfekt. Ihre erste Antwort erfordert nur 2 Durchgänge durch die Datei!
CorsiKa
47
Ein 10 MB Bignum? Das ist ziemlich extrem.
Mark Ransom
12
@Legate, überspringe einfach übergroße Zahlen und tue nichts dagegen. Da Sie ohnehin keine übergroße Zahl ausgeben, müssen Sie nicht nachverfolgen, welche davon Sie gesehen haben.
Hmakholm verließ Monica
12
Das Gute an Lösung 1 ist, dass Sie den Speicher verringern können, indem Sie die Durchgänge erhöhen.
Yousf
11
@Barry: Die obige Frage zeigt nicht an, dass genau eine Nummer fehlt. Es heißt auch nicht, dass sich die Zahlen in der Datei nicht wiederholen. (Der tatsächlich gestellten Frage zu folgen ist wahrscheinlich eine gute Idee in einem Interview, oder? ;-))
Christopher Creutzig
197

Statistisch informierte Algorithmen lösen dieses Problem mit weniger Durchgängen als deterministische Ansätze.

Wenn sehr große Ganzzahlen zulässig sind, kann eine Zahl generiert werden, die in O (1) -Zeit wahrscheinlich eindeutig ist. Eine pseudozufällige 128-Bit-Ganzzahl wie eine GUID kollidiert nur in weniger als einer von 64 Milliarden Milliarden Fällen mit einer der vorhandenen vier Milliarden Ganzzahlen in der Menge.

Wenn Ganzzahlen auf 32 Bit begrenzt sind, kann mit weniger als 10 MB eine Zahl generiert werden, die wahrscheinlich in einem einzigen Durchgang eindeutig ist. Die Wahrscheinlichkeit, dass eine pseudozufällige 32-Bit-Ganzzahl mit einer der 4 Milliarden vorhandenen Ganzzahlen kollidiert, liegt bei 93% (4e9 / 2 ^ 32). Die Wahrscheinlichkeit, dass 1000 pseudozufällige ganze Zahlen kollidieren, beträgt weniger als eine von 12.000 Milliarden Milliarden Milliarden (Wahrscheinlichkeit einer Kollision ^ 1000). Wenn also ein Programm eine Datenstruktur mit 1000 Pseudozufallskandidaten beibehält und die bekannten Ganzzahlen durchläuft, wodurch Übereinstimmungen aus den Kandidaten eliminiert werden, ist es so gut wie sicher, mindestens eine Ganzzahl zu finden, die nicht in der Datei enthalten ist.

Ben Haley
quelle
32
Ich bin mir ziemlich sicher, dass die ganzen Zahlen begrenzt sind. Wenn dies nicht der Fall wäre, würde selbst ein Anfängerprogrammierer an den Algorithmus denken: "Machen Sie einen Durchgang durch die Daten, um die maximale Anzahl zu finden, und addieren Sie 1 dazu"
Adrian Petrescu
12
Wenn Sie buchstäblich eine zufällige Ausgabe erraten, erhalten Sie wahrscheinlich nicht viele Punkte für ein Interview
Brian Gordon,
6
@Adrian, deine Lösung scheint offensichtlich (und es war für mich, ich habe sie in meiner eigenen Antwort verwendet), aber es ist nicht für alle offensichtlich. Es ist ein guter Test, um zu sehen, ob Sie offensichtliche Lösungen erkennen können oder ob Sie alles, was Sie berühren, zu kompliziert machen.
Mark Ransom
19
@Brian: Ich denke, diese Lösung ist sowohl einfallsreich als auch praktisch. Ich jedenfalls würde viel Lob für diese Antwort geben.
Richard H
6
ah hier liegt die Grenze zwischen Ingenieuren und Wissenschaftlern. Tolle Antwort Ben!
TrojanName
142

Eine ausführliche Diskussion über dieses Problem wird in diskutiert Jon Bentley "Spalte 1. Cracking the Oyster" Programmieren Pearls Addison-Wesley pp.3-10

Bentley diskutiert verschiedene Ansätze, einschließlich externer Sortierung, Zusammenführungssortierung unter Verwendung mehrerer externer Dateien usw. Die beste Methode, die Bentley vorschlägt, ist ein Single-Pass-Algorithmus unter Verwendung von Bitfeldern , den er humorvoll "Wonder Sort" nennt :) Kommen wir zum Problem, 4 Milliarden Zahlen können dargestellt werden in:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

Der Code zum Implementieren des Bitsets ist einfach: (von der Lösungsseite entnommen )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Der Bentley-Algorithmus führt einen einzelnen Durchlauf durch die Datei durch, settippt das entsprechende Bit im Array und untersucht dieses Array dann mithilfe des testobigen Makros, um die fehlende Nummer zu finden.

Wenn der verfügbare Speicher weniger als 0,466 GB beträgt, schlägt Bentley einen k-Pass-Algorithmus vor, der die Eingabe je nach verfügbarem Speicher in Bereiche unterteilt. Um ein sehr einfaches Beispiel zu nennen: Wenn nur 1 Byte (dh Speicher für 8 Zahlen) verfügbar war und der Bereich zwischen 0 und 31 lag, teilen wir dies in Bereiche von 0 bis 7, 8-15, 16-22 usw. auf und behandeln Sie diesen Bereich in jedem 32/8 = 4Durchgang.

HTH.

Weinstock
quelle
12
Ich kenne das Buch nicht, aber keinen Grund, es "Wonder Sort" zu nennen, da es nur eine Bucketsort mit einem 1-Bit-Zähler ist.
Flolo
3
Obwohl dieser Code portabler ist, wird er durch Code vernichtet , der geschrieben wurde, um hardwareunterstützte Vektoranweisungen zu verwenden . Ich denke, dass gcc in einigen Fällen Code automatisch in Vektoroperationen konvertieren kann.
Brian Gordon
3
@brian Ich glaube nicht, dass Jon Bentley solche Dinge in sein Buch über Algorithmen aufgenommen hat.
David Heffernan
8
@BrianGordon, die im RAM verbrachte Zeit ist im Vergleich zur Zeit, die zum Lesen der Datei aufgewendet wird, vernachlässigbar. Vergessen Sie die Optimierung.
Ian
1
@BrianGordon: Oder hast du über die Schleife am Ende gesprochen, um das erste nicht gesetzte Bit zu finden? Ja, Vektoren beschleunigen dies, aber sie durchlaufen das Bitfeld mit 64-Bit-Ganzzahlen und suchen nach einer, die != -1die auf einem einzelnen Kern laufende Speicherbandbreite noch sättigt (dies ist SIMD innerhalb eines Registers, SWAR, mit Bits als Elementen). (Für aktuelle Intel / AMD-Designs). Sie müssen erst herausfinden, welches Bit nicht gesetzt ist, nachdem Sie den 64-Bit-Speicherort gefunden haben, der es enthält. (Und dafür können Sie not / lzcnt.) Fair Point, dass das Durchlaufen eines Einzelbit-Tests möglicherweise nicht gut optimiert wird.
Peter Cordes
120

Da das Problem nicht angibt, dass wir die kleinstmögliche Nummer finden müssen, die nicht in der Datei enthalten ist, können wir einfach eine Nummer generieren, die länger als die Eingabedatei selbst ist. :) :)

Andris
quelle
6
Wenn die größte Zahl in der Datei nicht max int ist, werden Sie einfach überlaufen
KBusc
Wie groß wäre diese Datei in einem Programm der realen Welt, das möglicherweise eine neue Ganzzahl generieren und 100 Mal an die Datei "Verwendete Ganzzahlen" anhängen muss?
Michael
2
Ich habe das gedacht. Angenommen, es inthandelt sich um 32Bits, die nur ausgegeben werden 2^64-1. Erledigt.
Imallett
1
Wenn es ein int pro Zeile ist tr -d '\n' < nums.txt > new_num.txt
::
56

Für die 1 GB RAM-Variante können Sie einen Bitvektor verwenden. Sie müssen 4 Milliarden Bits == 500 MB Byte-Array zuweisen. Setzen Sie für jede Zahl, die Sie vom Eingang lesen, das entsprechende Bit auf '1'. Wenn Sie fertig sind, durchlaufen Sie die Bits und suchen Sie die erste, die noch '0' ist. Sein Index ist die Antwort.

Itay Maman
quelle
4
Der Zahlenbereich in der Eingabe ist nicht angegeben. Wie funktioniert dieser Algorithmus, wenn die Eingabe aus allen geraden Zahlen zwischen 8 und 16 Milliarden besteht?
Mark Ransom
27
@Mark, ignorieren Sie einfach Eingaben, die außerhalb des Bereichs 0..2 ^ 32 liegen. Sie werden sowieso keine von ihnen ausgeben, sodass Sie sich nicht merken müssen, welche von ihnen vermieden werden sollen.
Hmakholm verließ Monica
@Markieren Sie den Algorithmus, mit dem Sie bestimmen, wie eine 32-Bit-Zeichenfolge einer reellen Zahl zugeordnet wird. Der Prozess ist immer noch der gleiche. Der einzige Unterschied besteht darin, wie Sie es als reelle Zahl auf dem Bildschirm drucken.
CorsiKa
4
Anstatt sich selbst zu bitSet.nextClearBit(0)
wiederholen,
3
Es wäre nützlich zu erwähnen, dass unabhängig vom Bereich der ganzen Zahlen am Ende des Durchlaufs garantiert ist, dass mindestens ein Bit 0 ist. Dies ist auf das Pigeonhole-Prinzip zurückzuführen.
Rafał Dowgird
46

Wenn es sich um 32-Bit-Ganzzahlen handelt (wahrscheinlich aus der Auswahl von ~ 4 Milliarden Zahlen nahe 2 32 ), nimmt Ihre Liste mit 4 Milliarden Zahlen höchstens 93% der möglichen Ganzzahlen ein (4 * 10 9 / (2 32 )). ). Wenn Sie also ein Bit-Array von 2 32 Bit erstellen, wobei jedes Bit auf Null initialisiert ist (was 2 29 Byte ~ 500 MB RAM beansprucht; denken Sie an ein Byte = 2 3 Bit = 8 Bit), lesen Sie Ihre Ganzzahlliste und durch für jeden int setze das entsprechende Bit-Array-Element von 0 auf 1; Lesen Sie dann Ihr Bit-Array durch und geben Sie das erste Bit zurück, das noch 0 ist.

Wenn Sie weniger RAM (~ 10 MB) haben, muss diese Lösung leicht modifiziert werden. 10 MB ~ 83886080 Bit reichen immer noch aus, um ein Bit-Array für alle Zahlen zwischen 0 und 83886079 zu erstellen. Sie können also Ihre Liste der Ints durchlesen. und zeichnen Sie nur #s auf, die zwischen 0 und 83886079 in Ihrem Bit-Array liegen. Wenn die Zahlen zufällig verteilt sind; mit überwältigender Wahrscheinlichkeit (es unterscheidet sich um 100% um etwa 10 -2592069 ) finden Sie ein fehlendes int). Wenn Sie nur die Nummern 1 bis 2048 (mit nur 256 Byte RAM) auswählen, wird eine fehlende Nummer immer noch einen überwältigenden Prozentsatz (99,999999999999999999999999999999999999999999999999999999999999999999%) der Zeit finden.

Aber sagen wir, anstatt ungefähr 4 Milliarden Zahlen zu haben; Sie hatten ungefähr 2 32 - 1 Nummern und weniger als 10 MB RAM; Daher hat jeder kleine Bereich von Ints nur eine geringe Möglichkeit, die Zahl nicht zu enthalten.

Wenn Sie garantiert hätten, dass jedes int in der Liste eindeutig ist, könnten Sie die Zahlen summieren und die Summe mit einem fehlenden # von der vollen Summe (½) (2 32 ) (2 32 - 1) = 9223372034707292160 subtrahieren, um das fehlende int zu finden . Wenn jedoch zweimal ein int aufgetreten ist, schlägt diese Methode fehl.

Sie können jedoch immer teilen und erobern. Eine naive Methode wäre, das Array durchzulesen und die Anzahl der Zahlen in der ersten Hälfte (0 bis 2 31 -1) und der zweiten Hälfte (2 31 , 2 32 ) zu zählen. Wählen Sie dann den Bereich mit weniger Zahlen und wiederholen Sie die Aufteilung dieses Bereichs in zwei Hälften. (Wenn in (2 31 , 2 32 ) zwei weniger Zahlen enthalten wären, würde Ihre nächste Suche die Zahlen im Bereich (2 31 , 3 * 2 30 -1), (3 * 2 30 , 2 32 ) zählen. Behalten Wiederholen, bis Sie einen Bereich mit Nullzahlen gefunden haben und Ihre Antwort haben. Sollte O (lg N) ~ 32 Lesevorgänge durch das Array dauern.

Diese Methode war ineffizient. Wir verwenden nur zwei Ganzzahlen in jedem Schritt (oder ungefähr 8 Bytes RAM mit einer 4-Byte-Ganzzahl (32-Bit)). Eine bessere Methode wäre die Aufteilung in sqrt (2 32 ) = 2 16 = 65536 Bins mit jeweils 65536 Zahlen in einem Bin. Jeder Bin benötigt 4 Bytes, um seine Anzahl zu speichern, also benötigen Sie 2 18 Bytes = 256 kB. Also ist Bin 0 (0 bis 65535 = 2 16 -1), Bin 1 ist (2 16 = 65536 bis 2 * 2 16 -1 = 131071), Bin 2 ist (2 * 2 16 = 131072 bis 3 * 2 16 - 1 = 196607). In Python hätten Sie so 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 Ganzzahlliste durch. und zählen Sie, wie viele Ints in jeden der 2 16 Bins fallen, und finden Sie einen unvollständigen_Bin, der nicht alle 65536-Nummern enthält. Dann lesen Sie die 4-Milliarden-Integer-Liste erneut durch. Beachten Sie diesmal jedoch nur, wenn ganze Zahlen in diesem Bereich liegen. ein bisschen umdrehen, 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
Dr. Jimbob
quelle
3
So eine tolle Antwort. Das würde tatsächlich funktionieren; und hat Ergebnisse garantiert.
Jonathan Dickinson
@dr jimbob, was ist, wenn sich nur eine Nummer in einem Papierkorb befindet und diese einzelne Nummer 65535 Duplikate enthält? In diesem Fall zählt der Behälter immer noch 65536, aber alle 65536-Nummern sind gleich.
Alcott
@Alcott - Ich nahm an, dass Sie 2 ^ 32-1 (oder weniger) Zahlen hatten, so dass Sie nach dem Pigeonhole-Prinzip garantiert einen Behälter mit weniger als 65536 Zählungen haben, um detaillierter zu prüfen. Wir versuchen, nur eine fehlende Ganzzahl zu finden, nicht alle. Wenn Sie 2 ^ 32 oder mehr Zahlen hatten, können Sie eine fehlende Ganzzahl nicht garantieren und können diese Methode nicht verwenden (oder von Anfang an haben Sie eine Garantie, dass eine Ganzzahl fehlt). Ihre beste Wahl wäre dann Brute Force (z. B. 32-mal das Array durchlesen, die ersten 65536 # beim ersten Mal überprüfen und anhalten, sobald eine Antwort gefunden wurde).
Dr. Jimbob
Die clevere Methode der oberen 16 / unteren 16 wurde bereits von Henning veröffentlicht: stackoverflow.com/a/7153822/224132 . Ich mochte die Add-Them-Up-Idee für einen einzigartigen Satz von Ganzzahlen, bei denen genau ein Mitglied fehlt.
Peter Cordes
3
@PeterCordes - Ja, Hennings Lösung ist älter als meine, aber ich denke, meine Antwort ist immer noch nützlich (einige Dinge genauer durcharbeiten). Trotzdem schlug Jon Bentley in seinem Buch Programming Pearls eine Multi-Pass-Option für dieses Problem vor (siehe die Antwort von Vine'th), lange bevor es einen Stackoverflow gab (nicht, dass ich behaupte, einer von uns hätte bewusst von dort gestohlen oder Bentley war der erste, der dies tat dieses Problem analysieren - es ist eine ziemlich natürliche Lösung zu entwickeln). Zwei Durchgänge scheinen am natürlichsten zu sein, wenn die Einschränkung darin besteht, dass Sie nicht mehr über genügend Speicher für eine 1-Durchlauf-Lösung mit einem riesigen Bit-Array verfügen.
Dr. Jimbob
37

Warum es so kompliziert machen? Sie fragen nach einer Ganzzahl, die in der Datei nicht vorhanden ist?

Gemäß den angegebenen Regeln müssen Sie nur die größte Ganzzahl speichern, die Sie bisher in der Datei gefunden haben. Geben Sie nach dem Lesen der gesamten Datei eine größere Zahl 1 zurück.

Es besteht kein Risiko, Maxint oder etwas anderes zu treffen, da gemäß den Regeln keine Einschränkung hinsichtlich der Größe der Ganzzahl oder der vom Algorithmus zurückgegebenen Zahl besteht.

Pete
quelle
4
Dies würde funktionieren, wenn nicht das max int in der Datei wäre, was durchaus möglich ist ...
PearsonArtPhoto
13
Die Regeln geben nicht an, dass es sich um 32-Bit oder 64-Bit oder etwas anderes handelt. Gemäß den angegebenen Regeln gibt es also kein max int. Ganzzahl ist kein Computerbegriff, sondern ein mathematischer Begriff, der positive oder negative ganze Zahlen identifiziert.
Pete
Das stimmt, aber man kann nicht davon ausgehen, dass es sich um eine 64-Bit-Zahl handelt oder dass sich jemand nicht einfach in die maximale int-Zahl einschleicht, um solche Algorithmen zu verwirren.
PearsonArtPhoto
24
Der gesamte Begriff "max int" ist im Kontext nicht gültig, wenn keine Programmiersprache angegeben wurde. Schauen Sie sich beispielsweise Pythons Definition einer langen Ganzzahl an. Es ist grenzenlos. Es gibt kein Dach. Sie können jederzeit eine hinzufügen. Sie gehen davon aus, dass es in einer Sprache implementiert wird, die einen maximal zulässigen Wert für eine Ganzzahl hat.
Pete
32

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

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

  2. Berechnen Sie den Mittelpunkt.

  3. Durchlaufen Sie die Datei und zählen Sie, wie viele Zahlen gleich oder kleiner als der Mittelpunkt waren.

  4. Wenn keine Zahlen gleich waren, sind Sie fertig. Die Mittelpunktnummer ist die Antwort.

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

Dies erfordert bis zu 32 lineare Scans durch die Datei, benötigt jedoch nur wenige Byte Speicher zum Speichern des Bereichs und der Anzahl.

Dies entspricht im Wesentlichen der Lösung von Henning , außer dass zwei Behälter anstelle von 16 KB verwendet werden.

Hammar
quelle
2
Damit habe ich begonnen, bevor ich anfing, für die angegebenen Parameter zu optimieren.
Hmakholm verließ Monica
@ Henning: Cool. Es ist ein schönes Beispiel für einen Algorithmus, bei dem es einfach ist, den Raum-Zeit-Kompromiss zu optimieren.
Hammar
@ Hammar, aber was ist, wenn es diese Zahlen gibt, die mehr als einmal erscheinen?
Alcott
@Alcott: Dann wählt der Algorithmus den dichteren Behälter anstelle des sparseren Behälters aus, aber nach dem Pigeonhole-Prinzip kann er niemals einen vollständig vollen Behälter auswählen. (Die kleinere der beiden Zählungen ist immer kleiner als der Behälterbereich.)
Peter Cordes
27

BEARBEITEN Ok, dies war nicht ganz durchdacht, da davon ausgegangen wird, dass die Ganzzahlen in der Datei einer statischen Verteilung folgen. Anscheinend müssen sie 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 schlimmste Fall ist der mit der höchsten Shannon-Entropie: eine gleichmäßige Verteilung. In diesem Fall ist es wahrscheinlich, dass eine Ganzzahl nicht in der Datei vorkommt

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

Je niedriger die Shannon-Entropie ist, desto höher wird diese Wahrscheinlichkeit im Durchschnitt, aber selbst für diesen schlimmsten Fall haben wir eine Chance von 90%, nach 5 Vermutungen mit zufälligen ganzen Zahlen eine nicht vorkommende Zahl zu finden. Erstellen Sie solche Zahlen einfach mit einem Pseudozufallsgenerator und speichern Sie sie in einer Liste. Lesen Sie dann int nach int und vergleichen Sie es mit all Ihren Vermutungen. Wenn es eine Übereinstimmung gibt, entfernen Sie diesen Listeneintrag. Nachdem Sie die gesamte Datei durchgesehen haben, haben Sie wahrscheinlich noch mehr als eine Vermutung. Verwenden Sie einen von ihnen. In dem seltenen Fall (10% sogar im schlimmsten Fall), in dem keine Vermutung mehr besteht, erhalten Sie einen neuen Satz zufälliger Ganzzahlen, diesmal vielleicht mehr (10-> 99%).

Speicherverbrauch: einige Dutzend Bytes, Komplexität: O (n), Overhead: Nukleierbar, da die meiste Zeit für unvermeidbare Festplattenzugriffe aufgewendet wird, anstatt Ints zu vergleichen.


Der tatsächliche schlimmste Fall, wenn wir nicht ist eine statische Verteilung annehmen, dass jede Zahl max auftritt. einmal, weil dann nur 1 - 4000000000/2³² ≈ 6% aller ganzen Zahlen nicht in der Datei vorkommen. Sie brauchen also noch einige Vermutungen, aber das kostet immer noch keine schädlichen Mengen an Speicher.

links herum
quelle
5
Ich bin froh zu sehen, dass jemand anderes darüber nachgedacht hat, aber warum ist es hier unten so weit unten? Dies ist ein Algo mit 1 Durchgang… 10 MB reichen für 2,5 M-Vermutungen aus, und 93% ^ 2,5 M ≈ 10 ^ -79000 sind wirklich eine vernachlässigbare Chance, einen zweiten Scan zu benötigen. Aufgrund des Overheads der binären Suche geht es schneller, wenn Sie weniger Vermutungen verwenden! Dies ist zeitlich und räumlich optimal.
Potatoswatter
1
@ Potatoswatter: Gut, dass Sie die binäre Suche erwähnt haben. Das ist den Aufwand wahrscheinlich nicht wert, wenn nur 5 Vermutungen verwendet werden, aber es liegt sicherlich bei 10 oder mehr. Sie könnten sogar die 2 M-Vermutungen anstellen, aber dann sollten Sie sie in einem Hash-Set speichern, um O (1) für die Suche zu erhalten.
links um den
1
@ Potatoswatter Ben Haleys gleichwertige Antwort ist ganz oben
Brian Gordon
1
Ich mag diesen Ansatz, würde aber eine speichersparende Verbesserung vorschlagen: Wenn N Bits indizierten Speichers plus konstanten Speicher verfügbar sind, definieren Sie eine konfigurierbare reversible 32-Bit-Verschlüsselungsfunktion (Permutation), wählen Sie eine beliebige Permutation aus und löschen Sie alle indizierte Bits. Lesen Sie dann jede Zahl aus der Datei, verschlüsseln Sie sie und setzen Sie das entsprechende Bit, wenn das Ergebnis kleiner als N ist. Wenn am Ende der Datei kein Bit gesetzt ist, kehren Sie die Verschlüsselungsfunktion für den Index um. Mit 64 KB Speicher könnten über 512.000 Nummern in einem Durchgang effektiv auf Verfügbarkeit getestet werden.
Supercat
2
Bei diesem Algorithmus ist der schlimmste Fall natürlich einer, bei dem die Zahlen von demselben Zufallszahlengenerator erstellt wurden, den Sie verwenden. Angenommen, Sie können garantieren, dass dies nicht der Fall ist, besteht Ihre beste Taktik darin, einen linearen kongruenten Zufallszahlengenerator zu verwenden, um Ihre Liste zu generieren, sodass Sie den Zahlenraum pseudozufällig durchlaufen. Das heißt, wenn Sie irgendwie versagen, können Sie so lange Zahlen generieren, bis Sie den gesamten Bereich der Ints abgedeckt haben (oder eine Lücke gefunden haben), ohne jemals Ihren Aufwand zu verdoppeln.
Dewi Morgan
25

Wenn im Bereich [0, 2 ^ x - 1] eine Ganzzahl fehlt, xor sie einfach alle zusammen. Zum Beispiel:

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

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

rfrankel
quelle
1
Ja, es ist leicht zu beweisen, dass [ ] funktioniert, wenn eine Ganzzahl fehlt, aber es schlägt häufig fehl, wenn mehr als eine fehlt. Zum Beispiel 0 ^ 1 ^ 3 ^ 4 ^ 6 ^ 7ist 0. [ Schreiben von 2 x für 2 bis x'te Potenz und a ^ b für a xor b, das xor aller k <2 x ist Null - k ^ ~ k = (2 ^ x) - 1 für k <2 ^ (x-1) und k ^ ~ k ^ j ^ ~ j = 0, wenn j = k + 2 ** (x-2) - also ist das xor aller bis auf eine Zahl der Wert des Vermissten]
James Waldby - jwpat7
2
Wie ich in einem Kommentar zur Antwort von ircmaxell erwähne: Das Problem besagt nicht, dass "eine Nummer fehlt", sondern dass eine Nummer gefunden werden muss, die nicht in den 4 Milliarden Nummern in der Datei enthalten ist. Wenn wir 32-Bit-Ganzzahlen annehmen, fehlen möglicherweise etwa 300 Millionen Zahlen in der Datei. Die Wahrscheinlichkeit, dass das xor der vorhandenen Zahlen mit einer fehlenden Zahl übereinstimmt, beträgt nur etwa 7%.
James Waldby - jwpat7
Dies ist die Antwort, an die ich gedacht habe, als ich die Frage zum ersten Mal gelesen habe, aber bei näherer Betrachtung denke ich, dass die Frage mehrdeutiger ist als diese. Zu Ihrer Information
Lee Netherton
18

Sie suchen möglicherweise nach einem probabilistischen Bloom-Filter, der sehr effizient absolut bestimmen kann, ob ein Wert nicht Teil einer großen Menge ist (aber nur mit hoher Wahrscheinlichkeit feststellen kann, dass er Mitglied der Menge ist).

Paul
quelle
4
Mit wahrscheinlich über 90% der möglichen Werte müsste Ihr Bloom-Filter wahrscheinlich in das Bitfeld ausarten, das bereits von so vielen Antworten verwendet wird. Andernfalls erhalten Sie nur einen nutzlosen, vollständig gefüllten Bitstring.
Christopher Creutzig
@ Christopher Mein Verständnis von Bloom-Filtern ist, dass Sie kein gefülltes Bitarray erhalten, bis Sie 100% erreichen
Paul
... sonst würden Sie falsche Negative bekommen.
Paul
@Paul Ein gefülltes Bit-Array gibt Ihnen falsch positive Ergebnisse, die zulässig sind. In diesem Fall würde der Bloom-Filter höchstwahrscheinlich zu dem Fall degenerieren, in dem die Lösung, die negativ wäre, ein falsch positives Ergebnis zurückgibt.
Ataylor
1
@Paul: Sie können ein gefülltes Bitarray erhalten, sobald die Anzahl der Hash-Funktionen multipliziert mit der Anzahl der Einträge so groß ist wie die Länge Ihres Feldes. Das wäre natürlich ein Ausnahmefall, aber die Wahrscheinlichkeit wird ziemlich schnell steigen.
Christopher Creutzig
17

Basierend auf dem aktuellen Wortlaut der ursprünglichen Frage lautet die einfachste Lösung:

Suchen Sie den Maximalwert in der Datei und fügen Sie 1 hinzu.

oosterwal
quelle
5
Was ist, wenn der MAXINT in der Datei enthalten ist?
Petr Peller
@Petr Peller: Eine BIGINT-Bibliothek würde im Wesentlichen Einschränkungen der Ganzzahlgröße aufheben.
Oosterwal
2
@oosterwal, wenn diese Antwort erlaubt war, müssen Sie die Datei nicht einmal lesen - drucken Sie einfach so viele Zahlen wie möglich.
Nakilon
1
@oosterwal, wenn Ihre zufällige große Zahl die größte war, die Sie drucken konnten, und sie sich in einer Datei befand, konnte diese Aufgabe nicht gelöst werden.
Nakilon
3
@ Nakilon: +1 Dein Punkt ist vergeben. Dies entspricht in etwa der Ermittlung der Gesamtzahl der Ziffern in der Datei und dem Drucken einer Zahl mit so vielen Ziffern.
Oosterwal
14

Verwenden Sie a BitSet. 4 Milliarden Ganzzahlen (unter der Annahme von bis zu 2 ^ 32 Ganzzahlen), die mit 8 pro Byte in ein BitSet gepackt werden, sind 2 ^ 32/2 ^ 3 = 2 ^ 29 = ca. 0,5 GB.

Um ein bisschen mehr Details hinzuzufügen - setzen Sie jedes Mal, wenn Sie eine Zahl lesen, das entsprechende Bit im BitSet. Führen Sie dann einen Durchlauf über das BitSet durch, um die erste Nummer zu finden, die nicht vorhanden ist. In der Tat können Sie dies genauso effektiv tun, indem Sie wiederholt eine Zufallszahl auswählen und testen, ob sie vorhanden ist.

Tatsächlich teilt Ihnen BitSet.nextClearBit (0) das erste nicht gesetzte Bit mit.

Wenn Sie sich die BitSet-API ansehen, scheint sie nur 0..MAX_INT zu unterstützen, sodass Sie möglicherweise 2 BitSets benötigen - eines für + fünf Nummern und eines für nicht vorhandene Nummern -, aber die Speicheranforderungen ändern sich nicht.

dty
quelle
1
Oder wenn Sie kein ... verwenden möchten, BitSetversuchen Sie es mit einem Array von Bits. Tut das gleiche;)
jcolebrand
12

Wenn es keine Größenbeschränkung gibt, können Sie am schnellsten die Länge der Datei ermitteln und die Länge der Datei + 1 Anzahl zufälliger Ziffern (oder nur "11111 ...") generieren. Vorteil: Sie müssen die Datei nicht einmal lesen und können den Speicherbedarf auf nahezu Null reduzieren. Nachteil: Sie drucken Milliarden von Ziffern.

Wenn jedoch der einzige Faktor die Minimierung der Speichernutzung wäre und nichts anderes wichtig ist, wäre dies die optimale Lösung. Es könnte sogar zu einer Auszeichnung für den "schlimmsten Missbrauch der Regeln" führen.

vsz
quelle
11

Wenn wir davon ausgehen, dass der Zahlenbereich immer 2 ^ n ist (eine gerade Potenz von 2), dann exklusiv - oder funktioniert (wie auf einem anderen Poster gezeigt). Was den Grund angeht, beweisen wir es:

Die Theorie

Bei einem beliebigen 0-basierten Bereich von Ganzzahlen, bei dem 2^nElemente mit einem Element fehlen, können Sie dieses fehlende Element finden, indem Sie einfach die bekannten Werte zusammen xorieren, um die fehlende Zahl zu erhalten.

Der Beweis

Schauen wir uns n = 2 an. Für n = 2 können wir 4 eindeutige ganze Zahlen darstellen: 0, 1, 2, 3. Sie haben ein Bitmuster von:

  • 0 - 00
  • 1 - 01
  • 2 - 10
  • 3 - 11

Wenn wir jetzt schauen, wird jedes einzelne Bit genau zweimal gesetzt. Da es eine gerade Anzahl von Malen gesetzt ist und Exklusiv-oder der Nummern 0 ergibt, ergibt das Exklusiv-Oder eine Nummer, die, wenn Exklusiv mit der fehlenden Nummer angegeben wird, ergibt 0. Daher sind die fehlende Nummer und die resultierende exklusive Nummer genau gleich. Wenn wir 2 entfernen, ist das resultierende xor 10(oder 2).

Schauen wir uns nun n + 1 an. Rufen wir an, wie oft jedes Bit gesetzt nist xund wie oft jedes Bit gesetzt ist n+1 y. Der Wert von yist gleich, y = x * 2weil es xElemente gibt, bei denen das n+1Bit auf 0 gesetzt ist, und xElemente, bei denen das n+1Bit auf 1 gesetzt ist. Und da 2ximmer gerade ist, n+1wird jedes Bit immer gerade gesetzt.

Da n=2funktioniert und n+1funktioniert, funktioniert die xor-Methode daher für alle Werte von n>=2.

Der Algorithmus für 0-basierte Bereiche

Das ist ganz einfach. Es werden 2 * n Speicherbits verwendet, sodass für jeden Bereich <= 32 2 32-Bit-Ganzzahlen funktionieren (wobei der vom Dateideskriptor belegte Speicher ignoriert wird). Und es macht einen einzigen Durchgang der Datei.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

Der Algorithmus für willkürlich basierte Bereiche

Dieser Algorithmus funktioniert für Bereiche von beliebiger Startnummer bis zu beliebiger Endzahl, solange der Gesamtbereich gleich 2 ^ n ist. Dadurch wird der Bereich grundsätzlich so neu aufgebaut, dass das Minimum bei 0 liegt. Es sind jedoch 2 Durchgänge erforderlich durch die Datei (die erste, um das Minimum zu erreichen, die zweite, um das fehlende int zu berechnen).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Beliebige Bereiche

Wir können diese modifizierte Methode auf eine Reihe beliebiger Bereiche anwenden, da alle Bereiche mindestens einmal eine Potenz von 2 ^ n überschreiten. Dies funktioniert nur, wenn ein einzelnes Bit fehlt. Es dauert 2 Durchgänge einer unsortierten Datei, aber jedes Mal wird die einzelne fehlende Nummer gefunden:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

Grundsätzlich wird der Bereich um 0 neu berechnet. Anschließend wird die Anzahl der unsortierten Werte gezählt, die beim Berechnen des Exklusiv-Oder angehängt werden sollen. Dann addiert es 1 zur Anzahl der unsortierten Werte, um den fehlenden Wert zu beheben (zählen Sie den fehlenden). Dann xoring den n-Wert, der jedes Mal um 1 erhöht wird, bis n eine Potenz von 2 ist. Das Ergebnis wird dann wieder auf die ursprüngliche Basis zurückgesetzt. Erledigt.

Hier ist der Algorithmus, den ich in PHP getestet habe (unter Verwendung eines Arrays anstelle einer Datei, aber mit demselben Konzept):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

In einem Array mit einem beliebigen Wertebereich (ich habe getestet, einschließlich Negative) mit einem Wert innerhalb dieses Bereichs, der fehlt, wurde jedes Mal der richtige Wert gefunden.

Ein anderer Ansatz

Warum nicht einfach nach einer Lücke suchen, da wir die externe Sortierung verwenden können? Wenn wir davon ausgehen, dass die Datei vor dem Ausführen dieses Algorithmus sortiert ist:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;
ircmaxell
quelle
3
Das Problem besagt nicht, dass "eine Nummer fehlt", sondern dass eine Nummer gefunden werden muss, die nicht in den 4 Milliarden Nummern in der Datei enthalten ist. Wenn wir 32-Bit-Ganzzahlen annehmen, fehlen möglicherweise etwa 300 Millionen Zahlen in der Datei. Die Wahrscheinlichkeit, dass das xor der vorhandenen Zahlen mit einer fehlenden Zahl übereinstimmt, beträgt nur etwa 7%.
James Waldby - jwpat7
Wenn Sie einen zusammenhängenden, aber fehlenden Bereich haben, der nicht auf Null basiert, fügen Sie anstelle von xor hinzu. sum(0..n) = n*(n+1)/2. Also missing = nmax*(nmax+1)/2 - nmin*(nmin+1)/2 - sum(input[]). (Summenidee aus @ Hammars Antwort.)
Peter Cordes
9

Trickfrage, es sei denn, sie wurde falsch zitiert. Lesen Sie die Datei einfach einmal durch, um die maximale Ganzzahl zu erhalten n, und kehren Sie zurück n+1.

Natürlich benötigen Sie einen Sicherungsplan, falls n+1ein Ganzzahlüberlauf auftritt.

Mark Ransom
quelle
3
Hier ist eine Lösung, die funktioniert ... außer wenn dies nicht der Fall ist. Nützlich! :-)
dty
Sofern es nicht falsch zitiert wurde, war die Frage weder an die Art der Ganzzahl noch an die verwendete Sprache gebunden. Viele moderne Sprachen haben Ganzzahlen, die nur durch den verfügbaren Speicher begrenzt sind. Wenn die größte Ganzzahl in der Datei> 10 MB ist, Pech, Aufgabe für den zweiten Fall unmöglich. Meine Lieblingslösung.
Jürgen Strobel
9

Überprüfen Sie die Größe der Eingabedatei und geben Sie eine beliebige Zahl aus, die zu groß ist, um von einer Datei dieser Größe dargestellt zu werden. Dies mag wie ein billiger Trick erscheinen, aber es ist eine kreative Lösung für ein Interviewproblem, es umgeht das Speicherproblem ordentlich und es ist technisch gesehen O (n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Sollte 10 Bitcount drucken - 1 , was immer größer als 2 Bitcount ist . Technisch gesehen ist die Zahl, die Sie schlagen müssen, 2 Bitcount - (4 * 10 9 - 1) , da Sie wissen, dass die Datei (4 Milliarden - 1) andere Ganzzahlen enthält, und selbst bei perfekter Komprimierung nehmen sie mindestens Platz ein jeweils ein Bit.

Justin Morgan
quelle
Warum nicht einfach Console.Write( 1 << bitcount )statt der Schleife? Wenn die Datei n Bits enthält, ist jede (_n_ + 1) -Bit-Zahl mit einer führenden 1 absolut größer.
Emmet
@Emmet - Dies würde nur einen Ganzzahlüberlauf verursachen, es sei denn, die Datei wäre kleiner als die Größe eines Int (4 Byte in C #). In C ++ können Sie möglicherweise etwas Größeres verwenden, aber C # scheint mit dem <<Operator nur 32-Bit-Ints zuzulassen . In beiden Fällen ist die Dateigröße sehr gering, es sei denn, Sie rollen Ihren eigenen gigantischen Integer-Typ. Demo: rextester.com/BLETJ59067
Justin Morgan
8
  • Der einfachste Ansatz besteht darin, die Mindestanzahl in der Datei zu ermitteln und 1 weniger zurückzugeben. Dies verwendet O (1) -Speicher und O (n) -Zeit für eine Datei mit n Zahlen. Es schlägt jedoch fehl, wenn der Nummernkreis begrenzt ist, was dazu führen kann, dass min-1 keine Nummer ist.

  • Die einfache und unkomplizierte Methode zur Verwendung einer Bitmap wurde bereits erwähnt. Diese Methode verwendet O (n) Zeit und Speicher.

  • Ein 2-Pass-Verfahren mit 2 ^ 16 Zähleimern wurde ebenfalls erwähnt. Es liest 2 * n Ganzzahlen, verwendet also O (n) Zeit und O (1) Speicher, kann jedoch keine Datensätze mit mehr als 2 ^ 16 Zahlen verarbeiten. Es kann jedoch leicht auf (z. B.) 2 ^ 60 64-Bit-Ganzzahlen erweitert werden, indem 4 Durchgänge anstelle von 2 ausgeführt werden, und es kann leicht an die Verwendung von winzigem Speicher angepasst werden, indem nur so viele Fächer verwendet werden, wie in den Speicher passen, und die Anzahl der Durchgänge entsprechend erhöht wird In diesem Fall ist die Laufzeit nicht mehr O (n), sondern O (n * log n).

  • Die bisher von rfrankel und ausführlich von ircmaxell erwähnte Methode zum XOR'en aller Zahlen zusammen beantwortet die in gestellte Frage Stapelüberlauf Nr. 35185 , wie ltn100 hervorhob. Es verwendet O (1) Speicher und O (n) Laufzeit. Wenn wir momentan 32-Bit-Ganzzahlen annehmen, hat XOR eine Wahrscheinlichkeit von 7%, eine eindeutige Zahl zu erzeugen. Begründung: gegeben ~ 4G verschiedene Zahlen XOR'd zusammen, und ca. 300M nicht in der Datei, die Anzahl der gesetzten Bits an jeder Bitposition hat die gleiche Chance, ungerade oder gerade zu sein. Somit haben 2 ^ 32 Zahlen die gleiche Wahrscheinlichkeit, als XOR-Ergebnis aufzutreten, von denen 93% bereits in der Datei sind. Beachten Sie, dass die Erfolgswahrscheinlichkeit der XOR-Methode steigt, wenn die Zahlen in der Datei nicht alle unterschiedlich sind.

James Waldby - jwpat7
quelle
7

Aus irgendeinem Grund dachte ich, sobald ich dieses Problem las, an Diagonalisierung. Ich gehe von beliebig großen ganzen Zahlen aus.

Lesen Sie die erste Nummer. Füllen Sie es mit null Bit nach links, bis Sie 4 Milliarden Bit haben. Wenn das erste (höherwertige) Bit 0 ist, wird 1 ausgegeben; sonst wird 0 ausgegeben. (Sie müssen nicht wirklich das linke Feld auffüllen: Sie geben nur eine 1 aus, wenn die Zahl nicht genügend Bits enthält.) Machen Sie dasselbe mit der zweiten Zahl, außer dass Sie das zweite Bit verwenden. Fahren Sie auf diese Weise mit der Datei fort. Sie geben jeweils eine Bit-Nummer mit 4 Milliarden Bit aus, und diese Nummer stimmt nicht mit der in der Datei überein. Beweis: Es war das gleiche wie die n-te Zahl, dann würden sie sich auf das n-te Bit einigen, aber sie sind nicht konstruktionsbedingt.

Jonathan Amsterdam
quelle
+1 für Kreativität (und die bisher kleinste Worst-Case-Ausgabe für eine Single-Pass-Lösung).
Hmakholm verließ Monica
Es gibt jedoch keine 4 Milliarden Bits zum Diagonalisieren, sondern nur 32. Sie erhalten nur eine 32-Bit-Zahl, die sich von den ersten 32 Zahlen in der Liste unterscheidet.
Brian Gordon
@Henning Es ist kaum ein einziger Durchgang; Sie müssen noch von unär zu binär konvertieren. Bearbeiten: Nun, ich denke, es ist ein Durchgang über die Datei. Keine Ursache.
Brian Gordon
@ Brian, wo ist hier etwas "Unäres"? Die Antwort besteht darin, eine binäre Antwort Bit für Bit zu erstellen, und die Eingabedatei wird nur einmal gelesen, sodass sie in einem Durchgang ausgeführt wird. (Wenn eine Dezimalausgabe erforderlich ist, wird es problematisch. Dann ist es wahrscheinlich besser, eine Dezimalstelle pro drei Eingabenummern zu erstellen und eine 10% ige Erhöhung des Protokolls der Ausgabennummer zu akzeptieren.)
Hmakholm verließ Monica
2
@Henning Das Problem ist für beliebig große Ganzzahlen nicht sinnvoll, da es, wie viele Leute betont haben, trivial ist, nur die größte Zahl zu finden und eine hinzuzufügen oder eine sehr lange Zahl aus der Datei selbst zu erstellen. Diese Diagonalisierungslösung ist besonders ungeeignet, da Sie anstatt auf das idritte Bit zu verzweigen, einfach 4 Milliarden Mal 1 Bit ausgeben und am Ende eine zusätzliche 1 werfen könnten. Ich bin damit einverstanden, beliebig große Ganzzahlen im Algorithmus zu haben, aber ich denke, das Problem besteht darin, eine fehlende 32-Bit-Ganzzahl auszugeben. Anders macht es einfach keinen Sinn.
Brian Gordon
6

Sie können Bit-Flags verwenden, um zu markieren, ob eine Ganzzahl vorhanden ist oder nicht.

Scannen Sie nach dem Durchlaufen der gesamten Datei jedes Bit, um festzustellen, ob die Nummer vorhanden ist oder nicht.

Angenommen, jede Ganzzahl ist 32 Bit, passen sie bequem in 1 GB RAM, wenn die Bit-Kennzeichnung erfolgt.

Shamim Hafiz
quelle
0,5 GB, es sei denn, Sie haben das Byte neu definiert, um 4 Bit zu sein ;-)
dty
2
@dty Ich denke, er meint "bequem", da in der 1 GB viel Platz sein wird.
CorsiKa
6

Entfernen Sie den Leerraum und nicht numerische Zeichen aus der Datei und fügen Sie 1 hinzu. Ihre Datei enthält jetzt eine einzelne Nummer, die nicht in der Originaldatei aufgeführt ist.

Von Reddit von Carbonetc.

Ashley
quelle
Liebe es! Auch wenn es nicht ganz die Antwort ist, nach der er gesucht hat ...: D
Johann du Toit
6

Der Vollständigkeit halber ist hier eine weitere sehr einfache Lösung, deren Ausführung höchstwahrscheinlich sehr lange dauern wird, die jedoch nur sehr wenig Speicher benötigt.

Alle möglichen Ganzzahlen seien der Bereich von int_minbis int_maxund bool isNotInFile(integer)eine Funktion, die true zurückgibt, wenn die Datei keine bestimmte Ganzzahl und false else enthält (indem diese bestimmte Ganzzahl mit jeder Ganzzahl in der Datei verglichen wird).

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
Grad
quelle
Die Frage war genau nach dem Algorithmus für die isNotInFileFunktion. Bitte stellen Sie sicher, dass Sie die Frage verstanden haben, bevor Sie sie beantworten.
Aleks G
2
Nein, die Frage war "Welche Ganzzahl ist nicht in der Datei", nicht "Ist Ganzzahl x in der Datei". Eine Funktion zum Bestimmen der Antwort auf die letztere Frage könnte beispielsweise einfach jede Ganzzahl in der Datei mit der fraglichen Ganzzahl vergleichen und bei einer Übereinstimmung true zurückgeben.
Grad
Ich denke, das ist eine legitime Antwort. Mit Ausnahme von E / A benötigen Sie nur eine Ganzzahl und ein Bool-Flag.
Brian Gordon
@Aleks G - Ich verstehe nicht, warum dies als falsch markiert ist. Wir sind uns alle einig, dass es der langsamste Algorithmus von allen ist :-), aber er funktioniert und benötigt nur 4 Bytes, um die Datei zu lesen. Die ursprüngliche Frage besagt nicht, dass die Datei beispielsweise nur einmal gelesen werden kann.
Simon Mourier
1
@Aleks G - Richtig. Ich habe nie gesagt, dass du das auch gesagt hast. Wir sagen nur, dass IsNotInFile mithilfe einer Schleife in der Datei trivial implementiert werden kann: Open; While Not Eof {Read Integer; Return False, wenn Integer = i; Else Continue;}. Es benötigt nur 4 Bytes Speicher.
Simon Mourier
5

Für die 10-MB-Speicherbeschränkung:

  1. Konvertieren Sie die Zahl in ihre binäre Darstellung.
  2. Erstellen Sie einen Binärbaum mit left = 0 und right = 1.
  3. Fügen Sie jede Zahl mit ihrer Binärdarstellung in den Baum ein.
  4. Wenn bereits eine Nummer eingegeben wurde, wurden die Blätter bereits erstellt.

Wenn Sie fertig sind, nehmen Sie einfach einen Pfad, der zuvor noch nicht erstellt wurde, um die angeforderte Nummer zu erstellen.

4 Milliarden Anzahl = 2 ^ 32, was bedeutet, dass 10 MB möglicherweise nicht ausreichen.

BEARBEITEN

Eine Optimierung ist möglich, wenn zwei Endblätter erstellt wurden und ein gemeinsames übergeordnetes Element haben, können sie entfernt und das übergeordnete Element als keine Lösung gekennzeichnet werden. Dies schneidet Zweige und reduziert den Speicherbedarf.

EDIT II

Es ist auch nicht erforderlich, den Baum vollständig zu bauen. Sie müssen nur tiefe Zweige erstellen, wenn die Zahlen ähnlich sind. Wenn wir auch Zweige schneiden, könnte diese Lösung tatsächlich funktionieren.

Jérôme Verstrynge
quelle
6
... und wie passt das in 10 MB?
Hmakholm verließ Monica
Wie wäre es mit: Begrenzen Sie die Tiefe des BTree auf etwas, das in 10 MB passt; Dies würde bedeuten, dass Sie Ergebnisse in der Menge {falsch positiv | haben würden positiv} und Sie könnten dies durchlaufen und andere Techniken verwenden, um Werte zu finden.
Jonathan Dickinson
5

Ich werde die 1 GB Version beantworten:

Die Frage enthält nicht genügend Informationen, daher werde ich zunächst einige Annahmen treffen:

Die Ganzzahl beträgt 32 Bit mit einem Bereich von -2.147.483.648 bis 2.147.483.647.

Pseudocode:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}
BobTurbo
quelle
4

Solange wir kreative Antworten geben, ist hier eine andere.

Verwenden Sie das externe Sortierprogramm, um die Eingabedatei numerisch zu sortieren. Dies funktioniert für jede Menge Speicher, die Sie möglicherweise haben (bei Bedarf wird Dateispeicher verwendet). Lesen Sie die sortierte Datei durch und geben Sie die erste fehlende Nummer aus.

Rhialto unterstützt Monica
quelle
3

Bit-Eliminierung

Eine Möglichkeit besteht darin, Bits zu eliminieren, dies führt jedoch möglicherweise nicht zu einem Ergebnis (wahrscheinlich nicht). Pseudocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Bitzählungen

Verfolgen Sie die Anzahl der Bits. und verwenden Sie die Bits mit den geringsten Beträgen, um einen Wert zu generieren. Auch dies hat keine Garantie für die Erzeugung eines korrekten Wertes.

Bereichslogik

Verfolgen Sie eine Liste der geordneten Bereiche (sortiert nach Start). Ein Bereich wird durch die Struktur definiert:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Gehen Sie jeden Wert in der Datei durch und versuchen Sie, ihn aus dem aktuellen Bereich zu entfernen. Diese Methode hat keine Speichergarantien, sollte aber ziemlich gut funktionieren.

Jonathan Dickinson
quelle
3

2 128 * 10 18 + 1 (was (2 8 ) 16 * 10 18 + 1 ist) - kann es für heute keine universelle Antwort sein? Dies stellt eine Zahl dar, die nicht in einer 16-EB-Datei gespeichert werden kann. Dies ist die maximale Dateigröße in einem aktuellen Dateisystem.

Michael Sagalovich
quelle
Und wie würden Sie das Ergebnis drucken? Sie können es nicht in eine Datei einfügen, und das Drucken auf dem Bildschirm würde einige Milliarden Jahre dauern. Mit heutigen Computern ist keine Verfügbarkeit wahrscheinlich.
vsz
Es wird nie gesagt, dass wir das Ergebnis irgendwo drucken müssen, sondern es nur "generieren" müssen. es kommt also darauf an, was du mit generieren meinst. Jedenfalls ist meine Antwort nur ein Trick, um zu vermeiden, einen echten Algorithmus
auszuarbeiten
3

Ich denke, dies ist ein gelöstes Problem (siehe oben), aber es gibt einen interessanten Nebenfall, den man beachten sollte, weil er möglicherweise gefragt wird:

Wenn genau 4.294.967.295 (2 ^ 32 - 1) 32-Bit-Ganzzahlen ohne Wiederholungen vorhanden sind und daher nur eine fehlt, gibt es eine einfache Lösung.

Starten Sie eine laufende Summe bei Null und fügen Sie für jede Ganzzahl in der Datei diese Ganzzahl mit 32-Bit-Überlauf hinzu (effektiv runningTotal = (runningTotal + nextInteger)% 4294967296). Wenn Sie fertig sind, fügen Sie 4294967296/2 zur laufenden Summe hinzu, erneut mit 32-Bit-Überlauf. Subtrahieren Sie dies von 4294967296, und das Ergebnis ist die fehlende Ganzzahl.

Das Problem "nur eine fehlende Ganzzahl" kann mit nur einem Lauf und nur 64 Bit RAM für die Daten gelöst werden (32 für die laufende Summe, 32 zum Einlesen der nächsten Ganzzahl).

Folgerung: Die allgemeinere Spezifikation ist extrem einfach anzupassen, wenn es uns nicht darum geht, wie viele Bits das ganzzahlige Ergebnis haben muss. Wir generieren nur eine Ganzzahl, die groß genug ist, dass sie nicht in der angegebenen Datei enthalten sein kann. Auch dies beansprucht absolut minimalen RAM. Siehe den Pseudocode.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}
Syntaera
quelle
@ Nakilon und TheDayTurns haben dies in den Kommentaren zur ursprünglichen Frage
Brian Gordon
3

Wie Ryan es im Grunde gesagt hat, sortiere die Datei und gehe dann die ganzen Zahlen durch und wenn ein Wert dort übersprungen wird, hast du ihn :)

EDIT bei downvoters: die OP erwähnt , dass die Datei sortiert werden, so dies eine gültige Methode.

Ratschenfreak
quelle
Ein entscheidender Teil ist, dass Sie es tun sollten, während Sie gehen, so dass Sie nur einmal lesen müssen. Der Zugriff auf den physischen Speicher ist langsam.
Ryan Amos
@ryan externe Sortierung ist in den meisten Fällen eine Zusammenführungssortierung, so dass Sie bei der letzten Zusammenführung die Überprüfung durchführen können :)
Ratschenfreak
Wenn sich die Daten auf der Festplatte befinden, müssen sie in den Speicher geladen werden. Dies geschieht automatisch durch das Dateisystem. Wenn wir eine Nummer finden müssen (das Problem gibt nichts anderes an), ist das zeilenweise Lesen der sortierten Datei die effizienteste Methode. Es benötigt wenig Speicher und ist nicht langsamer als alles andere - die Datei muss gelesen werden.
Tony Ennis
Wie werden Sie 4 Milliarden Ganzzahlen sortieren, wenn Sie nur 1 GB Speicher haben? Wenn Sie virtuellen Speicher verwenden, dauert es eine lange Zeit, da Speicherblöcke in den physischen Speicher und aus diesem heraus ausgelagert werden.
Klas Lindbäck
4
@klas Merge Sort ist dafür ausgelegt
Ratschenfreak
2

Wenn Sie die 32-Bit-Einschränkung nicht annehmen, geben Sie einfach eine zufällig generierte 64-Bit-Zahl zurück (oder 128-Bit, wenn Sie ein Pessimist sind). Die Wahrscheinlichkeit einer Kollision beträgt 1 in 2^64/(4*10^9) = 4611686018.4(ungefähr 1 von 4 Milliarden). Du hättest die meiste Zeit Recht!

(Scherz ... irgendwie.)

Peter Gibson
quelle
Ich sehe, dass dies bereits vorgeschlagen wurde :) Upvotes für diese Leute
Peter Gibson
Das Geburtstagsparadox macht diese Art von Lösung das Risiko nicht wert, ohne die Datei zu überprüfen, um festzustellen, ob Ihre zufällige Vermutung tatsächlich eine gültige Antwort war. (Geburtstagsparadoxon gilt in diesem Fall nicht, aber das wiederholte Aufrufen dieser Funktion zum Generieren neuer eindeutiger Werte führt zu einer Geburtstagsparadoxon-Situation.)
Peter Cordes
@PeterCordes Zufällig generierte 128-Bit-Zahlen funktionieren genau so - UUIDs erwähnen sogar das Geburtstagsparadoxon bei der Berechnung der Wahrscheinlichkeit einer Kollision auf der Wikipedia- UUID-Seite
Peter Gibson
Variante: Finden Sie das Maximum im Satz und fügen Sie 1 hinzu.
Phil
Ich würde das ursprüngliche Array schnell sortieren (kein zusätzlicher Speicher), dann durch das Array marschieren und die erste übersprungene Ganzzahl melden. Erledigt. Beantwortete die Frage.
Level 42