Wygeneruj liczbę całkowitą, której nie ma wśród czterech miliardów podanych


691

Otrzymałem pytanie do tego wywiadu:

Biorąc pod uwagę plik wejściowy z czterema miliardami liczb całkowitych, zapewnij algorytm do generowania liczby całkowitej, która nie jest zawarta w pliku. Załóżmy, że masz 1 GB pamięci. Kontynuuj, co byś zrobił, gdybyś miał tylko 10 MB pamięci.

Moja analiza:

Rozmiar pliku to 4 × 10 9 × 4 bajtów = 16 GB.

Możemy dokonać zewnętrznego sortowania, co pozwoli nam poznać zakres liczb całkowitych.

Moje pytanie brzmi: jaki jest najlepszy sposób na wykrycie brakującej liczby całkowitej w posortowanych dużych liczbach całkowitych?

Moje zrozumienie (po przeczytaniu wszystkich odpowiedzi):

Zakładając, że mówimy o 32-bitowych liczbach całkowitych, istnieją 2 32 = 4 * 10 9 różnych liczb całkowitych.

Przypadek 1: mamy 1 GB = 1 * 10 9 * 8 bitów = 8 miliardów bitów pamięci.

Rozwiązanie:

Jeśli użyjemy jednego bitu reprezentującego jedną odrębną liczbę całkowitą, to wystarczy. nie potrzebujemy sortować.

Realizacja:

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);
        }
    }
}

Przypadek 2: 10 MB pamięci = 10 * 10 6 * 8 bitów = 80 milionów bitów

Rozwiązanie:

Dla wszystkich możliwych 16-bitowych prefiksów istnieje 2 16 liczb całkowitych = 65536, potrzebujemy 2 16 * 4 * 8 = 2 miliony bitów. Potrzebujemy zbudować 65536 wiader. Dla każdego segmentu potrzebujemy 4 bajtów z wszystkimi możliwościami, ponieważ najgorszym przypadkiem jest to, że wszystkie 4 miliardy liczb całkowitych należą do tego samego segmentu.

  1. Zbuduj licznik każdego segmentu przez pierwsze przejście przez plik.
  2. Zeskanuj wiadra, znajdź pierwszego, który ma mniej niż 65536 trafień.
  3. Twórz nowe segmenty, których wysokie 16-bitowe prefiksy znajdują się w kroku 2 do drugiego przejścia pliku
  4. Zeskanuj wiadra zbudowane w kroku 3, znajdź pierwsze wiadro, które nie ma trafienia.

Kod jest bardzo podobny do powyższego.

Wniosek: Zmniejszamy pamięć poprzez zwiększenie przepustowości plików.


Wyjaśnienie dla osób spóźniających się: Pytanie, jak zadano, nie mówi, że istnieje dokładnie jedna liczba całkowita, która nie jest zawarta w pliku - przynajmniej tak nie interpretuje większość ludzi. Wiele komentarzy W komentarzu wątku o tej odmianie zadania, choć. Niestety komentarz, który wprowadził go do wątku komentarza, został później usunięty przez autora, więc teraz wygląda na to, że osierocone odpowiedzi po prostu źle wszystko zrozumiały. Przepraszam, to bardzo mylące.


32
@trashgod, źle. Dla 4294967295 unikalnych liczb całkowitych pozostanie 1 liczba całkowita. Aby go znaleźć, należy zsumować wszystkie liczby całkowite i odjąć je od wstępnie obliczonego sumowania wszystkich możliwych liczb całkowitych.
Nakilon,

58
Jest to druga „perła” z „Programowania pereł” i sugerowałbym przeczytanie całej dyskusji w książce. Zobacz books.google.com/…
Alok Singhal

8
@Richard 64-bitowy int byłby więcej niż wystarczająco duży.
cftarnas

79
int getMissingNumber(File inputFile) { return 4; }( odniesienie )
John

14
Nie ma znaczenia, że ​​nie można zapisać sumy wszystkich liczb całkowitych od 1 do 2 ^ 32, ponieważ typ liczb całkowitych w językach takich jak C / C ++ ZAWSZE zachowuje właściwości takie jak asocjatywność i komunikatywność. Oznacza to, że chociaż suma nie będzie poprawną odpowiedzią, jeśli obliczysz oczekiwane przekroczenie, rzeczywista suma z przepełnieniem, a następnie odejmie, wynik będzie nadal poprawny (pod warunkiem, że sam się nie przepełni).
thedayturns

Odpowiedzi:


530

Zakładając, że „liczba całkowita” oznacza 32 bity : 10 MB miejsca wystarcza, aby policzyć, ile liczb jest w pliku wejściowym z dowolnym 16-bitowym prefiksem, dla wszystkich możliwych 16-bitowych prefiksów w jednym przejściu plik wejściowy. Co najmniej jeden z wiader zostanie trafiony mniej niż 2 16 razy. Wykonaj drugie przejście, aby dowiedzieć się, która z możliwych liczb w tym segmencie jest już używana.

Jeśli oznacza to więcej niż 32 bity, ale wciąż o ograniczonym rozmiarze : Wykonaj jak wyżej, ignorując wszystkie liczby wejściowe, które przypadają poza (podpisany lub niepodpisany; twój wybór) zakres 32-bitowy.

Jeśli „liczba całkowita” oznacza matematyczną liczbę całkowitą : przeczytaj raz dane wejściowe i śledź największą długość liczby z najdłuższej liczby, jaką kiedykolwiek widziałeś. Kiedy skończysz, wypisz maksimum plus jeden losową liczbę, która ma jeszcze jedną cyfrę. (Jedną z liczb w pliku może być bignum, które dokładnie reprezentuje więcej niż 10 MB, ale jeśli dane wejściowe to plik, to możesz przynajmniej reprezentować długość wszystkiego, co się w nim mieści).


24
Doskonały. Twoja pierwsza odpowiedź wymaga tylko 2 przejść przez plik!
corsiKa

47
Bignum 10 MB? To dość ekstremalne.
Mark Ransom

12
@ Legate, po prostu pomiń zbyt duże liczby i nie rób nic z nimi. Ponieważ i tak nie zamierzasz wyświetlać zbyt dużej liczby, nie musisz śledzić, który z nich widziałeś.
Hmakholm pozostawił Monikę

12
Zaletą rozwiązania 1 jest to, że można zmniejszyć pamięć poprzez zwiększenie liczby przebiegów.
Yousf

11
@ Barry: Powyższe pytanie nie wskazuje, że brakuje dokładnie jednej liczby. Nie mówi też, że liczby w pliku też się nie powtarzają. (Podążanie za faktycznie zadanym pytaniem jest prawdopodobnie dobrym pomysłem w wywiadzie, prawda? ;-))
Christopher Creutzig

197

Algorytmy posiadające informacje statystyczne rozwiązują ten problem przy użyciu mniejszej liczby przejść niż podejścia deterministyczne.

Jeśli dozwolone są bardzo duże liczby całkowite, można wygenerować liczbę, która prawdopodobnie będzie unikalna w czasie O (1). Pseudolosowa 128-bitowa liczba całkowita, taka jak GUID , zderzy się tylko z jedną z czterech istniejących miliardów liczb całkowitych w zestawie w mniej niż jednej na 64 miliardy miliardów przypadków.

