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

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?

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:

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

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

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.

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.

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.

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.

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)

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.

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.

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.

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.

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.

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.

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

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.

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

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.

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

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.

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.

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

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

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.

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ę ).

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

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

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

            }

        }

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

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.

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.