Zdobądź 100 najwyższych liczb z nieskończonej listy

53

Jedno z moich znajomych zostało zadane w tym wywiadzie -

„Ciągły napływ liczb przychodzi z nieskończonej listy liczb, z których trzeba utrzymywać strukturę danych, aby zwracać 100 najwyższych liczb w danym momencie. Załóżmy, że wszystkie liczby są tylko liczbami całkowitymi”.

Jest to proste, musisz utrzymywać posortowaną listę w kolejności malejącej i śledzić najniższy numer na tej liście. Jeśli uzyskany nowy numer jest większy niż ten najniższy numer, należy usunąć ten najniższy numer i w razie potrzeby wstawić nowy numer na posortowanej liście.

Następnie pytanie zostało przedłużone -

„Czy możesz upewnić się, że zamówienie na wstawienie powinno mieć wartość O (1)? Czy to możliwe?”

O ile mi wiadomo, nawet jeśli dodasz nowy numer do listy i posortujesz go ponownie za pomocą dowolnego algorytmu sortowania, najlepiej byłoby O (logn) dla szybkiego sortowania (myślę). Więc mój przyjaciel powiedział, że to niemożliwe. Ale nie był przekonany, poprosił o zachowanie innej struktury danych niż listy.

Myślałem o zrównoważonym drzewie binarnym, ale nawet tam nie dostaniesz wstawienia w kolejności 1. Więc to samo pytanie mam również teraz. Chciałem wiedzieć, czy istnieje taka struktura danych, która może wstawiać w kolejności 1 dla powyższego problemu lub nie jest to w ogóle możliwe.

Sachin Shanbhag
źródło
19
Może to tylko ja źle rozumiem pytanie, ale dlaczego musisz prowadzić posortowaną listę? Dlaczego po prostu nie śledzić najniższej liczby, a jeśli napotkasz liczbę wyższą niż ta, usuń najniższą liczbę i wstaw nowy, bez sortowania listy. To dałoby ci O (1).
EdoDodo
36
@EdoDodo - a po tej operacji, skąd wiesz, jaki jest nowy najniższy numer?
Damien_The_Unbeliever
19
Posortuj listę [O (100 * log (100)) = O (1)] lub przeprowadź przez nią liniowe wyszukiwanie co najmniej [O (100) = O (1)], aby uzyskać nową najniższą liczbę. Twoja lista ma stały rozmiar, więc wszystkie te operacje są również stałym czasem.
Random832
6
Nie musisz sortować całej listy. Nie obchodzi Cię, jaki jest najwyższy lub drugi najwyższy numer. Musisz tylko wiedzieć, która jest najniższa. Więc po wstawieniu nowego numeru, po prostu przejrzyj 100 liczb i sprawdź, która z nich jest teraz najniższa. To jest stały czas.
Tom Zych
27
Asymptotycznej kolejność operacji jest tylko interesujące , gdy rozmiar problemu mogą rosnąć bez granicy. Z twojego pytania nie jest jasne, która ilość rośnie bez ograniczeń; wygląda na to, że pytasz, jaki jest porządek asymptotyczny dla problemu, którego rozmiar jest ograniczony do 100; nie jest to nawet rozsądne pytanie; coś musi rosnąć bez ograniczeń. Jeśli pytanie brzmi „czy możesz to zrobić, aby zachować najwyższą liczbę n, a nie najwyższą liczbę 100, w czasie O (1)?” to pytanie jest rozsądne.
Eric Lippert,

Odpowiedzi:

35

Powiedzmy, że k jest liczbą najwyższych liczb, które chcesz znać (100 w twoim przykładzie). Następnie możesz dodać nowy numer, w O(k)którym również jest O(1). Ponieważ O(k*g) = O(g) if k is not zero and constant.