Jeśli liczby całkowite są ograniczone do 32 bitów, wówczas można wygenerować liczbę, która prawdopodobnie będzie unikalna w jednym przejściu, używając znacznie mniej niż 10 MB. Szanse na zderzenie pseudolosowej 32-bitowej liczby całkowitej z jedną z 4 miliardów istniejących liczb całkowitych wynoszą około 93% (4e9 / 2 ^ 32). Szanse, że zderzy się 1000 pseudolosowych liczb całkowitych, są mniejsze niż jeden na 12 000 miliardów miliardów (prawdopodobieństwo jednego zderzenia ^ 1000). Więc jeśli program utrzymuje strukturę danych zawierającą 1000 pseudolosowych kandydatów i iteruje znane liczby całkowite, eliminując dopasowania z kandydatów, prawie na pewno znajdzie przynajmniej jedną liczbę całkowitą, której nie ma w pliku.


32
Jestem pewien, że liczby całkowite są ograniczone. Gdyby tak nie było, nawet początkujący programista pomyślałby o algorytmie „przejmij dane, aby znaleźć maksymalną liczbę, i dodaj do niej 1”
Adrian Petrescu

12
Dosłownie odgadnięcie losowego wyniku prawdopodobnie nie zapewni ci wielu punktów w wywiadzie
Brian Gordon

6
@Adrian, twoje rozwiązanie wydaje się oczywiste (i to było dla mnie, użyłem go we własnej odpowiedzi), ale nie jest to oczywiste dla wszystkich. To dobry test, aby zobaczyć, czy potrafisz dostrzec oczywiste rozwiązania, czy też nadmiernie skomplikujesz wszystko, czego dotkniesz.
Mark Ransom

19
@Brian: Myślę, że to rozwiązanie jest zarówno pomysłowe, jak i praktyczne. Dałbym za to wiele uznania dla tej odpowiedzi.
Richard H

6
ach tutaj leży granica między inżynierami i naukowcami. Świetna odpowiedź Ben!
TrojanName

142

Szczegółowa dyskusja na ten temat została omówiona w kolumnie Jona Bentleya „Kolumna 1. Cracking the Oyster” Perły programistyczne Addison-Wesley str. 3-10

Bentley omawia kilka podejść, w tym sortowanie zewnętrzne, sortowanie korespondencji seryjnej przy użyciu kilku plików zewnętrznych itp., Ale najlepsza metoda sugerowana przez Bentleya to algorytm jednoprzebiegowy wykorzystujący pola bitowe , które humorystycznie nazywa „Wonder Sort” :) Podchodząc do problemu, 4 miliardy liczby mogą być reprezentowane w:

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

Kod implementujący zestaw bitów jest prosty: (wzięty ze strony rozwiązań )

#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)); }

Algorytm Bentleya wykonuje pojedyncze przejście przez plik, setzaznaczając odpowiedni bit w tablicy, a następnie sprawdza tę tablicę za pomocą testmakra powyżej, aby znaleźć brakującą liczbę.

Jeśli dostępna pamięć jest mniejsza niż 0,466 GB, Bentley sugeruje algorytm k-pass, który dzieli dane wejściowe na zakresy w zależności od dostępnej pamięci. Aby wziąć bardzo prosty przykład, jeśli dostępny był tylko 1 bajt (tj. Pamięć do obsługi 8 liczb), a zakres wynosił od 0 do 31, dzielimy to na zakres od 0 do 7, 8-15, 16-22 i tak dalej i obsługiwać ten zakres w każdym z 32/8 = 4przebiegów.

HTH.


12
Nie znam tej książki, ale nie ma powodu, by nazywać ją „Cudowne sortowanie”, ponieważ jest to po prostu segregator z 1-bitowym licznikiem.
flolo

3
Chociaż bardziej przenośny, ten kod zostanie unicestwiony przez kod napisany w celu użycia instrukcji wektorowych obsługiwanych sprzętowo . Myślę, że gcc może w niektórych przypadkach automatycznie konwertować kod na operacje wektorowe.
Brian Gordon,

3
@brian Nie sądzę, że Jon Bentley pozwolił na takie rzeczy w swojej książce na temat algorytmów.
David Heffernan

8
@BrianGordon, czas spędzony w pamięci RAM będzie nieznaczny w porównaniu do czasu spędzonego na czytaniu pliku. Zapomnij o optymalizacji.
Ian

1
@BrianGordon: A może mówiłeś o pętli na końcu, aby znaleźć pierwszy niezbity bit? Tak, wektory przyspieszą to, ale zapętlają pole bitowe z 64-bitowymi liczbami całkowitymi, szukając takiego, != -1który nadal będzie nasycał przepustowość pamięci działającą na jednym rdzeniu (jest to SWD z rejestru SIMD, z bitami jako elementami). (Dla najnowszych projektów Intel / AMD). Musisz tylko dowiedzieć się, który bit jest rozbrojony po znalezieniu zawierającej go 64-bitowej lokalizacji. (I do tego można not / lzcnt.) Należy uczciwie stwierdzić, że zapętlenie w teście pojedynczym może nie zostać odpowiednio zoptymalizowane.
Peter Cordes

120

Ponieważ problem nie określa, że ​​musimy znaleźć najmniejszą możliwą liczbę, której nie ma w pliku, moglibyśmy po prostu wygenerować liczbę dłuższą niż sam plik wejściowy. :)


6
Chyba że największa liczba w pliku to max int, to po prostu przepełnisz się
KBusc

Jaki byłby rozmiar tego pliku w programie z prawdziwego świata, który może potrzebować wygenerować nową liczbę całkowitą i dołączyć ją do pliku „używanych liczb całkowitych” 100 razy?
Michael

2
Myślałem o tym. Zakładając, że intto 32bity, po prostu wyjście 2^64-1. Gotowy.
imallett

1
Jeśli jest to jedna int na linię tr -d '\n' < nums.txt > new_num.txt:: D
Shon

56

W przypadku wariantu 1 GB pamięci RAM można użyć nieco wektora. Musisz przydzielić 4 miliardy bitów == 500 MB bajtów. Dla każdej liczby odczytywanej z wejścia ustaw odpowiedni bit na „1”. Gdy skończysz, iteruj po bitach, znajdź pierwszy, który wciąż ma „0”. Jego indeks jest odpowiedzią.


4
Zakres liczb na wejściu nie jest określony. Jak działa ten algorytm, jeśli dane wejściowe składają się ze wszystkich liczb parzystych od 8 do 16 miliardów?
Mark Ransom

27
@ Mark, po prostu zignoruj ​​dane wejściowe, które są poza zakresem 0..2 ^ 32. I tak nie zamierzasz wypisywać żadnego z nich, więc nie musisz pamiętać, którego z nich unikać.
hmakholm opuścił Monikę

@ Zaznacz dowolny algorytm, którego używasz do określenia, w jaki sposób 32-bitowy ciąg odwzorowany na liczbę rzeczywistą zależy od Ciebie. Proces jest nadal taki sam. Jedyną różnicą jest to, jak wydrukujesz go na ekranie jako liczbę rzeczywistą.
corsiKa

4
Zamiast iterować się, możesz użyć bitSet.nextClearBit(0): download.oracle.com/javase/6/docs/api/java/util/…
starblue

3
Warto wspomnieć, że niezależnie od zakresu liczb całkowitych, co najmniej jeden bit ma zagwarantowane zero na końcu przebiegu. Wynika to z zasady szuflady.
Rafał Dowgird,

46

