Napisz program, aby znaleźć 100 największych liczb z tablicy 1 miliarda liczb


300

Niedawno wziąłem udział w wywiadzie, w którym poproszono mnie o „napisanie programu znajdującego 100 największych liczb z tablicy 1 miliarda liczb”.

Byłem w stanie podać rozwiązanie brutalnej siły, które polegało na posortowaniu tablicy w złożoności czasowej O (nlogn) i wzięciu ostatnich 100 liczb.

Arrays.sort(array);

Ankieter szukał lepszej komplikacji czasowej. Wypróbowałem kilka innych rozwiązań, ale nie odpowiedziałem mu. Czy istnieje lepsze rozwiązanie w zakresie złożoności czasu?


70
Być może problemem jest to, że nie było to pytanie sortujące , ale szukające .
geomagas

11
Z technicznego punktu widzenia sortowanie może nie być najlepszym sposobem rozwiązania problemu, ale nie sądzę, że jest to brutalna siła - mogę wymyślić o wiele gorsze sposoby na zrobienie tego.
Bernhard Barker,

88
Właśnie pomyślałem o jeszcze bardziej głupiej metodzie brutalnej siły ... Znajdź wszystkie możliwe kombinacje 100 elementów z tablicy 1 miliarda elementów i zobacz, która z tych kombinacji ma największą sumę.
Shashank

10
Zauważ, że wszystkie deterministyczne (i poprawne) algorytmy są O(1)w tym przypadku, ponieważ nie ma wzrostu wymiarów. Ankieter powinien był zapytać „Jak znaleźć m największych elementów z tablicy nz n >> m?”.
Bakuriu

Odpowiedzi:


328

Możesz zachować kolejkę priorytetową ze 100 największych liczb, iterować przez miliardy liczb, ilekroć napotkasz liczbę większą niż najmniejsza liczba w kolejce (głowa kolejki), usuń głowę kolejki i dodaj nowy numer do kolejki.

EDYCJA: jak zauważył Dev, z kolejką priorytetową zaimplementowaną ze stertą, złożoność wstawiania do kolejki jestO(logN)

W najgorszym przypadku masz lepszy niżbillionlog2(100)billionlog2(billion)

Ogólnie rzecz biorąc, jeśli potrzebujesz największych liczb K z zestawu liczb N, złożoność jest O(NlogK)raczej niż O(NlogN), może to być bardzo znaczące, gdy K jest bardzo małe w porównaniu do N.

EDYCJA 2:

Oczekiwany czas działania tego algorytmu jest dość interesujący, ponieważ w każdej iteracji wstawienie może wystąpić lub nie. Prawdopodobieństwo, że i-ta liczba zostanie wstawiona do kolejki, to prawdopodobieństwo, że zmienna losowa jest większa niż przynajmniej i-Kzmienne losowe z tego samego rozkładu (pierwsze k liczb jest automatycznie dodawane do kolejki). Możemy użyć statystyk zamówień (patrz link ), aby obliczyć to prawdopodobieństwo. Załóżmy na przykład, że liczby zostały losowo wybrane równomiernie z {0, 1}, oczekiwaną wartością (iK) liczby (spośród liczb i) jest (i-k)/i, a szansa na to, że zmienna losowa będzie większa niż ta wartość 1-[(i-k)/i] = k/i.

Zatem oczekiwana liczba wstawek wynosi:

enter image description here

Oczekiwany czas działania można wyrazić jako:

enter image description here

( kczas wygenerowania kolejki z pierwszymi kelementami, następnie n-kporównań i oczekiwanej liczby wstawek, jak opisano powyżej, każdy zajmuje średni log(k)/2czas)

Zauważ, że gdy Njest bardzo duży w porównaniu do K, to wyrażenie jest znacznie bliższe nniż NlogK. Jest to nieco intuicyjne, ponieważ w przypadku pytania, nawet po 10000 iteracjach (co jest bardzo małe w porównaniu do miliarda), szansa na wstawienie liczby do kolejki jest bardzo mała.


6
W rzeczywistości jest to tylko O (100) dla każdej wkładki.
MrSmith42

8
@RonTeller Nie można efektywnie wyszukiwać binarnie połączonej listy, dlatego kolejka priorytetowa jest zwykle implementowana ze stertą. Twój opisany czas wstawiania to O (n), a nie O (logn). Za pierwszym razem miałeś rację (kolejka uporządkowana lub kolejka priorytetowa), dopóki Skizz sam nie zgadł.
Dev

17
@ThomasJungblut miliard jest również stały, więc jeśli tak, to O (1): P
Ron Teller

9
@RonTeller: zwykle tego rodzaju pytania dotyczą np. Znalezienia 10 najważniejszych stron z miliardów wyników wyszukiwania Google, 50 najczęściej używanych słów w chmurze słów lub 10 najpopularniejszych piosenek na MTV itp. Tak więc uważam, że w normalnych okolicznościach Można go uznać za k stały i mały w porównaniu do n. Trzeba jednak zawsze pamiętać o tych „normalnych okolicznościach”.
zaprzyjaźnij się

5
Ponieważ masz przedmioty 1G, próbkuj 1000 elementów losowo i wybierz największą 100. Powinno to unikać przypadków zdegenerowanych (sortowanych, sortowanych odwrotnie, głównie sortowanych), co znacznie zmniejsza liczbę wstawek.
ChuckCottrill

136

Jeśli zostanie to zadane podczas wywiadu, myślę, że osoba przeprowadzająca wywiad prawdopodobnie chce zobaczyć proces rozwiązywania problemów, a nie tylko znajomość algorytmów.

Opis jest dość ogólny, więc może możesz zapytać go o zakres lub znaczenie tych liczb, aby wyjaśnić problem. Może to wywrzeć na ankiecie wrażenie. Jeśli na przykład liczby te oznaczają wiek osób w danym kraju (np. Chinach), to jest to o wiele łatwiejszy problem. Przy rozsądnym założeniu, że nikt nie żyje, jest starszy niż 200, możesz użyć tablicy int o rozmiarze 200 (może 201), aby policzyć liczbę osób w tym samym wieku w jednej iteracji. Tutaj wskaźnik oznacza wiek. Po tym jest bułka z masłem, aby znaleźć 100 największą liczbę. Nawiasem mówiąc, ten algo nazywa się sortowaniem zliczającym .

W każdym razie, uściślenie i wyjaśnienie pytania jest dobre dla ciebie w wywiadzie.


26
Bardzo dobre punkty. Nikt inny nie zapytał ani nie wskazał nic na temat rozmieszczenia tych liczb - może to mieć znaczenie w podejściu do problemu.
NealB