duedl0r
źródło
6
O (50) oznacza O (n), a nie O (1). Wstawienie do listy długości N w czasie O (1) oznacza, że ​​czas nie zależy od wartości N. Oznacza to, że jeśli 100 staje się 10000, 50 NIE może stać się 5000.
18
@hamstergene - ale w przypadku tego pytania, Nczy rozmiar posortowanej listy, czy liczba elementów, które zostały przetworzone do tej pory? Jeśli przetworzysz 10000 pozycji i utrzymasz 100 najlepszych pozycji na liście lub przetworzysz 1000000000 pozycji i utrzymasz 100 najlepszych pozycji na posortowanej liście, koszty wstawienia na tej liście pozostaną takie same.
Damien_The_Unbeliever
6
@hamstergene: W takim przypadku podstawy były błędne. W linku wikipedia nie jest właściwością ( „Mnożenie przez stałą”) O(k*g) = O(g) if k not zero and constant. => O(50*1) = O(1).
duedl0r
9
Myślę, że duedl0r ma rację. Ograniczmy problem i powiedzmy, że potrzebujesz tylko wartości minimalnej i maksymalnej. Czy to O (n), ponieważ minimalna i maksymalna to 2? (n = 2). Nr 2 jest częścią definicji problemu. Jest stałą, więc jest ak w O (k * coś), co jest równoważne O (coś)
xanatos
9
@hamstergene: o jakiej funkcji mówisz? wartość 100 wydaje mi się dość stała.
duedl0r
19

Zachowaj listę nieposortowaną. Ustalenie, czy wstawić nowy numer zajmie więcej czasu, ale wstawienie będzie O (1).

Emilio M. Bumachar
źródło
7
Myślę, że dostaniesz nagrodę smart-aleck, jeśli nic więcej. * 8 ')
Mark Booth
4
@Emilio, technicznie masz rację - i oczywiście jest to najlepszy rodzaj poprawności…
Gareth
1
Możesz jednak zachować najniższą z 100 liczb, a następnie zdecydować, czy chcesz wstawić O (1). Tylko wtedy, gdy wstawisz numer, musisz wyszukać nowy najniższy numer. Ale zdarza się to rzadziej niż decyzja o wstawieniu lub nie, co dzieje się z każdym nowym numerem.
Andrei Vajna II
12

To jest łatwe. Rozmiar listy stałej, dlatego czas sortowania listy jest stały. Mówi się, że operacja wykonywana w stałym czasie to O (1). Dlatego sortowanie listy to O (1) dla listy o ustalonym rozmiarze.

Kirk Broadhurst
źródło
9

Po przejściu 100 liczb, maksymalny koszt, jaki kiedykolwiek poniesiesz za następną liczbę, to koszt sprawdzenia, czy liczba jest w najwyższej liczbie 100 ( oznaczmy to CheckTime ) plus koszt wpisania jej do tego zestawu i wysunięcie najniższy (nazwijmy to EnterTime ), który jest stałym czasem (przynajmniej dla liczb ograniczonych) lub O (1) .

Worst = CheckTime + EnterTime

Następnie, jeśli rozkład liczb jest losowy, średni koszt zmniejsza się, im więcej liczb masz. Na przykład szansa, że ​​będziesz musiał wpisać 101. liczbę do maksymalnego zestawu, wynosi 100/101, szanse na 1000. liczby to 1/10, a szanse na n-tą liczbę to 100 / n. Zatem nasze równanie średniego kosztu będzie:

Average = CheckTime + EnterTime / n

Zatem, gdy n zbliża się do nieskończoności, ważny jest tylko CheckTime :

Average = CheckTime

Jeśli liczby są powiązane, CheckTime jest stały, a zatem jest to czas O (1) .

Jeśli liczby nie są powiązane, czas sprawdzania wydłuży się wraz z większą liczbą liczb. Teoretycznie dzieje się tak, ponieważ jeśli najmniejsza liczba w maksymalnym zestawie stanie się wystarczająco duża, czas sprawdzania będzie dłuższy, ponieważ będziesz musiał rozważyć więcej bitów. To sprawia, że ​​wydaje się, że będzie nieco wyższy niż stały czas. Jednak można również argumentować, że szansa, że ​​następna liczba jest w najwyższym zbiorze, zbliża się do zera, gdy n zbliża się do nieskończoności, a więc szansa, że ​​musisz rozważyć więcej bitów, również zbliża się do 0, co byłoby argumentem dla O (1) czas.