Jeśli są to 32-bitowe liczby całkowite (prawdopodobnie z wyboru ~ 4 miliardów liczb blisko 2 32 ), twoja lista 4 miliardów liczb zajmie najwyżej 93% możliwych liczb całkowitych (4 * 10 9 / (2 32 ) ). Więc jeśli utworzysz tablicę bitów składającą się z 2 32 bitów z każdym bitem zainicjowanym na zero (co zajmie 2 29 bajtów ~ 500 MB pamięci RAM; pamiętaj bajt = 2 3 bity = 8 bitów), przeczytaj listę liczb całkowitych i dla każdego int ustaw odpowiedni element tablicy bitów od 0 do 1; a następnie przeczytaj swoją tablicę bitów i zwróć pierwszy bit, który wciąż wynosi 0.

W przypadku, gdy masz mniej pamięci RAM (~ 10 MB), to rozwiązanie należy nieco zmodyfikować. 10 MB ~ 83886080 bitów wciąż wystarcza, aby wykonać tablicę bitów dla wszystkich liczb od 0 do 83886079. Abyś mógł przeczytać swoją listę liczb wewnętrznych; i zapisuj tylko liczby z zakresu od 0 do 83886079 w tablicy bitów. Jeśli liczby są losowo rozmieszczone; z ogromnym prawdopodobieństwem (różni się o 100% o około 10 -2592069 ) znajdziesz brakującą liczbę całkowitą ). W rzeczywistości, jeśli wybierzesz tylko liczby od 1 do 2048 (tylko 256 bajtów pamięci RAM), nadal znajdziesz brakującą liczbę w przeważającej części (99,999999999999999999999999999999999999999999999999999999999999999995%).

Ale powiedzmy zamiast mieć około 4 miliardów liczb; miałeś coś w rodzaju 2 32-1 liczb i mniej niż 10 MB pamięci RAM; więc każdy mały zakres liczb całkowitych ma jedynie niewielką możliwość nieumieszczania liczby.

Jeśli masz gwarancję, że każda liczba int na liście jest unikalna, możesz zsumować liczby i odjąć sumę z jednym brakiem do pełnej sumy (½) (2 32 ) (2 32 - 1) = 9223372034707292160, aby znaleźć brakującą liczbę int . Jednak jeśli int wystąpił dwukrotnie, ta metoda zawiedzie.

Zawsze możesz jednak dzielić i podbijać. Naiwną metodą byłoby odczytanie tablicy i policzenie liczb znajdujących się w pierwszej połowie (od 0 do 2 31 -1) i drugiej połowie (2 31 , 2 32 ). Następnie wybierz zakres z mniejszą liczbą liczb i powtórz dzieląc ten zakres na pół. (Załóżmy, że w (2 31 , 2 32 ) było mniej dwóch liczb , to następne wyszukiwanie policzy liczby w zakresie (2 31 , 3 * 2 30 -1), (3 * 2 30 , 2 32 ). powtarzając, dopóki nie znajdziesz zakresu z zerowymi liczbami i nie uzyskasz odpowiedzi. Powinieneś wziąć O (lg N) ~ 32 odczytów przez tablicę.

Ta metoda była nieefektywna. Używamy tylko dwóch liczb całkowitych na każdym kroku (lub około 8 bajtów pamięci RAM z 4 bajtową liczbą całkowitą (32-bitową)). Lepszym sposobem byłoby podzielenie na sqrt (2 32 ) = 2 16 = 65536 przedziałów, każdy z 65536 liczbami w bin. Każdy pojemnik wymaga 4 bajtów do przechowywania swojej liczby, więc potrzebujesz 2 18 bajtów = 256 kB. Tak więc bin 0 to (0 do 65535 = 2 16 -1), bin 1 to (2 16 = 65536 do 2 * 2 16 -1 = 131071), bin 2 to (2 * 2 16 = 131072 do 3 * 2 16 - 1 = 196607). W pythonie masz coś takiego:

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)

Przeczytaj listę ~ 4 miliardów liczb całkowitych; i policz ile ints przypada na każdy z 2 16 pojemników i znajdź niekompletny_bin, który nie ma wszystkich 65536 liczb. Następnie ponownie przeczytasz listę 4 miliardów liczb całkowitych; ale tym razem zauważ tylko, gdy liczby całkowite są w tym zakresie; przewracając trochę, gdy je znajdziesz.

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

3
Taka niesamowita odpowiedź. To faktycznie działałoby; i ma gwarantowane wyniki.
Jonathan Dickinson

@dr jimbob, co, jeśli w pojemniku jest tylko jedna liczba, a ten pojedynczy numer ma 65535 duplikatów? Jeśli tak, kosz nadal będzie liczył 65536, ale wszystkie liczby 65536 są takie same.
Alcott,