13
Chciałbym tę odpowiedź na tyle, by ją rozszerzyć. Przeczytaj liczby jeden raz, aby uzyskać wartości min / max, abyś mógł założyć rozkład. Następnie wybierz jedną z dwóch opcji. Jeśli zasięg jest wystarczająco mały, zbuduj tablicę, w której możesz po prostu sprawdzić liczby w miarę ich pojawiania się. Jeśli zasięg jest zbyt duży, skorzystaj z algorytmu posortowanego stosu omówionego powyżej ... Po prostu myśl.
Richard_G

2
Zgadzam się, zadawanie pytań ankieterowi rzeczywiście robi dużą różnicę. W rzeczywistości pytanie takie, czy jesteś ograniczony mocą obliczeniową, czy nie, może również pomóc w zrównolegleniu rozwiązania za pomocą wielu węzłów obliczeniowych.
Sumit Nigam

1
@R_G Nie ma potrzeby przeglądania całej listy. Wystarczy, aby pobrać próbkę niewielkiej części (np. Milion) losowych członków listy, aby uzyskać przydatne statystyki.
Itamar,

Dla tych, którzy nie pomyśleliby o tym rozwiązaniu, polecam przeczytać o sortowaniu liczącym en.wikipedia.org/wiki/Counting_sort . To właściwie dość częste pytanie podczas wywiadu: czy możesz posortować tablicę lepiej niż O (nlogn). To pytanie jest tylko rozszerzeniem.
Maxime Chéramy

69

Możesz iterować liczby, które przyjmują O (n)

Za każdym razem, gdy znajdziesz wartość większą niż bieżące minimum, dodaj nową wartość do kolejki okrągłej o rozmiarze 100.

Min. Tej okrągłej kolejki to nowa wartość porównania. Dodawaj do tej kolejki. Jeśli jest pełna, wyodrębnij minimum z kolejki.


3
To nie działa np. znajdź pierwszą 2 z {1, 100, 2, 99} da {100,1} jako pierwszą 2.
Skizz

7
Nie można się obejść, aby uporządkować kolejkę. (jeśli nie chcesz za każdym razem przeszukiwać kolejki otworów w poszukiwaniu następnego najmniejszego elementu)
MrSmith42,

3
@ MrSmith42 Częściowe sortowanie, jak na stosie, jest wystarczające. Zobacz odpowiedź Rona Tellera.
Christopher Creutzig

1
Tak, po cichu założyłem, że kolejka wyodrębniania-min jest zaimplementowana jako sterta.
Regenschein,

Zamiast kolejki kołowej używaj sterty min o rozmiarze 100, będzie ona miała co najmniej sto liczb na górze. To zajmie tylko O ​​(log n) do wstawienia w porównaniu do o (n) w przypadku kolejki
techExplorer

33

Uświadomiłem sobie, że jest to oznaczone „algorytmem”, ale wyrzuci kilka innych opcji, ponieważ prawdopodobnie powinien być również oznaczony jako „wywiad”.

Jakie jest źródło 1 miliarda liczb? Jeśli jest to baza danych, wówczas „wybierz wartość z tabeli według wartości desc limit 100” wykona zadanie całkiem nieźle - mogą występować różnice w dialektach.

Czy to jednorazowe, czy coś, co się powtórzy? Jeśli powtórzone, jak często? Jeśli jest to jednorazowe, a dane znajdują się w pliku, to „cat srcfile | sortuj (opcje w razie potrzeby) | head -100 'sprawi, że szybko wykonasz produktywną pracę, za którą otrzymujesz wynagrodzenie, podczas gdy komputer zajmuje się tym trywialnym obowiązkiem.

Jeśli się powtórzy, radzisz wybrać jakieś przyzwoite podejście, aby uzyskać wstępną odpowiedź i przechowywać / buforować wyniki, abyś mógł ciągle być w stanie zgłosić 100 najlepszych.

Wreszcie jest taka uwaga. Szukasz pracy na poziomie podstawowym i rozmowy z naukowym kierownikiem lub przyszłym współpracownikiem? Jeśli tak, możesz rzucić wiele podejść opisujących względne zalety i wady techniczne. Jeśli szukasz bardziej menedżerskiej pracy, podejdź do niej tak, jak zrobiłby to menedżer, zainteresowany kosztami opracowania i utrzymania rozwiązania, i powiedz „dziękuję bardzo” i odejdź, jeśli to osoba przeprowadzająca wywiad chce skupić się na ciekawostkach z zakresu CS . Jest mało prawdopodobne, aby on i ty mieli duży potencjał rozwoju.

Powodzenia w kolejnym wywiadzie.


2
Wyjątkowa odpowiedź. Wszyscy inni skoncentrowali się na technicznej stronie pytania, a ta odpowiedź dotyczy części biznesowej.
vbocan

2
Nigdy nie wyobrażałem sobie, że możesz podziękować i zostawić wywiad i nie czekać na jego zakończenie. Dzięki za otwarcie mojego umysłu.
UrsulRosu

1
Dlaczego nie możemy utworzyć sterty miliardów elementów i wyodrębnić 100 największych elementów. W ten sposób koszt = O (miliard) + 100 * O (log (miliard)) ??
Mohit Shah,

17

Moją natychmiastową reakcją byłoby użycie sterty, ale jest sposób na użycie QuickSelect bez trzymania pod ręką wszystkich wartości wejściowych.

Utwórz tablicę o rozmiarze 200 i wypełnij ją pierwszymi 200 wartościami wejściowymi. Uruchom QuickSelect i odrzuć niskie 100, pozostawiając ci 100 wolnych miejsc. Wczytaj kolejne 100 wartości wejściowych i ponownie uruchom QuickSelect. Kontynuuj, dopóki nie przejdziesz całego wejścia w partiach po 100.

Na koniec masz 100 najlepszych wartości. Dla N wartości uruchomiłeś QuickSelect z grubsza N / 100 razy. Każdy Quickselect kosztuje około 200 razy pewną stałą, więc całkowity koszt wynosi 2 N razy pewną stałą. Wygląda mi to liniowo w stosunku do wielkości wejściowej, bez względu na rozmiar parametru, który chcę mieć 100 w tym objaśnieniu.


10
Możesz dodać małą, ale prawdopodobnie ważną optymalizację: po uruchomieniu QuickSelect w celu podzielenia tablicy o rozmiarze 200 wiadomo minimum 100 najlepszych elementów. Następnie, podczas iteracji całego zestawu danych, wypełnij dolne 100 wartości tylko wtedy, gdy bieżąca wartość jest większa niż bieżące minimum. Prosta implementacja tego algorytmu w C ++ jest na równi z działaniem libstdc ++ partial_sortbezpośrednio na zestawie danych 200 milionów 32-bitów int(utworzonych przez MT19937, równomiernie rozproszonych).
wtorek,