Nie jestem pozytywny, ale moje jelita mówią, że jest to czas O (log (log (n))) . Jest tak, ponieważ szansa, że ​​najniższa liczba wzrośnie, jest logarytmiczna, a szansa, że ​​liczba bitów, które należy wziąć pod uwagę przy każdej kontroli, jest również logarytmiczna. Interesują mnie inne narody, ponieważ nie jestem do końca pewien ...

Briguy37
źródło
Tyle, że lista jest dowolna, co jeśli jest to lista ciągle rosnących liczb?
dan_waterworth
@dan_waterworth: Jeśli nieskończona lista jest dowolna i zdarza się, że kiedykolwiek rośnie (prawdopodobieństwo jej wyniesie 1 / ∞!), pasowałoby to do najgorszego scenariusza CheckTime + EnterTimedla każdej liczby. Ma to sens tylko wtedy, gdy liczby są nieograniczone, i tak, CheckTimei EnterTimeoba wzrosną przynajmniej logarytmicznie z powodu wzrostu wielkości liczb.
Briguy37,
1
Liczby nie są losowe, są arbitralne. Nie ma sensu rozmawiać o szansach.
dan_waterworth
@dan_waterworth: Powiedziałeś już dwa razy, że liczby są dowolne. Skąd to bierzesz? Uważam również, że nadal możesz stosować statystyki do dowolnych liczb, poczynając od przypadkowego przypadku, i poprawić ich dokładność, ponieważ wiesz więcej o arbitrze. Na przykład, gdybyś był arbitrem, wydaje się, że byłaby większa szansa na wybranie ciągle rosnących liczb, niż gdyby, powiedzmy, byłem arbitrem;)
Briguy37,
7

ten jest łatwy, jeśli znasz Binary Heap Trees . Sterty binarne wspierają wstawianie w średnim stałym czasie, O (1). I daje łatwy dostęp do pierwszych x elementów.

maniak zapadkowy
źródło
Po co przechowywać elementy, których nie potrzebujesz? (wartości, które są zbyt niskie) Wydaje się, że algorytm niestandardowy jest bardziej odpowiedni. Nie mówiąc, że nie można „nie dodawać” wartości, gdy nie są one wyższe od najniższych.
Steven Jeuris,
Nie wiem, moja intuicja podpowiada mi, że kupa (o jakimś smaku) mogłaby to całkiem dobrze znieść. Nie znaczy to, że musiałby zachować wszystkie elementy, aby to zrobić. Nie badałem tego, ale „czuje się dobrze” (TM).
Rig
3
Stertę można zmodyfikować, aby odrzucić wszystko poniżej pewnego m-tego poziomu (dla stosów binarnych i k = 100, m wynosi 7, ponieważ liczba węzłów = 2 ^ m-1). Spowolniłoby to, ale nadal byłby amortyzowany przez cały czas.
Plutor
3
Jeśli użyłeś binarnej min-sterty (ponieważ wtedy górna jest minimum, którą cały czas sprawdzasz) i znajdziesz nową liczbę> min, to musisz usunąć górny element, zanim będziesz mógł wstawić nowy . Usunięcie górnego (min) elementu będzie oznaczało O (logN), ponieważ musisz przejść przez wszystkie poziomy drzewa jeden raz. Jest więc technicznie prawdą, że wstawki mają średnią wartość O (1), ponieważ w praktyce jest to nadal O (logN) za każdym razem, gdy znajdziesz liczbę> min.
Scott Whitlock,
1
@Plutor, zakładasz pewne gwarancje, których nie dają binarne stosy. Wizualizując to jako drzewo binarne, może się zdarzyć, że każdy element w lewej gałęzi jest mniejszy niż jakikolwiek element w prawej gałęzi, ale zakładasz, że najmniejsze elementy są najbliższe katalogu głównego.
Peter Taylor
6