@Alcott - Zakładam, że masz 2 ^ 32-1 (lub mniej) liczb, więc zgodnie z zasadą szuflady masz gwarancję, że masz jeden pojemnik z mniej niż 65536 liczbami, aby sprawdzić bardziej szczegółowo. Staramy się znaleźć tylko jedną brakującą liczbę całkowitą, a nie wszystkie. Jeśli miałeś 2 ^ 32 lub więcej liczb, nie możesz zagwarantować brakującej liczby całkowitej i nie będziesz mógł skorzystać z tej metody (lub mieć gwarancji od samego początku, że brakuje liczby całkowitej). Najlepszym rozwiązaniem byłaby wtedy brutalna siła (np. Przeczytanie tablicy 32 razy; sprawdzenie pierwszych 65536 #s za pierwszym razem; zatrzymanie się po znalezieniu odpowiedzi).
dr jimbob

Sprytna metoda Upper-16 / Lower-16 została opublikowana wcześniej przez Henninga: stackoverflow.com/a/7153822/224132 . Podobał mi się pomysł dodania ich do unikalnego zestawu liczb całkowitych, w których brakuje dokładnie jednego elementu.
Peter Cordes

3
@PeterCordes - Tak, rozwiązanie Henninga wyprzedza moje, ale myślę, że moja odpowiedź jest nadal przydatna (bardziej szczegółowo pracując nad kilkoma rzeczami). To powiedziawszy, Jon Bentley w swojej książce Programming Pearls zasugerował opcję wieloprzebiegową dla tego problemu (patrz odpowiedź Vine'tha) na długo przed pojawieniem się przepełnienia stosu (nie że twierdzę, że któreś z nas świadomie ukradło stamtąd lub że Bentley był pierwszym, który przeanalizuj ten problem - jest to dość naturalne rozwiązanie do opracowania). Dwa przejścia wydają się najbardziej naturalne, gdy ograniczenie polega na tym, że nie masz już wystarczającej ilości pamięci dla rozwiązania 1 przejścia z gigantyczną tablicą bitów.
dr jimbob

37

Dlaczego to takie skomplikowane? Pytasz o liczbę całkowitą, której nie ma w pliku?

Zgodnie z podanymi regułami jedyną rzeczą, którą musisz przechowywać, jest największa liczba napotkana do tej pory w pliku. Po odczytaniu całego pliku zwróć liczbę o 1 większą od tego.

Nie ma ryzyka uderzenia w maksimum lub cokolwiek innego, ponieważ zgodnie z regułami nie ma ograniczeń co do wielkości liczby całkowitej lub liczby zwracanej przez algorytm.


4

13
Reguły nie określają, że jest to wersja 32-bitowa lub 64-bitowa, ani nic, więc zgodnie z określonymi regułami nie ma maksymalnej liczby int. Liczba całkowita nie jest terminem komputerowym, jest to termin matematyczny identyfikujący dodatnie lub ujemne liczby całkowite.
Pete,

To prawda, ale nie można zakładać, że jest to liczba 64-bitowa lub że ktoś nie zakradłby się do maksymalnej liczby int tylko po to, by pomylić takie algorytmy.
PearsonArtPhoto

24
Całe pojęcie „max int” jest niepoprawne w kontekście, jeśli nie określono języka programowania. np. spójrz na definicję długiej liczby całkowitej w Pythonie. To jest nieograniczone. Nie ma dachu. Zawsze możesz dodać jeden. Zakładasz, że jest on implementowany w języku, który ma maksymalną dozwoloną wartość dla liczby całkowitej.
Pete,

32

Można to rozwiązać na bardzo małej przestrzeni za pomocą wariantu wyszukiwania binarnego.

  1. Zacznij od dozwolonego zakresu liczb, 0do 4294967295.

  2. Oblicz punkt środkowy.

  3. Zapętlaj plik, licząc, ile liczb było równych, mniejszych lub wyższych od wartości punktu środkowego.

  4. Jeśli żadna liczba nie była równa, gotowe. Numer punktu środkowego jest odpowiedzią.

  5. W przeciwnym razie wybierz zakres, który miał najmniej liczb, i powtórz od kroku 2 z tym nowym zakresem.

Będzie to wymagało do 32 liniowych skanów przez plik, ale zajmie tylko kilka bajtów pamięci do przechowywania zakresu i zliczeń.

Jest to w zasadzie to samo co rozwiązanie Henninga , z tym wyjątkiem, że używa dwóch pojemników zamiast 16k.


2
Od tego zacząłem, zanim zacząłem optymalizować dla podanych parametrów.
Hmakholm pozostawił Monikę

@ Henning: Cool. To dobry przykład algorytmu, w którym łatwo jest dostosować kompromis czasoprzestrzenny.
hammar

@hammar, ale co jeśli te liczby pojawiają się więcej niż jeden raz?
Alcott,

@Alcott: wtedy algorytm wybierze gęstszy pojemnik zamiast pojemnika sparser, ale zgodnie z zasadą szufladki nigdy nie może wybrać całkowicie pełnego pojemnika. (Mniejsza z tych dwóch liczb będzie zawsze mniejsza niż zakres bin.)
Peter Cordes

27

EDYCJA Ok, nie zostało to do końca przemyślane, ponieważ zakłada, że ​​liczby całkowite w pliku są zgodne z pewnym rozkładem statycznym. Najwyraźniej nie muszą, ale nawet wtedy należy spróbować:


Istnieje ≈4,3 miliarda 32-bitowych liczb całkowitych. Nie wiemy, jak są one dystrybuowane w pliku, ale najgorszym przypadkiem jest ten, który ma najwyższą entropię Shannona: równy rozkład. W takim przypadku prawdopodobieństwo wystąpienia jednej liczby całkowitej w pliku jest następujące

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

Im niższa entropia Shannona, tym większe prawdopodobieństwo, że dostaje się ono średnio, ale nawet w tym najgorszym przypadku mamy szansę 90% na znalezienie nie powtarzającej się liczby po 5 zgadnięciach z losowymi liczbami całkowitymi. Po prostu twórz takie liczby za pomocą generatora pseudolosowego, przechowuj je na liście. Następnie przeczytaj int po int i porównaj go ze wszystkimi swoimi domysłami. W przypadku dopasowania usuń ten wpis z listy. Po przejrzeniu całego pliku istnieje szansa, że ​​pozostanie więcej niż jeden przypuszczenie. Użyj dowolnego z nich. W rzadkim (10% nawet w najgorszym przypadku) przypadku, w którym nie ma wątpliwości, zdobądź nowy zestaw losowych liczb całkowitych, być może tym razem więcej (10-> 99%).

Zużycie pamięci: kilkadziesiąt bajtów, złożoność: O (n), koszty ogólne: nieuniknione, ponieważ większość czasu zostanie poświęcona na nieunikniony dostęp do dysku twardego, a nie na porównywanie int.


Najgorszym przypadkiem, w którym nie zakładamy rozkładu statycznego, jest to, że każda liczba całkowita występuje maks. jeden raz, ponieważ wtedy tylko 1 - 4000000000 / 2³² ≈ 6% wszystkich liczb całkowitych nie występuje w pliku. Potrzebujesz więcej domysłów, ale wciąż nie będzie to kosztować szkodliwych ilości pamięci.


5
Cieszę się, że ktoś jeszcze o tym pomyślał, ale dlaczego jest tu na dole? Jest to algo 1-przebiegowy… 10 MB wystarcza na 2,5 mln zgadnięć, a 93% ^ 2,5 mln ≈ 10 ^ -79000 to naprawdę znikoma szansa na konieczność drugiego skanowania. Ze względu na narzut związany z wyszukiwaniem binarnym jest szybszy, jeśli użyjesz mniejszej liczby domysłów! Jest to optymalne zarówno pod względem czasu, jak i przestrzeni.
Potatoswatter

1
@Patatoswatter: dobrze wspominałeś o wyszukiwaniu binarnym. Prawdopodobnie nie jest to warte narzutu, gdy używa się tylko 5 domysłów, ale na pewno jest to 10 lub więcej. Możesz nawet wykonać 2 zgadnięcia, ale powinieneś je zapisać w zestawie skrótów, aby uzyskać O (1) do wyszukiwania.
leftaroundabout

1
@Potatoswatter Równoważna odpowiedź Bena Haleya znajduje się u góry
Brian Gordon

1
Podobało mi się to podejście, ale sugerowałbym ulepszenie oszczędzania pamięci: jeśli ktoś ma N bitów pamięci indeksowanej oraz trochę stałej pamięci, zdefiniuj konfigurowalną odwracalną 32-bitową funkcję szyfrowania (permutację), wybierz dowolną permutację i wyczyść wszystko indeksowane bity. Następnie przeczytaj każdą liczbę z pliku, wymieszaj ją, a jeśli wynik jest mniejszy niż N, ustaw odpowiedni bit. Jeśli jakiś bit nie jest ustawiony na końcu pliku, odwróć funkcję szyfrowania w jego indeksie. Dzięki 64 KB pamięci można skutecznie przetestować ponad 512 000 numerów pod kątem dostępności w jednym przejściu.
supercat

2
Oczywiście przy tym algorytmie najgorszym przypadkiem jest taki, w którym liczby zostały utworzone przez ten sam generator liczb losowych, którego używasz. Zakładając, że możesz zagwarantować, że tak nie jest, najlepszą taktyką jest użycie liniowego kongruencjalnego generatora liczb losowych do wygenerowania listy, dzięki czemu przejdziesz przez przestrzeń liczbową w sposób pseudolosowy. Oznacza to, że jeśli w jakiś sposób zawiedziesz, możesz kontynuować generowanie liczb, dopóki nie pokryjesz całego zakresu liczb całkowitych (lub znajdziesz przerwę), bez powielania wysiłku.
Dewi Morgan

25

Jeśli brakuje jednej liczby całkowitej z zakresu [0, 2 ^ x - 1], po prostu xor je wszystkie razem. Na przykład:

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

(Wiem, że to nie odpowiada na pytanie dokładnie , ale jest to dobra odpowiedź na bardzo podobne pytanie).


1
Tak, łatwo jest udowodnić [ ], że działa, gdy brakuje jednej liczby całkowitej, ale często zawodzi, jeśli brakuje więcej niż jednej. Na przykład 0 ^ 1 ^ 3 ^ 4 ^ 6 ^ 7wynosi 0. [ Zapis 2 x dla 2 do potęgi x, a a ^ b dla xor b, xor wszystkich k <2 x wynosi zero - k ^ ~ k = (2 ^ x) - 1 dla k <2 ^ (x-1) i k ^ ~ k ^ j ^ ~ j = 0, gdy j = k + 2 ** (x-2) - więc xor wszystkich liczb oprócz jednej jest wartością brakującego]
James Waldby - jwpat7

2
Jak wspomniałem w komentarzu do odpowiedzi ircmaxell: Problem nie mówi „brakuje jednej liczby”, mówi o znalezieniu liczby nieuwzględnionej w 4 miliardach liczb w pliku. Jeśli przyjmiemy 32-bitowe liczby całkowite, w pliku może brakować około 300 milionów liczb. Prawdopodobieństwo, że xor obecnych liczb pasuje do brakującej liczby, wynosi tylko około 7%.
James Waldby - jwpat7

Oto odpowiedź, o której myślałem, kiedy początkowo czytałem pytanie, ale po bliższym przyjrzeniu się myślę, że pytanie jest bardziej niejednoznaczne. Do Twojej wiadomości, oto pytanie, o którym myślałem: stackoverflow.com/questions/35185/...
Lee Netherton

18

Mogą chcieć sprawdzić, czy słyszałeś o probabilistycznym filtrze Blooma, który może bardzo skutecznie określić absolutnie, czy wartość nie jest częścią dużego zbioru, (ale może z dużym prawdopodobieństwem ustalić, że jest członkiem zbioru).


4
Po ustawieniu prawdopodobnie ponad 90% możliwych wartości filtr Bloom prawdopodobnie musiałby zdegenerować się na polu bitowym, z którego korzysta już wiele odpowiedzi. W przeciwnym razie skończysz z bezużytecznym całkowicie wypełnionym łańcuchem bitów.
Christopher Creutzig

@Christopher Rozumiem filtry Blooma, że ​​nie dostajesz wypełnionego bitrrayu, dopóki nie osiągniesz 100%
Paul

... inaczej otrzymalibyście fałszywe negatywy.
Paul

@Paul wypełniona tablica bitów daje fałszywe alarmy, które są dozwolone. W takim przypadku filtr Bloom najprawdopodobniej zdegeneruje się w przypadku, gdy rozwiązanie, które byłoby ujemne, zwraca fałszywie dodatni.
ataylor

1
@Paul: Możesz otrzymać wypełnioną tablicę bitów, gdy tylko liczba funkcji skrótu pomnożona przez liczbę wpisów jest tak duża, jak długość twojego pola. Oczywiście byłby to wyjątkowy przypadek, ale prawdopodobieństwo wzrośnie dość szybko.
Christopher Creutzig

17

W oparciu o obecne sformułowanie w pierwotnym pytaniu najprostszym rozwiązaniem jest:

Znajdź maksymalną wartość w pliku, a następnie dodaj do niej 1.


5
Co jeśli MAXINT jest zawarty w pliku?
Petr Peller

@Petr Peller: Biblioteka BIGINT zasadniczo usunęłaby ograniczenia dotyczące wielkości całkowitych.
oosterwal

2
@ oosterwal, jeśli ta odpowiedź była dozwolona, ​​to nawet nie musisz czytać pliku - po prostu wydrukuj jak największą liczbę.
Nakilon

1
@ oosterwal, jeśli twoja losowa ogromna liczba była największą możliwą do wydrukowania i znajdowała się w pliku, to zadanie nie mogło zostać rozwiązane.
Nakilon

3
@Nakilon: +1 Twój punkt jest zajęty. Jest to mniej więcej odpowiednik obliczenia całkowitej liczby cyfr w pliku i wydrukowania liczby z taką liczbą cyfr.
oosterwal

14

Użyj a BitSet. 4 miliardy liczb całkowitych (przy założeniu do 2 ^ 32 liczb całkowitych) spakowanych do BitSet po 8 na bajt to 2 ^ 32/2 ^ 3 = 2 ^ 29 = około 0,5 Gb.

Aby dodać nieco więcej szczegółów - za każdym razem, gdy czytasz cyfrę, ustaw odpowiedni bit w BitSet. Następnie przełóż BitSet, aby znaleźć pierwszy numer, który nie jest obecny. W rzeczywistości możesz to zrobić równie skutecznie, wielokrotnie wybierając losową liczbę i testując, czy jest ona obecna.

Właściwie BitSet.nextClearBit (0) powie ci pierwszy nie ustawiony bit.

Patrząc na BitSet API, wydaje się, że obsługuje tylko 0..MAX_INT, więc możesz potrzebować 2 BitSetów - jeden dla liczb + i jeden dla numerów - ale wymagania dotyczące pamięci się nie zmieniają.


1
Lub jeśli nie chcesz użyć BitSet... wypróbuj tablicę bitów. Robi to samo;)
jcolebrand

12

Jeśli nie ma limitu rozmiaru, najszybszym sposobem jest pobranie długości pliku i wygenerowanie długości pliku + 1 liczby losowych cyfr (lub tylko „11111 ...”). Zaleta: nie musisz nawet czytać pliku i możesz zminimalizować zużycie pamięci prawie do zera. Wada: wydrukujesz miliardy cyfr.

Gdyby jednak jedynym czynnikiem było zminimalizowanie zużycia pamięci i nic innego nie jest ważne, byłoby to optymalne rozwiązanie. Może nawet dać ci nagrodę za „najgorsze nadużycie zasad”.


11

Jeśli założymy, że zakres liczb zawsze będzie wynosił 2 ^ n (równa potęga 2), wówczas wyłączność - lub zadziała (jak pokazano na innym plakacie). O ile to udowodnimy:

Teoria

Biorąc pod uwagę dowolny zakres liczb całkowitych oparty na 0, który ma 2^n brakuje elementów z jednym elementem, możesz znaleźć ten brakujący element, po prostu łącząc znane wartości razem, aby uzyskać brakującą liczbę.

Dowód

Spójrzmy na n = 2. Dla n = 2 możemy przedstawić 4 unikalne liczby całkowite: 0, 1, 2, 3. Mają one następujący wzór:

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

Teraz, jeśli spojrzymy, każdy bit jest ustawiany dokładnie dwa razy. Dlatego, ponieważ jest on ustawiany parzystą liczbę razy, a liczba wyłączna - lub z liczb da 0. 0. Jeśli brakuje jednej liczby, wartość wyłączna - lub da liczbę, która w przypadku wykluczenia z brakującą liczbą spowoduje 0. W związku z tym brakująca liczba i wynikowa liczba rudy wyłącznej są dokładnie takie same. Jeśli usuniemy 2, powstanie xor10 (lub 2).

Teraz spójrzmy na n + 1. Nazwijmy, ile razy każdy bit jest ustawiony n, xi ile razy każdy bit jest ustawiony n+1 y. Wartość ybędzie równa, y = x * 2ponieważ istnieją xelementy z n+1bitem ustawionym na 0, i xelementy z n+1bitem ustawionym na 1. A ponieważ 2xzawsze będzie parzysty, n+1zawsze będzie ustawiony bit na parzystą liczbę razy.

Dlatego, ponieważ n=2działa i n+1działa, metoda xor będzie działać dla wszystkich wartości n>=2.

Algorytm dla zakresów opartych na 0

To jest dość proste. Wykorzystuje 2 * n bitów pamięci, więc dla dowolnego zakresu <= 32, będą działać 2 32-bitowe liczby całkowite (ignorując pamięć zajętą ​​przez deskryptor pliku). I to robi pojedyncze przejście pliku.

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

Algorytm dla zakresów opartych na arbitrażu

Ten algorytm będzie działał dla zakresów od dowolnej liczby początkowej do dowolnej liczby końcowej, pod warunkiem, że całkowity zakres jest równy 2 ^ n ... Zasadniczo ponownie opiera zakres, aby mieć minimum na 0. Ale wymaga 2 przebiegów przez plik (pierwszy pobiera minimum, drugi oblicza brakującą liczbę całkowitą).

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;

Zakresy arbitralne

Możemy zastosować tę zmodyfikowaną metodę do zbioru dowolnych zakresów, ponieważ wszystkie zakresy przekroczą potęgę 2 ^ n przynajmniej raz. Działa to tylko wtedy, gdy brakuje jednego bitu. Zajmuje 2 przebiegi nieposortowanego pliku, ale za każdym razem znajdzie brakujący numer:

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;

Zasadniczo ponownie opiera zakres około 0. Następnie zlicza liczbę nieposortowanych wartości, które mają zostać dołączone, obliczając wartość wyłączności lub. Następnie dodaje 1 do liczby nieposortowanych wartości, aby zająć się brakującą wartością (policzyć tę brakującą). Następnie trzymaj xoring wartość n, zwiększaną o 1 za każdym razem, aż n będzie potęgą 2. Wynik jest następnie ponownie oparty na pierwotnej podstawie. Gotowy.

Oto algorytm, który przetestowałem w PHP (używając tablicy zamiast pliku, ale tej samej koncepcji):

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;
}