1
Dobry pomysł - nie wpływa na analizę najgorszego przypadku, ale wydaje się warty zrobienia.
mcdowella,

@mcdowella Warto spróbować i zrobię to, dzięki!
userx

8
To właśnie robi Guava Ordering.greatestOf(Iterable, int) . Jest absolutnie liniowy w czasie i jednoprzebiegowy i jest super uroczym algorytmem. FWIW, mamy również kilka rzeczywistych punktów odniesienia: jej stałe czynniki są o włos wolniejsze niż tradycyjna kolejka priorytetowa w przeciętnym przypadku, ale ta implementacja jest znacznie bardziej odporna na dane wejściowe „najgorszego przypadku” (np. Dane wejściowe ściśle rosnące).
Louis Wasserman,

15

Możesz użyć algorytmu szybkiego wyboru, aby znaleźć liczbę o indeksie (według kolejności) [miliard-101], a następnie iterować liczby i znaleźć liczby większe od tej liczby.

array={...the billion numbers...} 
result[100];

pivot=QuickSelect(array,billion-101);//O(N)

for(i=0;i<billion;i++)//O(N)
   if(array[i]>=pivot)
      result.add(array[i]);

Ten algorytm Czas wynosi: 2 XO (N) = O (N) (Średnia wydajność sprawy)

Druga opcja, jak sugeruje Thomas Jungblut , to:

Użyj Sterty, budowanie sterty MAKS zajmie O (N), następnie 100 najlepszych liczb maksymalnych znajdzie się na górze Sterty, wszystko czego potrzebujesz to wyciągnięcie ich ze sterty (100 XO (Log (N)).

Ten algorytm Czas wynosi: O (N) + 100 XO (Log (N)) = O (N)


8
Trzy razy przeglądasz całą listę. 1 bio. liczby całkowite to w przybliżeniu 4 GB, co byś zrobił, gdybyś nie mógł zmieścić ich w pamięci? Quickselect to w tym przypadku najgorszy możliwy wybór. Iterowanie raz i utrzymywanie sterty 100 najlepszych pozycji to IMHO najlepiej działające rozwiązanie w O (n) (zwróć uwagę, że możesz odciąć O (log n) wstawek sterty, ponieważ n na stercie wynosi 100 = stała = bardzo mała ).
Thomas Jungblut,

3
Mimo tego, że O(N)wykonanie dwóch QuickSelectów i kolejnego skanowania liniowego jest znacznie większe niż potrzeba.
Kevin

To jest kod PSEUDO, wszystkie rozwiązania tutaj zajmą więcej czasu (O (NLOG (N) lub 100 * O (N))
One Man Crew

1
100*O(N)(jeśli jest to poprawna składnia) = O(100*N)= O(N)(wprawdzie 100 może być zmienną, jeśli tak, to nie jest to do końca prawda). Aha, a Quickselect ma najgorsze działanie O (N ^ 2) (ouch). A jeśli nie zmieści się w pamięci, przeładujesz dane z dysku dwukrotnie, co jest o wiele gorsze niż raz (jest to wąskie gardło).
Bernhard Barker,

Problem polega na tym, że jest to oczekiwany czas działania, a nie najgorszy przypadek, ale przy użyciu przyzwoitej strategii wyboru osi przestawnej (np. Wybierz losowo 21 elementów i wybierz medianę tych 21 jako oś przestawną), wówczas można porównać liczbę porównań z dużym prawdopodobieństwem gwarantowane co najwyżej (2 + c) n dla arbitralnie małej stałej c.
One Man Crew,

10

Mimo że inne rozwiązanie szybkiego wyboru zostało odrzucone, pozostaje faktem, że quickselect znajdzie rozwiązanie szybciej niż przy użyciu kolejki o rozmiarze 100. Oczekiwany czas działania Quickselect wynosi 2n + o (n), jeśli chodzi o porównania. Byłoby to bardzo proste wdrożenie

array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

To zajmie średnio porównania 3n + o (n). Co więcej, można go usprawnić, korzystając z faktu, że szybkie wybranie pozostawi 100 największych elementów w tablicy w 100 najbardziej po prawej stronie. Tak więc czas działania można poprawić do 2n + o (n).

Problem polega na tym, że jest to oczekiwany czas działania, a nie najgorszy przypadek, ale przy użyciu przyzwoitej strategii wyboru osi przestawnych (np. Wybierz losowo 21 elementów i wybierz medianę tych 21 jako oś przestawną), wówczas można porównać liczbę porównań z dużym prawdopodobieństwem gwarantowane co najwyżej (2 + c) n dla arbitralnie małej stałej c.

W rzeczywistości, stosując zoptymalizowaną strategię próbkowania (np. Losowo próbkuj elementy sqrt (n) i wybierz 99. percentyl), czas działania można sprowadzić do (1 + c) n + o (n) dla dowolnie małego c (zakładając, że K, liczba elementów do wyboru wynosi o (n)).

Z drugiej strony użycie kolejki o rozmiarze 100 będzie wymagało porównań O (log (100) n), a podstawa logarytmu 2 wynosząca 100 jest w przybliżeniu równa 6,6.

Jeśli pomyślimy o tym problemie w bardziej abstrakcyjnym sensie wyboru największych elementów K z tablicy o rozmiarze N, gdzie K = o (N), ale zarówno K, jak i N idą w nieskończoność, to czas działania wersji szybkiego wyboru będzie wynosić O (N) i wersją kolejki będzie O (N log K), więc w tym sensie szybkie wybieranie jest również asymptotycznie lepsze.

W komentarzach wspomniano, że rozwiązanie kolejki będzie działać w oczekiwanym czasie N + K log N na losowym wejściu. Oczywiście założenie losowego wejścia nigdy nie jest ważne, chyba że pytanie wyraźnie to określa. Rozwiązanie kolejki można wykonać w taki sposób, aby przechodzić przez tablicę w losowej kolejności, ale spowoduje to dodatkowy koszt N wywołań do generatora liczb losowych, jak również albo permutowanie całej tablicy wejściowej, albo przydzielenie nowej tablicy o długości N zawierającej losowe wskaźniki.

Jeśli problem nie pozwala na poruszanie się po elementach w oryginalnej tablicy, a koszt alokacji pamięci jest wysoki, więc duplikowanie tablicy nie jest opcją, to inna sprawa. Ale ściśle pod względem czasu działania jest to najlepsze rozwiązanie.


4
Ostatni akapit jest kluczowy: przy miliardowych liczbach nie jest możliwe przechowywanie wszystkich danych w pamięci ani zamiana elementów. (Przynajmniej tak interpretowałbym problem, biorąc pod uwagę, że było to pytanie do wywiadu.)
Ted Hopp,

14
W każdym pytaniu algorytmicznym, jeśli odczyt danych stanowi problem, należy o tym wspomnieć w pytaniu. Pytanie brzmi: „dana tablica” nie „dana tablica na dysku, która nie mieści się w pamięci i nie można nią manipulować zgodnie z modelem von neumana, który jest standardem w analizie algorytmów”. Obecnie możesz kupić laptopa z 8 gramami pamięci ram. Nie jestem pewien, skąd wziął się pomysł trzymania w pamięci miliarda liczb. W tej chwili mam w pamięci kilka miliardów liczb.
mrip

FYI Środowisko uruchomieniowe szybkiego wybierania to O (n ^ 2) (patrz en.wikipedia.org/wiki/Quickselect ), a także modyfikuje kolejność elementów w tablicy wejściowej. Możliwe jest zastosowanie najgorszego rozwiązania O (n) z bardzo dużą stałą ( en.wikipedia.org/wiki/Median_of_medians ).
pkt

Najgorszy przypadek szybkiego wyboru jest mało prawdopodobny, co oznacza, że ​​ze względów praktycznych nie ma to znaczenia. Łatwo jest zmodyfikować szybki wybór, aby z dużym prawdopodobieństwem liczba porównań wynosiła (2 + c) n + o (n) dla dowolnie małego c.
mrip

„pozostaje faktem, że szybkie wybieranie znajdzie rozwiązanie szybciej niż przy użyciu kolejki o rozmiarze 100” - Nie. Rozwiązanie hałdy wymaga porównań N + Klog (N) w porównaniu ze średnią 2N dla szybkiego wyboru i 2,95 dla mediany median. Jest wyraźnie szybszy dla danego K.
Neil G

5

weź pierwsze 100 liczb miliarda i posortuj je. teraz po prostu iteruj przez miliard, jeśli liczba źródłowa jest większa niż najmniejsza ze 100, wstaw w porządku sortowania. To, co kończysz, jest czymś znacznie bliższym O (n) niż rozmiar zestawu.


3
Ups, nie widziałem bardziej szczegółowej odpowiedzi niż moja.
Samuel Thurston,

Weź 500 pierwszych liczb i zatrzymaj się, aby posortować (i wyrzuć niskie 400), gdy lista się zapełni. (I nie trzeba dodawać, że dodajesz do listy tylko wtedy, gdy nowy numer jest> najniższy w wybranym 100.)
Hot Licks

4

Dwie opcje:

(1) Sterta (PriorQueue)

Zachowaj stertę min o wielkości 100. Przejdź przez tablicę. Gdy element będzie mniejszy niż pierwszy element w stercie, wymień go.

InSERT ELEMENT INTO HEAP: O(log100)
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2) Model zmniejszania mapy.

Jest to bardzo podobne do przykładu liczby słów w hadoopie. Zadanie mapy: policz częstotliwość lub czasy pojawienia się każdego elementu. Zmniejsz: zdobądź najwyższy element K.

Zwykle dawałbym rekruterowi dwie odpowiedzi. Daj im, co im się podoba. Oczywiście kodowanie map redukujących byłoby pracochłonne, ponieważ musisz znać wszystkie dokładne parametry. Nie zaszkodzi ćwiczyć. Powodzenia.


+1 za MapReduce, nie mogę uwierzyć, że jako jedyny wspominałeś o Hadoopie dla miliarda liczb. Co jeśli ankieter poprosił o 1 miliard numerów? Moim zdaniem zasługujesz na więcej głosów.
Silviu Burcea

@Silviu Burcea Wielkie dzięki. Cenię też MapReduce. :)
Chris Su