Jeśli na pytanie pytający naprawdę chciał zapytać „czy możemy upewnić się, że każdy przychodzący numer jest przetwarzany w stałym czasie”, to jak wielu już wskazało (np. Patrz odpowiedź @ duedl0r), rozwiązaniem twojego znajomego jest już O (1), i tak by było, nawet gdyby użył nieposortowanej listy, użył sortowania bąbelkowego lub cokolwiek innego. W takim przypadku pytanie nie ma większego sensu, chyba że było to trudne pytanie lub źle go pamiętasz.

Zakładam, że pytanie ankietera było znaczące, że nie pytał, jak zrobić coś, aby być O (1), co już bardzo oczywiste już jest.

Ponieważ złożoność algorytmu kwestionowania ma sens tylko wtedy, gdy wielkość danych wejściowych rośnie w nieskończoność, a jedyne dane wejściowe, które mogą tutaj wzrosnąć, to 100 - wielkość listy; Zakładam, że prawdziwym pytaniem było „czy możemy się upewnić, że Top N spędza O (1) czas na liczbę (nie O (N) jak w rozwiązaniu twojego przyjaciela), czy to możliwe?”.

Pierwszą rzeczą, która przychodzi na myśl, jest zliczanie sortowania, które kupi złożoność czasu O (1) na liczbę dla problemu Top-N za cenę użycia przestrzeni O (m), gdzie m jest długością zakresu liczb przychodzących . Tak, jest to możliwe.

hamstergen
źródło
4

Użyj kolejki o minimalnym priorytecie zaimplementowanej ze stertą Fibonacciego , która ma stały czas wstawiania:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)
Gabe Moothart
źródło
4
„Operacje usuwają i usuwają minimalny czas pracy w O(log n)zamortyzowanym czasie” , więc nadal spowodowałoby to, O(log k)gdzie kjest ilość przedmiotów do przechowywania.
Steven Jeuris,
1
Nie różni się to od odpowiedzi Emilio, która została nazwana „nagrodą smart-aleck”, ponieważ delete min działa w O (log n) (według Wikipedii).
Nicole,
@Rezezja Emilio odpowiedziałaby O (k), aby znaleźć minimum, moje to O (log k)
Gabe Moothart
1
@ Gabe W porządku, mam na myśli w zasadzie. Innymi słowy, jeśli nie weźmiesz 100 za stałą, to ta odpowiedź również nie będzie ciągła.
Nicole,
@Reneesis Usunąłem (niepoprawną) instrukcję z odpowiedzi.
Gabe Moothart,
2

Zadanie polega na znalezieniu algorytmu O (1) o długości N wymaganej listy liczb. Nie ma więc znaczenia, czy potrzebujesz 100 najlepszych numerów, czy 10000 liczb, czas wstawienia powinien wynosić O (1).

Sztuczka polega na tym, że chociaż wspomniany jest wymóg O (1) dla wstawki listy, pytanie nie mówiło nic o kolejności czasu wyszukiwania w całej przestrzeni liczbowej, ale okazuje się, że można to zrobić O (1) także. Rozwiązanie jest następujące:

  1. Umów się na tablicę skrótów z liczbami na klucze i parami połączonych wskaźników listy dla wartości. Każda para wskaźników jest początkiem i końcem połączonej sekwencji list. Zwykle będzie to tylko jeden element, a następnie następny. Każdy element na połączonej liście znajduje się obok elementu o kolejnym najwyższym numerze. Lista połączona zawiera posortowaną sekwencję wymaganych numerów. Przechowuj rekord o najniższej liczbie.

  2. Weź nową liczbę x z losowego strumienia.

  3. Czy jest wyższy niż ostatnio zarejestrowany najniższy numer? Tak => Krok 4, Nie => Krok 2

  4. Traf w tablicę skrótów z właśnie pobraną liczbą. Czy jest wpis? Tak => Krok 5. Nie => Weź nową liczbę x-1 i powtórz ten krok (jest to proste wyszukiwanie liniowe w dół, po prostu zmiłuj się tutaj, można to poprawić, a ja wyjaśnię, jak)

  5. Po uzyskaniu elementu listy z tabeli skrótów wstaw nowy numer zaraz po elemencie na liście połączonej (i zaktualizuj skrót)

  6. Weź najniższą zarejestrowaną liczbę l (i usuń ją z mieszania / listy).

  7. Traf w tablicę skrótów z właśnie pobraną liczbą. Czy jest wpis? Tak => Krok 8. Nie => Weź nową liczbę l + 1 i powtórz ten krok (jest to proste wyszukiwanie liniowe w górę)

  8. Po trafieniu dodatnim liczba staje się nową najniższą liczbą. Przejdź do kroku 2