Podawana w tablicy z dowolnym zakresem wartości (testowałem łącznie z negatywami) z jedną z tego brakującego zakresu, za każdym razem znajdowała prawidłową wartość.

Inne podejście

Ponieważ możemy korzystać z zewnętrznego sortowania, dlaczego nie po prostu sprawdzić lukę? Jeśli założymy, że plik jest sortowany przed uruchomieniem tego algorytmu:

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;

3
Problem nie mówi „brakuje jednej liczby”, mówi o znalezieniu liczby nieuwzględnionej w 4 miliardach liczb w pliku. Jeśli przyjmiemy 32-bitowe liczby całkowite, w pliku może brakować około 300 milionów liczb. Prawdopodobieństwo, że xor obecnych liczb pasuje do brakującej liczby, wynosi tylko około 7%.
James Waldby - jwpat7

Jeśli masz ciągły, ale brakuje jednego zakresu, który nie jest zerowy, dodaj zamiast xor. sum(0..n) = n*(n+1)/2. Tak missing = nmax*(nmax+1)/2 - nmin*(nmin+1)/2 - sum(input[]). (pomysł sumy z odpowiedzi @ hammar.)
Peter Cordes

9

Podchwytliwe pytanie, chyba że zostało źle podane. Wystarczy raz przeczytać plik, aby uzyskać maksymalną liczbę całkowitą ni wrócić n+1.