Chociaż rozmiar 100 jest stały w tym przykładzie, naprawdę powinieneś uogólnić to na osobną zmienną, tj. k. Skoro 100 jest równe 1 miliardowi, to dlaczego podajesz rozmiar dużego zestawu liczb zmienną wielkości n, a nie mniejszy zestaw liczb? Naprawdę twoją złożonością powinno być O (nlogk), które nie jest O (n).
Tom Heard,

1
Ale chodzi mi o to, że jeśli tylko odpowiadasz na pytanie, 1 miliard jest również ustalony w pytaniu, więc po co uogólniać 1 miliard na n, a nie 100 na k. Zgodnie z twoją logiką złożoność powinna w rzeczywistości wynosić O (1), ponieważ zarówno 1 miliard, jak i 100 są ustalone w tym pytaniu.
Tom Heard

1
@TomHeard W porządku. O (nlogk) Jest tylko jeden czynnik, który wpłynie na wyniki. Oznacza to, że jeśli n rośnie coraz bardziej, „poziom wyniku” będzie wzrastał liniowo. Albo możemy powiedzieć, że nawet biorąc pod uwagę tryliony liczb, wciąż mogę uzyskać 100 największych liczb. Jednak nie można powiedzieć: Wraz ze wzrostem n, k wzrasta, więc k wpłynie na wynik. Dlatego używam O (nlogk), ale nie O (nlogn)
Chris Su

4

Bardzo łatwym rozwiązaniem byłoby iterowanie tablicy 100 razy. Co jest O(n).

Za każdym razem, gdy wyciągniesz największą liczbę (i zmienisz jej wartość na wartość minimalną, aby nie było jej widać w następnej iteracji, lub śledzisz indeksy poprzednich odpowiedzi (śledząc indeksy, oryginalna tablica może mieć wielokrotność tego samego numeru)). Po 100 iteracjach masz 100 największych liczb.


1
Dwie wady - (1) Niszczysz dane wejściowe w procesie - najlepiej tego uniknąć. (2) Przeglądasz tablicę wiele razy - jeśli tablica jest przechowywana na dysku i nie mieści się w pamięci, może to być prawie 100 razy wolniejsze niż zaakceptowana odpowiedź. (Tak, oba są O (n), ale nadal)
Bernhard Barker

Dobry telefon @Dukeling, dodałem dodatkowe sformułowanie, jak uniknąć zmiany oryginalnego wkładu poprzez śledzenie poprzednich wskaźników odpowiedzi. Co nadal byłoby dość łatwe do zakodowania.
James Oravec

Genialny przykład rozwiązania O (n), które jest znacznie wolniejsze niż O (n log n). log2 (1 miliard) to tylko 30 ...
gnasher729