Aby pozwolić na zduplikowane wartości, skrót faktycznie musi utrzymywać początek i koniec połączonej sekwencji elementów, które są duplikatami. Dodanie lub usunięcie elementu pod danym klawiszem zwiększa lub zmniejsza wskazany zakres.

Tu wstawka to O (1). Wspomniane wyszukiwania to, jak sądzę, coś w rodzaju O (średnia różnica między liczbami). Średnia różnica rośnie wraz z rozmiarem przestrzeni liczbowej, ale maleje wraz z wymaganą długością listy liczb.

Zatem strategia wyszukiwania liniowego jest dość słaba, jeśli przestrzeń liczbowa jest duża (np. Dla typu int 4 bajtowego, od 0 do 2 ^ 32-1) i N = 100. Aby obejść ten problem z wydajnością, możesz przechowywać równoległe zestawy tablic mieszających, w których liczby są zaokrąglane do większych wielkości (np. 1s, 10s, 100s, 1000s), aby utworzyć odpowiednie klucze. W ten sposób możesz zwiększać i zmniejszać biegi, aby szybciej przeprowadzać wymagane wyszukiwania. Wydajność staje się wtedy O (logarytmiczny zakres), myślę, że jest stała, tj. O (1) również.

Aby to wyjaśnić, wyobraź sobie, że masz pod ręką liczbę 197. Trafiłeś tablicę haszującą 10s, z „190”, jest ona zaokrąglana do najbliższej dziesiątki. Byle co? Nie. Więc schodzisz za 10s, aż trafisz powiedz 120. Następnie możesz zacząć od 129 w tablicy 1s, a następnie spróbuj 128, 127, aż coś trafisz. Znalazłeś teraz miejsce na połączonej liście, aby wstawić numer 197. Podczas wpisywania musisz również zaktualizować tablicę hashtable 1 z wpisem 197, tablicę hasht z 10s o numerze 190, 100s ze 100 itd. Najwięcej kroków musisz tu zrobić 10 razy więcej niż dziennik zakresu liczb.

Mogłem pomylić niektóre szczegóły, ale ponieważ jest to wymiana programistów, a kontekstem były wywiady, mam nadzieję, że powyższe jest wystarczająco przekonującą odpowiedzią na tę sytuację.

EDYCJA Dodałem tutaj kilka dodatkowych szczegółów w celu wyjaśnienia równoległego schematu tablicy mieszającej i tego, jak to znaczy, że słabe wyszukiwania liniowe, o których wspomniałem, można zastąpić wyszukiwaniem O (1). Zdałem sobie również sprawę, że oczywiście nie ma potrzeby szukania następnej najniższej liczby, ponieważ możesz przejść od razu do niej, zaglądając do tablicy hasht z najmniejszą liczbą i przechodząc do następnego elementu.