Oczywiście na wszelki wypadek potrzebujesz planu tworzenia kopii zapasowych n+1 przepełnienia liczby całkowitej.


3
Oto rozwiązanie, które działa ... chyba że nie. Przydatny! :-)
dty

O ile nie zostało to źle cytowane, pytanie nie nałożyło ograniczenia na rodzaj liczby całkowitej, ani nawet na używany język. Wiele współczesnych języków ma liczby całkowite ograniczone tylko dostępną pamięcią. Jeśli największa liczba całkowita w pliku wynosi> 10 MB, pech, zadanie niemożliwe w drugim przypadku. Moje ulubione rozwiązanie.
Jürgen Strobel

9

Sprawdź rozmiar pliku wejściowego, a następnie wypisz dowolną liczbę, która jest zbyt duża, aby mogła być reprezentowana przez plik o tym rozmiarze. To może wydawać się tanią sztuczką, ale jest kreatywnym rozwiązaniem problemu z wywiadem, starannie omija problem z pamięcią i technicznie jest 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);
    }
}

Powinien wypisać 10 bitcount - 1 , która zawsze będzie większa niż 2 bitcount . Technicznie liczba, którą musisz pokonać, to 2 bity - (4 * 10 9 - 1) , ponieważ wiesz, że w pliku są (4 miliardy - 1) inne liczby całkowite, a nawet przy doskonałej kompresji zajmą co najmniej po jednym kawałku.


Dlaczego nie Console.Write( 1 << bitcount )zamiast pętli? Jeśli w pliku jest n bitów, to każda (_n_ + 1) liczba bitów z wiodącą 1 jest absolutnie gwarantowana, że ​​jest większa.
Emmet,