@ gnasher729 Jak duża jest stała ukryta w O (n log n)?
miracle173

1

Zainspirowany odpowiedzią narratora @ron, oto podstawowy program C do robienia tego, co chcesz.

#include <stdlib.h>
#include <stdio.h>

#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100

int 
compare_function(const void *first, const void *second)
{
    int a = *((int *) first);
    int b = *((int *) second);
    if (a > b){
        return 1;
    }
    if (a < b){
        return -1;
    }
    return 0;
}

int 
main(int argc, char ** argv)
{
    if(argc != 2){
        printf("please supply a path to a binary file containing 1000000000"
               "integers of this machine's wordlength and endianness\n");
        exit(1);
    }
    FILE * f = fopen(argv[1], "r");
    if(!f){
        exit(1);
    }
    int top100[N_TOP_NUMBERS] = {0};
    int sorts = 0;
    for (int i = 0; i < TOTAL_NUMBERS; i++){
        int number;
        int ok;
        ok = fread(&number, sizeof(int), 1, f);
        if(!ok){
            printf("not enough numbers!\n");
            break;
        }
        if(number > top100[0]){
            sorts++;
            top100[0] = number;
            qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
        }

    }
    printf("%d sorts made\n"
    "the top 100 integers in %s are:\n",
    sorts, argv[1] );
    for (int i = 0; i < N_TOP_NUMBERS; i++){
        printf("%d\n", top100[i]);
    }
    fclose(f);
    exit(0);
}

Na mojej maszynie (rdzeń i3 z szybkim dyskiem SSD) zajmuje to 25 sekund, a sortowanie 1724. Wygenerowałem plik binarny dd if=/dev/urandom/ count=1000000000 bs=1dla tego uruchomienia.

Oczywiście występują problemy z wydajnością odczytu tylko 4 bajtów naraz - z dysku, ale jest to na przykład dla dobra. Zaletą jest bardzo mało pamięci.


1

Najprostszym rozwiązaniem jest zeskanowanie dużej tablicy miliardów liczb i przechowywanie 100 największych wartości znalezionych do tej pory w buforze małej tablicy bez sortowania i zapamiętanie najmniejszej wartości tego bufora. Najpierw pomyślałem, że ta metoda została zaproponowana przez fordprefect, ale w komentarzu powiedział, że zakłada, że ​​struktura danych o liczbie 100 jest implementowana jako sterta. Ilekroć zostanie znaleziony nowy numer, który jest większy, minimum w buforze zostanie zastąpione nową znalezioną wartością i bufor zostanie ponownie przeszukany pod kątem aktualnego minimum. Jeśli liczby w miliardowej tablicy liczb są przez większość czasu losowo rozmieszczane, wartość z dużej tablicy jest porównywana z minimum małej tablicy i odrzucana. Tylko dla bardzo małej części liczby wartość należy wstawić do małej tablicy. Różnicę w manipulowaniu strukturą danych zawierającą małe liczby można więc pominąć. W przypadku niewielkiej liczby elementów trudno jest ustalić, czy użycie kolejki priorytetowej jest rzeczywiście szybsze niż użycie mojego naiwnego podejścia.

Chcę oszacować liczbę wstawek w małym 100-elementowym buforze tablicy, gdy skanowana jest tablica 10 ^ 9 elementów. Program skanuje pierwsze 1000 elementów tej dużej tablicy i musi wstawić maksymalnie 1000 elementów do bufora. Bufor zawiera 100 elementów z 1000 skanowanych elementów, czyli 0,1 skanowanego elementu. Zakładamy więc, że prawdopodobieństwo, że wartość z dużej tablicy jest większa niż bieżące minimum bufora, wynosi około 0,1. Taki element należy wstawić do bufora. Teraz program skanuje kolejne 10 ^ 4 elementów z dużej tablicy. Ponieważ minimum bufora wzrośnie za każdym razem, gdy wstawiany jest nowy element. Oszacowaliśmy, że stosunek elementów większych niż nasze obecne minimum wynosi około 0,1, a więc do wstawienia jest 0,1 * 10 ^ 4 = 1000 elementów. W rzeczywistości oczekiwana liczba elementów wstawianych do bufora będzie mniejsza. Po zeskanowaniu tego 10 ^ 4 elementów ułamek liczb w buforze będzie wynosił około 0,01 skanowanych do tej pory elementów. Zatem podczas skanowania kolejnych 10 ^ 5 liczb przyjmujemy, że do bufora zostanie wstawionych nie więcej niż 0,01 * 10 ^ 5 = 1000. Kontynuując tę ​​argumentację, wstawiliśmy około 7000 wartości po skanowaniu 1000 + 10 ^ 4 + 10 ^ 5 + ... + 10 ^ 9 ~ 10 ^ 9 elementów dużej tablicy. Zatem podczas skanowania tablicy z 10 ^ 9 elementami o losowym rozmiarze oczekujemy nie więcej niż 10 ^ 4 (= 7000 zaokrąglonych w górę) wstawek w buforze. Po każdym wstawieniu do bufora należy znaleźć nowe minimum. Jeśli bufor jest prostą tablicą, potrzebujemy 100 porównań, aby znaleźć nowe minimum. Jeśli bufor jest inną strukturą danych (np. Stertą), potrzebujemy co najmniej 1 porównania, aby znaleźć minimum. Aby porównać elementy dużej tablicy, potrzebujemy porównań 10 ^ 9. Podsumowując, potrzebujemy około 10 ^ 9 + 100 * 10 ^ 4 = 1,001 * 10 ^ 9 porównań przy użyciu tablicy jako bufora i co najmniej 1.000 * 10 ^ 9 porównań przy użyciu innego rodzaju struktury danych (np. Sterty) . Zatem użycie sterty przynosi tylko 0,1% przyrostu, jeśli wydajność zależy od liczby porównań. Ale jaka jest różnica w czasie wykonywania między wstawieniem elementu do sterty 100 elementów a zastąpieniem elementu w tablicy 100 elementów i znalezieniem nowego minimum? Porównania 000 * 10 ^ 9 w przypadku korzystania z innego rodzaju struktury danych (np. Sterty). Zatem użycie sterty przynosi tylko 0,1% przyrostu, jeśli wydajność zależy od liczby porównań. Ale jaka jest różnica w czasie wykonywania między wstawieniem elementu do sterty 100 elementów a zastąpieniem elementu w tablicy 100 elementów i znalezieniem nowego minimum? Porównania 000 * 10 ^ 9 w przypadku korzystania z innego rodzaju struktury danych (np. Sterty). Zatem użycie sterty przynosi tylko 0,1% przyrostu, jeśli wydajność zależy od liczby porównań. Ale jaka jest różnica w czasie wykonywania między wstawieniem elementu do sterty 100 elementów a zastąpieniem elementu w tablicy 100 elementów i znalezieniem nowego minimum?

  • Na poziomie teoretycznym: ile porównań jest potrzebnych do wstawienia do stosu. Wiem, że jest to O (log (n)), ale jak duży jest stały współczynnik? ja

  • Na poziomie maszyny: Jaki jest wpływ buforowania i przewidywania rozgałęzień na czas wykonania wstawki sterty i wyszukiwania liniowego w tablicy.

  • Na poziomie wdrożenia: Jakie dodatkowe koszty są ukryte w strukturze danych sterty dostarczanej przez bibliotekę lub kompilator?