Benedykt
źródło
1
Wyszukiwanie musi być częścią funkcji wstawiania - nie są to funkcje niezależne. Ponieważ twoje wyszukiwanie to O (n), twoja funkcja wstawiania jest również O (n).
Kirk Broadhurst,
Nie. Korzystając ze strategii, którą opisałem, gdzie więcej skrótów jest używanych do szybszego przemierzania przestrzeni liczb, jest to O (1). Przeczytaj ponownie moją odpowiedź.
Benedykt
1
@Benedict, twoja odpowiedź mówi dość wyraźnie, że ma wyszukiwania liniowe w krokach 4 i 7. Wyszukiwanie liniowe nie jest O (1).
Peter Taylor
Tak, ale mam to później. Czy mógłbyś przeczytać resztę, proszę. W razie potrzeby zmienię moją odpowiedź, aby była całkowicie jasna.
Benedykt
@Benedict Masz rację - wyłączając wyszukiwanie, Twoja odpowiedź to O (1). Niestety to rozwiązanie nie będzie działać bez wyszukiwania.
Kirk Broadhurst
1

Czy możemy założyć, że liczby mają stały typ danych, taki jak liczba całkowita? Jeśli tak, zachowaj podsumowanie każdego dodanego numeru. Jest to operacja O (1).

  1. Zadeklaruj tablicę z tyloma elementami, ile jest możliwych liczb:
  2. Czytaj każdy numer, który jest przesyłany strumieniowo.
  3. Zlicz liczbę. Zignoruj ​​go, jeśli liczba ta została już zwiększona 100 razy, ponieważ nigdy jej nie będziesz potrzebować. Zapobiega to liczeniu przelewów przez nieskończoną liczbę razy.
  4. Powtórz od kroku 2.

Kod VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Po zwróceniu listy możesz wziąć tyle, ile chcesz. Po prostu iteruj od końca listy i utwórz nową listę z najwyższymi 100 zarejestrowanymi wartościami. To operacja O (n), ale to nieistotne.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Edycja: W rzeczywistości nie ma znaczenia, czy jest to stały typ danych. Biorąc pod uwagę, że nie ma narzuconych limitów zużycia pamięci (lub dysku twardego), możesz to zrobić dla dowolnego zakresu liczb całkowitych dodatnich.

Hand-E-Food
źródło
1

Sto liczb można łatwo zapisać w tablicy, rozmiar 100. Każde drzewo, lista lub zestaw jest przesadzone, biorąc pod uwagę dane zadanie.

Jeśli liczba przychodząca jest wyższa niż najniższa (= ostatnia) w tablicy, przejrzyj wszystkie wpisy. Gdy znajdziesz pierwszy, który jest mniejszy niż nowy numer (możesz użyć do tego wyszukanych wyszukiwań), biegnij przez resztę tablicy, przesuwając każdy wpis „w dół” o jeden.

Ponieważ sortujesz listę od początku, nie musisz wcale uruchamiać żadnego algorytmu sortowania. To jest O (1).

Jörg Z.
źródło
0

Możesz użyć Binary Max-Heap. Będziesz musiał śledzić wskaźnik do minimalnego węzła (który może być nieznany / null).

Zaczynasz od wstawienia pierwszych 100 liczb do sterty. Maksimum będzie na górze. Po wykonaniu tej czynności zawsze będziesz przechowywać 100 numerów.

Następnie, gdy otrzymasz nowy numer:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Niestety findMinimumNodejest O (n), a ty ponosisz ten koszt raz na wkładkę (ale nie podczas wkładki :). Usunięcie minimalnego węzła i wstawienie nowego węzła to średnio O (1), ponieważ będą dążyły do ​​dołu stosu.

Idąc w drugą stronę z Binary Min-Heap, min jest na górze, co jest świetne do znalezienia min do porównania, ale jest do bani, gdy trzeba zastąpić minimum nową liczbą, która jest> min. Jest tak, ponieważ musisz usunąć minimalny węzeł (zawsze O (logN)), a następnie wstawić nowy węzeł (średni O (1)). Tak więc nadal masz O (logN), co jest lepsze niż Max-Heap, ale nie O (1).

Oczywiście, jeśli N jest stałe, to zawsze masz O (1). :)

Scott Whitlock
źródło