@Emmet - To spowodowałoby przepełnienie liczb całkowitych, chyba że plik byłby mniejszy niż rozmiar liczby całkowitej (4 bajty w języku C #). C ++ może pozwolić ci na użycie czegoś większego, ale wydaje się, że C # nie pozwala na nic poza 32-bitowymi intami z <<operatorem. Tak czy inaczej, chyba że rzucisz własną gigantyczną liczbą całkowitą, będzie to bardzo mały rozmiar pliku. Demo: rextester.com/BLETJ59067
Justin Morgan

8
  • Najprostszym podejściem jest znalezienie minimalnej liczby w pliku i zwrócenie 1 mniejszej. Wykorzystuje to pamięć O (1) i czas O (n) dla pliku o liczbie n. Jednak nie powiedzie się, jeśli zakres liczb jest ograniczony, co może sprawić, że min-1 nie będzie liczbą.

  • Wspomniano już o prostej i bezpośredniej metodzie użycia mapy bitowej. Ta metoda wykorzystuje O (n) czas i pamięć.

  • Wspomniano także o metodzie 2-przebiegowej z liczeniem 2 ^ 16. Odczytuje 2 * n liczb całkowitych, więc używa czasu O (n) i pamięci O (1), ale nie może obsługiwać zestawów danych zawierających więcej niż 2 ^ 16 liczb. Można go jednak łatwo rozszerzyć na (np.) 2 ^ 60 64-bitowych liczb całkowitych, uruchamiając 4 przebiegi zamiast 2, i łatwo przystosować do korzystania z małej pamięci, używając tylko tyle przedziałów, ile mieści się w pamięci i odpowiednio zwiększając liczbę przebiegów w który czas wykonania przypadku nie jest już O (n), ale zamiast tego O (n * log n).

  • Metoda XOR'owania wszystkich liczb razem, wspomniana do tej pory przez rfrankel i w końcu przez ircmaxell, odpowiada na pytanie zadane w przepełnieniu stosu # 35185 , jak wskazała ltn100. Wykorzystuje pamięć O (1) i czas działania O (n). Jeśli na razie przyjmiemy 32-bitowe liczby całkowite, XOR ma 7% prawdopodobieństwo wygenerowania wyraźnej liczby. Uzasadnienie: podano ~ 4G odrębne liczby XOR razem i ok. 300 M poza plikiem, liczba ustawionych bitów w każdej pozycji bitowej ma równe szanse bycia nieparzystym lub parzystym. Zatem 2 ^ 32 liczb ma równe prawdopodobieństwo pojawienia się jako wynik XOR, z czego 93% jest już zapisanych. Zauważ, że jeśli wszystkie liczby w pliku nie są różne, prawdopodobieństwo sukcesu metody XOR wzrasta.


7

Z jakiegoś powodu, gdy tylko przeczytałem ten problem, pomyślałem o diagonalizacji. Zakładam, że dowolnie duże liczby całkowite.

Przeczytaj pierwszy numer. Lewy pad z zerowymi bitami, aż będziesz miał 4 miliardy bitów. Jeśli pierwszy (wysoki) bit jest równy 0, wyjście 1; w przeciwnym razie wyjście 0. (Nie musisz tak naprawdę wstawiać lewej strony: po prostu wyprowadzasz 1, jeśli liczba nie jest wystarczająca.) Zrób to samo z drugą liczbą, z wyjątkiem tego, że używasz jej drugiego bitu. Kontynuuj przeglądanie pliku w ten sposób. Będziesz wysyłać 4 miliardy bitów po jednym bicie, a liczba ta nie będzie taka sama jak w pliku. Dowód: były takie same jak n-ta liczba, wtedy zgodziliby się co do n-tego bitu, ale z założenia nie.


+1 za kreatywność (i najmniejszą jak dotąd najgorszą wydajność dla rozwiązania jednoprzebiegowego).
Hmakholm pozostał nad Moniką

Ale nie ma 4 miliardów bitów do przekątnej, są tylko 32. Po prostu skończysz z 32-bitową liczbą, która różni się od pierwszych 32 liczb na liście.
Brian Gordon

@Henning Nie jest to jednorazowe przejście; nadal musisz przekonwertować z jednoargumentowej na binarną. Edycja: Wydaje mi się, że to jedno przejście przez plik. Nieważne.
Brian Gordon

@Brian, gdzie jest coś „unarskiego”? Odpowiedź konstruuje odpowiedź binarną raz na raz i odczytuje plik wejściowy tylko raz, co czyni go pojedynczym przejściem. (Jeśli wymagane jest wyjście dziesiętne , sytuacja staje się problematyczna - prawdopodobnie lepiej jest skonstruować jedną cyfrę dziesiętną na trzy liczby wejściowe i zaakceptować 10% wzrost dziennika liczby wyjściowej).
Hmakholm pozostawił Monikę

2
@Henning Problem nie ma sensu w przypadku dowolnie dużych liczb całkowitych, ponieważ, jak wiele osób zauważyło, znalezienie największej liczby i dodanie jednej lub skonstruowanie bardzo długiej liczby z samego pliku jest banalne. To rozwiązanie diagonalizacji jest szczególnie nieodpowiednie, ponieważ zamiast rozgałęziać na tym ibicie, możesz po prostu wyprowadzić 1 bit 4 miliardy razy i rzucić dodatkową 1 na końcu. Nie przeszkadza mi to, że mam w algorytmie dowolnie duże liczby całkowite , ale myślę, że problemem jest wyprowadzenie brakującej 32-bitowej liczby całkowitej. To po prostu nie ma sensu w żaden inny sposób.
Brian Gordon

6

Możesz użyć flag bitowych, aby zaznaczyć, czy liczba całkowita jest obecna, czy nie.

Po przejściu całego pliku, przeskanuj każdy bit, aby ustalić, czy numer istnieje, czy nie.

Zakładając, że każda liczba całkowita jest 32-bitowa, dogodnie zmieści się w 1 GB pamięci RAM, jeśli zostanie wykonane oznaczanie bitów.


0,5 Gb, chyba że ponownie zdefiniowałeś bajt na 4 bity ;-)
dty

2
@dty Myślę, że ma na myśli „komfortowo”, ponieważ w 1Gb będzie dużo miejsca.
corsiKa

6

Usuń białe znaki i znaki nienumeryczne z pliku i dołącz 1. Twój plik zawiera teraz pojedynczy numer niewymieniony w oryginalnym pliku.

Od Reddit przez Carbonetc.


Kocham to! Mimo że nie była to odpowiedź, której szukał ...: D
Johann du Toit

6

Tylko dla kompletności, oto kolejne bardzo proste rozwiązanie, które najprawdopodobniej potrwa bardzo długo, ale zużywa bardzo mało pamięci.

Niech wszystkie możliwe liczby całkowite będą z zakresu od int_mindo int_maxoraz bool isNotInFile(integer)funkcja, która zwraca wartość true, jeśli plik nie zawiera określonej liczby całkowitej, a fałsz inny (przez porównanie tej liczby całkowitej z każdą liczbą całkowitą w pliku)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Pytanie dotyczyło dokładnie algorytmu isNotInFilefunkcji. Przed udzieleniem odpowiedzi upewnij się, że rozumiesz pytanie.
Aleks G

2
nie, pytanie brzmiało „która liczba całkowita nie znajduje się w pliku”, nie „jest liczbą całkowitą x w pliku”. funkcja określająca odpowiedź na to ostatnie pytanie może na przykład po prostu porównać każdą liczbę całkowitą w pliku z liczbą całkowitą, o której mowa, i zwrócić wartość true w przypadku dopasowania.
deg

Myślę, że to uzasadniona odpowiedź. Poza I / O potrzebujesz tylko jednej liczby całkowitej i flagi bool.
Brian Gordon

@Aleks G - Nie rozumiem, dlaczego jest to oznaczone jako nieprawidłowe. Wszyscy zgadzamy się, że jest to najwolniejszy ze wszystkich algorytmów :-), ale działa i potrzebuje 4 bajtów, aby odczytać plik. Oryginalne pytanie nie przewiduje, że plik można odczytać tylko raz.
Simon Mourier

1
@Aleks G - Racja. Nigdy nie powiedziałem, że to powiedziałeś. Mówimy tylko, że IsNotInFile można w prosty sposób zaimplementować za pomocą pętli w pliku: Open; While Not Eof {Read Integer; Return False if Integer = i; Else Continue;}. Wymaga tylko 4 bajtów pamięci.
Simon Mourier,

5

Dla ograniczenia pamięci 10 MB:

  1. Konwertuj liczbę na jej reprezentację binarną.
  2. Utwórz drzewo binarne, gdzie lewy = 0, a prawy = 1.
  3. Wstaw każdą liczbę do drzewa, używając jej reprezentacji binarnej.
  4. Jeśli numer został już wstawiony, liście zostaną już utworzone.

Po zakończeniu wybierz ścieżkę, która nie została wcześniej utworzona, aby utworzyć żądany numer.

4 miliardy liczb = 2 ^ 32, co oznacza, że ​​10 MB może być niewystarczające.

EDYTOWAĆ

Optymalizacja jest możliwa, jeśli utworzono dwa końce liści i mają one wspólnego elementu nadrzędnego, wówczas można je usunąć, a element nadrzędny oflagować jako rozwiązanie. To odcina gałęzie i zmniejsza zapotrzebowanie na pamięć.

EDYCJA II

Nie ma też potrzeby budowania drzewa całkowicie. Musisz budować głębokie gałęzie tylko wtedy, gdy liczby są podobne. Jeśli wycinamy również gałęzie, to rozwiązanie może faktycznie działać.


6
... i jak to zmieści się w 10 MB?
hmakholm opuścił Monikę