Myślę, że to niektóre z pytań, na które należy odpowiedzieć, zanim będzie można spróbować oszacować rzeczywistą różnicę między wydajnością stosu 100 elementów lub tablicy 100 elementów. Sensowne byłoby więc przeprowadzenie eksperymentu i zmierzenie rzeczywistej wydajności.


1
Tak robi kupa.
Neil G,

@Neil G: Co to jest?
miracle173

1
Górna część sterty jest minimalnym elementem w sterty, a nowe elementy są odrzucane za pomocą jednego porównania.
Neil G,

1
Rozumiem, co mówisz, ale nawet jeśli porównujesz bezwzględną liczbę porównań zamiast asymptotycznej liczby porównań, tablica jest nadal znacznie wolniejsza, ponieważ czas na „wstawienie nowego elementu, odrzucenie starego minimum i znalezienie nowego minimum” wynosi 100 zamiast około 7.
Neil G

1
Okej, ale twój szacunek jest bardzo okrągły. Możesz bezpośrednio obliczyć oczekiwaną liczbę wstawek, które mają być k (digamma (n) - digamma (k)), która jest mniejsza niż klog (n). W każdym razie zarówno rozwiązanie sterty, jak i macierz wydają tylko jedno porównanie, aby odrzucić element. Jedyną różnicą jest to, że liczba porównań dla wstawionego elementu wynosi 100 dla twojego rozwiązania w porównaniu do 14 dla stosu (chociaż średni przypadek jest prawdopodobnie znacznie mniejszy.)
Neil G

1
 Although in this question we should search for top 100 numbers, I will 
 generalize things and write x. Still, I will treat x as constant value.

Algorytm Największe x elementów od n:

Wywołam wartość zwracaną LISTĘ . Jest to zestaw elementów x (moim zdaniem powinna być połączona lista)

  • Pierwsze x elementów jest pobieranych z puli „jak przychodzą” i sortowane w LISTY (odbywa się to w stałym czasie, ponieważ x jest traktowany jako stały - czas O (x log (x)))
  • Dla każdego następnego elementu sprawdzamy, czy jest większy niż najmniejszy element na LIŚCIE i czy wyskakujemy najmniejszy i wstawiamy bieżący element do LISTY. Ponieważ jest to uporządkowana lista, każdy element powinien znaleźć swoje miejsce w czasie logarytmicznym (wyszukiwanie binarne), a ponieważ jest uporządkowana, wstawienie listy nie stanowi problemu. Każdy krok odbywa się również w stałym czasie (czas O (log (x))).

Jaki jest najgorszy scenariusz?

x log (x) + (nx) (log (x) +1) = nlog (x) + n - x

To jest czas O (n) w najgorszym przypadku. +1 oznacza sprawdzenie, czy liczba jest większa niż najmniejsza z LISTY. Oczekiwany czas dla przeciętnego przypadku będzie zależeć od matematycznego rozkładu tych n elementów.

Możliwe ulepszenia

Algorytm ten można nieco ulepszyć w najgorszym przypadku, ale IMHO (nie mogę udowodnić tego twierdzenia), który obniży średnie zachowanie. Zachowanie asymptotyczne będzie takie samo.

Ulepszenie w tym algorytmie polega na tym, że nie sprawdzimy, czy element jest większy niż najmniejszy. Dla każdego elementu spróbujemy go wstawić, a jeśli będzie mniejszy niż najmniejszy, zignorujemy go. Chociaż brzmi to niedorzecznie, jeśli weźmiemy pod uwagę tylko najgorszy możliwy scenariusz

x log (x) + (nx) log (x) = nlog (x)

operacje.

W tym przypadku użycia nie widzę żadnych dalszych ulepszeń. Jednak musisz zadać sobie pytanie - co jeśli będę musiał to zrobić więcej niż log (n) razy i dla różnych x-es? Oczywiście sortowalibyśmy tę tablicę w O (n log (n)) i bierzemy nasz element x, gdy tylko będziemy go potrzebować.


1

Odpowiedź na to pytanie byłaby złożoność N log (100) (zamiast N log N) za pomocą tylko jednego wiersza kodu C ++.

 std::vector<int> myvector = ...; // Define your 1 billion numbers. 
                                 // Assumed integer just for concreteness 
 std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());

Ostateczną odpowiedzią byłby wektor, w którym pierwszych 100 elementów ma zagwarantowane 100 największych liczb z twojej tablicy, podczas gdy pozostałe elementy są nieuporządkowane

C ++ STL (biblioteka standardowa) jest dość przydatny przy tego rodzaju problemach.

Uwaga: nie mówię, że jest to optymalne rozwiązanie, ale uratowałoby to twój wywiad.


1

Prostym rozwiązaniem byłoby użycie kolejki priorytetowej, dodanie pierwszych 100 liczb do kolejki i śledzenie najmniejszej liczby w kolejce, a następnie iterowanie kolejnych miliardów liczb, i za każdym razem znajdziemy jedną, która jest większa od największej liczby w kolejce priorytetowej usuwamy najmniejszą liczbę, dodajemy nowy numer i ponownie śledzimy najmniejszą liczbę w kolejce.

Gdyby liczby były w kolejności losowej, działałoby to pięknie, ponieważ podczas iteracji przez miliard liczb losowych bardzo rzadko zdarza się, aby następna liczba była wśród 100 największych jak dotąd. Ale liczby mogą nie być losowe. Jeśli tablica została już posortowana w porządku rosnącym, to zawsze wstawilibyśmy element do kolejki priorytetowej.

Więc najpierw wybieramy powiedzmy 100 000 losowych liczb z tablicy. Aby uniknąć losowego dostępu, który może być powolny, dodajemy powiedzmy 400 losowych grup po 250 kolejnych liczb. Dzięki temu losowemu wyborowi możemy być całkiem pewni, że bardzo niewiele pozostałych liczb znajduje się w pierwszej setce, więc czas wykonania będzie bardzo zbliżony do czasu prostej pętli porównującej miliard liczb z pewną maksymalną wartością.