A może: ograniczyć głębokość BTree do czegoś, co zmieściłoby się w 10 MB; oznaczałoby to, że miałbyś wyniki w zbiorze {fałszywie dodatni | pozytywne} i możesz iterować przez to i użyć innych technik, aby znaleźć wartości.
Jonathan Dickinson

5

Odpowiem na wersję 1 GB:

W pytaniu nie ma wystarczających informacji, dlatego najpierw przedstawię pewne założenia:

Liczba całkowita wynosi 32 bity z zakresu -2 147 483 648 do 2 147 483 647.

Pseudo kod:

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;
    }
}

4

Tak długo, jak robimy twórcze odpowiedzi, oto kolejna.

Użyj zewnętrznego programu do sortowania, aby posortować plik wejściowy numerycznie. Będzie to działać dla dowolnej ilości pamięci, którą możesz mieć (w razie potrzeby wykorzysta miejsce do przechowywania plików). Przeczytaj posortowany plik i wypisz pierwszą brakującą liczbę.


3

Eliminacja bitów

Jednym ze sposobów jest wyeliminowanie bitów, jednak może to nie dać rezultatu (istnieje szansa, że ​​tak się nie stanie). Psuedocode:

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

Liczy się bit

Śledź liczbę bitów; i użyj bitów z najmniejszą ilością do wygenerowania wartości. Ponownie nie ma to gwarancji wygenerowania prawidłowej wartości.

Logika zasięgu

Śledź listę uporządkowanych zakresów (uporządkowanych według początku). Zakres jest określony przez strukturę:

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

Przejrzyj każdą wartość w pliku i spróbuj usunąć ją z bieżącego zakresu. Ta metoda nie ma gwarancji pamięci, ale powinna działać całkiem dobrze.


3

2 128 * 10 18 + 1 (czyli (2 8 ) 16 * 10 18 + 1) - czy nie może to być odpowiedź uniwersalna na dziś? Jest to liczba, której nie można zapisać w pliku 16 EB, czyli maksymalny rozmiar pliku w dowolnym bieżącym systemie plików.


A jak wydrukowałbyś wynik? Nie można go umieścić w pliku, a drukowanie na ekranie zajęłoby kilka miliardów lat. W dzisiejszych komputerach nie ma czasu przestoju.
vsz

nigdy nie mówi się, że musimy nigdzie wydrukować wynik, wystarczy go „wygenerować”. więc zależy to od tego, co rozumiesz przez generowanie. tak czy inaczej, moja odpowiedź jest tylko sztuczką, aby uniknąć wypracowania prawdziwego algorytmu :)
Michael Sagalovich

3

Myślę, że jest to rozwiązany problem (patrz wyżej), ale jest ciekawy przypadek uboczny, o którym należy pamiętać, ponieważ można go zapytać:

Jeśli istnieje dokładnie 4 294 967 295 (2 ^ 32 - 1) 32-bitowych liczb całkowitych bez powtórzeń, a zatem brakuje tylko jednego, istnieje proste rozwiązanie.

Rozpocznij sumę całkowitą od zera, a dla każdej liczby całkowitej w pliku dodaj tę liczbę całkowitą z 32-bitowym przepełnieniem (efektywnie, runningTotal = (runningTotal + nextInteger)% 4294967296). Po zakończeniu dodaj 4294967296/2 do bieżącej sumy, ponownie z 32-bitowym przepełnieniem. Odejmij to od 4294967296, a wynikiem będzie brakująca liczba całkowita.

Problem „tylko jednej brakującej liczby całkowitej” można rozwiązać tylko jednym uruchomieniem i tylko 64 bitami pamięci RAM przeznaczonymi na dane (32 dla łącznej liczby operacji, 32 do odczytu w następnej liczbie całkowitej).

Następstwo: bardziej ogólna specyfikacja jest niezwykle łatwa do dopasowania, jeśli nie martwi nas liczba bitów, jaką musi zawierać wynik liczby całkowitej. Po prostu generujemy na tyle dużą liczbę całkowitą, że nie może być zawarta w podanym pliku. Ponownie zajmuje to absolutnie minimalną pamięć RAM. Zobacz pseudokod.

# 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";
  }
}

@Nakilon i TheDayTurns zwrócili na to uwagę w komentarzach do pierwotnego pytania
Brian Gordon

3

Jak powiedział Ryan w zasadzie, posortuj plik, a następnie przejrzyj liczby całkowite, a gdy pominiesz wartość, masz ją :)

EDYCJA u downvoters: OP wspomniał, że plik może być posortowany, więc jest to poprawna metoda.


Jedną z kluczowych rzeczy jest to, że powinieneś robić to na bieżąco, w ten sposób musisz czytać tylko raz. Dostęp do pamięci fizycznej jest powolny.
Ryan Amos,

@ryan sortowanie zewnętrzne jest w większości przypadków sortowaniem scalającym, więc przy ostatnim scaleniu możesz wykonać sprawdzenie :)
maniak ratchet

Jeśli dane znajdują się na dysku, należy je załadować do pamięci. Dzieje się to automatycznie przez system plików. Jeśli musimy znaleźć jeden numer (problem nie stanowi inaczej), to najbardziej efektywnym sposobem jest odczytanie posortowanego pliku po linii. Zużywa niewiele pamięci i nie jest wolniejszy niż cokolwiek innego - plik musi zostać odczytany.
Tony Ennis,

Jak posortujesz 4 miliardy liczb całkowitych, jeśli masz tylko 1 GB pamięci? Jeśli użyjesz pamięci wirtualnej, zajmie to dużo czasu, ponieważ bloki pamięci są wczytywane i usuwane z pamięci fizycznej.
Klas Lindbäck

4
@klas sortowanie przez scalanie jest przeznaczony do tego
zapadkowy dziwaka

2

Jeśli nie przyjmujesz ograniczenia 32-bitowego, po prostu zwróć losowo wygenerowaną liczbę 64-bitową (lub 128-bitową, jeśli jesteś pesymistą). Prawdopodobieństwo kolizji wynosi 1 in 2^64/(4*10^9) = 4611686018.4(około 1 na 4 miliardy). Przez większość czasu miałbyś rację!

(Żartuję ... w pewnym sensie.)


Widzę, że zostało to już zasugerowane :) głosy poparcia dla tych ludzi
Peter Gibson

Paradoks urodzinowy sprawia, że ​​tego rodzaju rozwiązanie nie jest warte ryzyka, bez sprawdzania pliku, aby sprawdzić, czy przypadkowe odgadnięcie było rzeczywiście prawidłową odpowiedzią. (Paradoks urodzinowy nie ma zastosowania w tym przypadku, ale wielokrotne wywoływanie tej funkcji w celu wygenerowania nowych unikalnych wartości tworzy sytuację paradoksu urodzinowego.)
Peter Cordes

@PeterCordes Losowo generowane liczby 128-bitowe dokładnie działają UUID - wspominają nawet o paradoksie urodzinowym przy obliczaniu prawdopodobieństwa kolizji na stronie UUID
Peter Gibson

Wariant: znajdź maksimum w zestawie, dodaj 1.
Phil

Szybko posortowałem pierwotną tablicę (bez dodatkowej pamięci), a następnie maszerowałem przez tablicę i zgłosiłem pierwszą „pominiętą” liczbę całkowitą. Gotowy. Odpowiedział na pytanie.
Poziom 42
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.