1

Znalezienie 100 najlepszych z miliarda liczb najlepiej jest wykonać przy użyciu min-sterty 100 elementów.

Najpierw zalej minimum stos z pierwszymi 100 napotkanymi liczbami. min-heap zapisze najmniejszą z pierwszych 100 liczb w katalogu głównym (u góry).

Teraz, gdy będziesz postępować zgodnie z pozostałymi liczbami, porównaj je tylko z pierwiastkiem (najmniejszym ze 100).

Jeśli nowy napotkany numer jest większy od katalogu głównego stosu min, wymień katalog główny na ten numer, w przeciwnym razie zignoruj ​​go.

W ramach wstawiania nowego numeru do stosu min, najmniejsza liczba w stosie dojdzie na górę (root).

Gdy przejdziemy przez wszystkie liczby, będziemy mieli 100 największych liczb w min-stosie.


0

Napisałem proste rozwiązanie w Pythonie na wypadek, gdyby ktoś był zainteresowany. Wykorzystujebisect moduł i tymczasową listę zwrotną, którą przechowuje. Jest to podobne do implementacji kolejki priorytetowej.

import bisect

def kLargest(A, k):
    '''returns list of k largest integers in A'''
    ret = []
    for i, a in enumerate(A):
        # For first k elements, simply construct sorted temp list
        # It is treated similarly to a priority queue
        if i < k:
            bisect.insort(ret, a) # properly inserts a into sorted list ret
        # Iterate over rest of array
        # Replace and update return array when more optimal element is found
        else:
            if a > ret[0]:
                del ret[0] # pop min element off queue
                bisect.insort(ret, a) # properly inserts a into sorted list ret
    return ret

Użycie ze 100 000 000 elementów i najgorsze dane wejściowe, które są posortowaną listą:

>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
 99999996, 99999997, 99999998, 99999999]

Obliczenie tego dla 100 000 000 elementów zajęło około 40 sekund, więc boję się tego za 1 miliard. Szczerze mówiąc, zasilałem go najgorszym wejściem (jak na ironię macierz, która jest już posortowana).


0

Widzę wiele dyskusji na temat O (N), więc proponuję coś innego tylko dla ćwiczenia myślenia.

Czy są znane informacje na temat charakteru tych liczb? Jeśli ma charakter losowy, nie idź dalej i spójrz na inne odpowiedzi. Nie uzyskasz lepszych rezultatów niż oni.

Jednak! Sprawdź, czy jakikolwiek mechanizm zapełniający listę zapełnił tę listę w określonej kolejności. Czy mają dobrze zdefiniowany wzór, w którym można z całą pewnością wiedzieć, że największa liczba liczb znajdzie się w określonym regionie listy lub w określonym przedziale czasu? Może to być wzór. Jeśli tak jest, na przykład, jeśli gwarantuje się, że są w jakimś normalnym rozkładzie z charakterystycznym garbem pośrodku, zawsze powtarzają się tendencje wzrostowe wśród zdefiniowanych podzbiorów, mają przedłużony skok w pewnym momencie T w środku danych ustawione na przykład jako przypadek wykorzystania informacji poufnych lub awarii sprzętu, a może po prostu „skok” co N-tą liczbę, ponieważ w analizie sił po katastrofie możesz znacznie zmniejszyć liczbę rekordów, które musisz sprawdzić.

W każdym razie jest trochę do przemyślenia. Być może pomoże to w udzieleniu przyszłej ankiecie przemyślanej odpowiedzi. Wiem, że byłbym pod wrażeniem, gdyby ktoś zadał mi takie pytanie w odpowiedzi na taki problem - powiedziałby mi, że myśli o optymalizacji. Po prostu zauważ, że nie zawsze może istnieć możliwość optymalizacji.


0
Time ~ O(100 * N)
Space ~ O(100 + N)
  1. Utwórz pustą listę 100 pustych miejsc

  2. Dla każdej liczby na liście wejść:

    • Jeśli liczba jest mniejsza niż pierwsza, pomiń

    • W przeciwnym razie zastąp go tym numerem

    • Następnie przepchnij numer przez sąsiednią zamianę; aż będzie mniejszy niż następny

  3. Zwróć listę


Uwaga: jeśli log(input-list.size) + c < 100, to optymalnym sposobem jest posortowanie listy danych wejściowych, a następnie podziel 100 pierwszych pozycji.


0

Złożoność to O (N)

Najpierw utwórz tablicę o wartości początkowej 100 intszeze pierwszy element tej tablicy jako pierwszy element wartości N, śledź indeks bieżącego elementu za pomocą innej zmiennej, nazwij go CurrentBig

Iteruj przez wartości N.

if N[i] > M[CurrentBig] {

M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)

CurrentBig++;      ( go to the next position in the M array)

CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)

M[CurrentBig]=N[i];    ( pick up the current value again to use it for the next Iteration of the N array)

} 

po zakończeniu wydrukuj tablicę M z CurrentBig 100 razy modulo 100 :-) Dla ucznia: upewnij się, że ostatni wiersz kodu nie przebija prawidłowych danych tuż przed wyjściem kodu


0

Kolejny algorytm O (n) -

Algorytm znajduje największą 100 poprzez eliminację

rozważ wszystkie miliony liczb w ich reprezentacji binarnej. Zacznij od najbardziej znaczącego fragmentu. Ustalenie, czy MSB wynosi 1, można wykonać przez pomnożenie operacji logicznej przez odpowiednią liczbę. Jeśli w tym milionie jest więcej niż 100 1, wyeliminuj pozostałe liczby zerami. Teraz z pozostałych liczb przejdź do następnego najbardziej znaczącego bitu. zachowaj liczbę pozostałych liczb po wyeliminowaniu i kontynuuj tak długo, jak długo ta liczba będzie większa niż 100.

Główna operacja logiczna może być wykonywana równolegle na procesorach graficznych


0

Dowiedziałbym się, kto miał czas na umieszczenie miliarda liczb w tablicy i zwolnienie go. Musi pracować dla rządu. Przynajmniej jeśli masz połączoną listę, możesz wstawić liczbę na środek, nie ruszając pół miliarda, aby zrobić miejsce. Jeszcze lepiej Btree pozwala na wyszukiwanie binarne. Każde porównanie eliminuje połowę całości. Algorytm skrótu pozwala zapełnić strukturę danych jak szachownica, ale nie tak dobry dla rzadkich danych. Ponieważ najlepiej jest mieć tablicę rozwiązań zawierającą 100 liczb całkowitych i śledzić najniższą liczbę w tablicy rozwiązań, aby można ją było zastąpić, gdy znajdziesz wyższą liczbę w tablicy oryginalnej. Będziesz musiał spojrzeć na każdy element w oryginalnej tablicy, zakładając, że nie jest on posortowany na początek.


0

Możesz to zrobić na O(n)czas. Po prostu iteruj po liście i śledź 100 największych liczb, które widziałeś w danym punkcie i minimalną wartość w tej grupie. Gdy znajdziesz nową liczbę większą niż najmniejsza z dziesięciu, zastąp ją i zaktualizuj nową minimalną wartość 100 (może to zająć stały czas 100, aby ustalić to za każdym razem, gdy to zrobisz, ale nie wpływa to na ogólną analizę ).


1
Podejście to jest prawie identyczne z odpowiedzią na to pytanie zarówno najbardziej, jak i drugą pod względem popularności.
Bernhard Barker,

0

Zarządzanie osobną listą to dodatkowa praca i za każdym razem, gdy znajdziesz inną, musisz przenosić różne elementy całej listy. Po prostu posortuj go i weź 100 najlepszych.


-1 szybkisort to O (n log n), czyli dokładnie to, co zrobił OP i prosi o ulepszenie. Nie musisz zarządzać osobną listą, a jedynie listą 100 liczb. Twoja sugestia ma również niepożądany efekt uboczny polegający na zmianie oryginalnej listy lub skopiowaniu jej. To już 4GiB pamięci.

0
  1. Użyj n-tego elementu, aby uzyskać 100-ty element O (n)
  2. Powtórz drugi raz, ale tylko raz i wypisz każdy element, który jest większy niż ten konkretny element.

Uwaga esp. drugi krok może być łatwy do obliczenia równoległego! I będzie również efektywnie, gdy będziesz potrzebować miliona największych elementów.


0

To pytanie zadane przez Google lub innych gigantów branży. Być może poniższy kod jest właściwą odpowiedzią, jakiej oczekuje Twój ankieter. Koszt czasu i koszt miejsca zależą od maksymalnej liczby w tablicy wejściowej. Dla 32-bitowego wejścia int tablicy Maksymalny koszt miejsca to 4 * 125 mln bajtów, koszt czasu to 5 * miliardów.

public class TopNumber {
    public static void main(String[] args) {
        final int input[] = {2389,8922,3382,6982,5231,8934
                            ,4322,7922,6892,5224,4829,3829
                            ,6892,6872,4682,6723,8923,3492};
        //One int(4 bytes) hold 32 = 2^5 value,
        //About 4 * 125M Bytes
        //int sort[] = new int[1 << (32 - 5)];
        //Allocate small array for local test
        int sort[] = new int[1000];
        //Set all bit to 0
        for(int index = 0; index < sort.length; index++){
            sort[index] = 0;
        }
        for(int number : input){
            sort[number >>> 5] |= (1 << (number % 32));
        }
        int topNum = 0;
        outer:
        for(int index = sort.length - 1; index >= 0; index--){
            if(0 != sort[index]){
                for(int bit = 31; bit >= 0; bit--){
                    if(0 != (sort[index] & (1 << bit))){
                        System.out.println((index << 5) + bit);
                        topNum++;
                        if(topNum >= 3){
                            break outer;
                        }
                    }
                }
            }
        }
    }
}

0

Zrobiłem własny kod, nie jestem pewien, czy to jest to, czego szuka „ankieter”

private static final int MAX=100;
 PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
        queue.add(array[0]);
        for (int i=1;i<array.length;i++)
        {

            if(queue.peek()<array[i])
            {
                if(queue.size() >=MAX)
                {
                    queue.poll();
                }
                queue.add(array[i]);

            }

        }

0

Możliwe ulepszenia.

Jeśli plik zawiera 1 miliard, odczyt może być naprawdę długi ...

Aby poprawić to działanie, możesz:

  • Podziel plik na n części, utwórz n wątków, spraw, aby n wątków szukało 100 największych liczb w swojej części pliku (przy użyciu kolejki priorytetowej), i na koniec uzyskaj 100 największych liczb ze wszystkich wyjściowych wątków.
  • Wykonaj takie zadanie za pomocą klastra z rozwiązaniem takim jak hadoop. Tutaj możesz podzielić plik jeszcze bardziej i uzyskać wynik szybciej dla pliku o wartości 1 miliarda (lub 10 ^ 12).

0

Najpierw weź 1000 elementów i dodaj je na stosie. Teraz wyjmij pierwsze maksymalnie 100 elementów i przechowuj je gdzieś. Teraz wybierz kolejne 900 elementów z pliku i dodaj je do sterty wraz z ostatnim 100 najwyższym elementem.

Powtarzaj ten proces pobierania 100 elementów ze sterty i dodawania 900 elementów z pliku.

Ostateczny wybór 100 elementów da nam maksymalnie 100 elementów z miliarda liczb.


-1

Problem: Znajdź m największych elementów n przedmiotów, gdzie n >>> m

Najprostszym rozwiązaniem, które powinno być oczywiste dla wszystkich, jest po prostu wykonanie kilku kroków algorytmu sortowania bąbelkowego.

następnie wydrukuj ostatnie n elementów tablicy.

Nie wymaga to żadnych zewnętrznych struktur danych i wykorzystuje algorytm, który wszyscy znają.

Szacowany czas pracy wynosi O (m * n). Najlepsze jak dotąd odpowiedzi to O (n log (m)), więc to rozwiązanie nie jest znacznie droższe dla małego m.

Nie twierdzę, że nie można tego poprawić, ale jest to zdecydowanie najprostsze rozwiązanie.


1
Brak zewnętrznych struktur danych? Co z miliardową tablicą liczb do posortowania? Tablica tego rozmiaru jest ogromnym nakładem czasowym zarówno do wypełnienia, jak i miejsca do przechowywania. Co jeśli wszystkie „duże” liczby znajdowały się na niewłaściwym końcu tablicy? Potrzebowałbyś rzędu 100 miliardów swapów, aby „spulchnić” je w odpowiednie miejsce - kolejne duże obciążenie… W końcu M N = 100 miliardów vs M Log2 (N) = 6,64 miliarda, co stanowi prawie dwa rzędy różnicy wielkości. Może jeszcze raz pomyśl o tym. Jednoprzebiegowe skanowanie przy jednoczesnym zachowaniu struktury danych o największej liczbie pozwoli znacznie wykonać to podejście.
NealB
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.