Jak uzyskać największe liczby z dużej liczby liczb?

Question

Chciałbym uzyskać największe 100 elementów z listy co najmniej 100000000 liczb.

Mogę posortować całą listę i po prostu wziąć ostatnie 100 elementów z posortowanej listy, ale byłoby to bardzo kosztowne zarówno pod względem pamięci, jak i czasu.

Czy istnieje jakiś łatwy, pytonowy sposób robienia tego?

To, czego chcę, to śledzenie funkcji zamiast czystego sortowania. Właściwie nie chcę tracić czasu na sortowanie elementów, które mnie nie interesują.

Na przykład, jest to funkcja chciałbym posiadać:

getSortedElements(100, lambda x,y:cmp(x,y)) 

Uwaga Ten wymóg jest tylko dla punktu widzenia wydajności.

Answer 1

Moduł heapq w bibliotece standardowej oferuje funkcję nlargest(), aby to zrobić:

top100 = heapq.nlargest(100, iterable [,key]) 

Nie będzie uszeregować całą listę, więc nie będzie tracić czasu na elementach don” t potrzeby.

Answer 2

Selection algorithms powinien pomóc tutaj.

Bardzo prostym rozwiązaniem jest znalezienie 100. największego elementu, a następnie wybieranie elementów większych niż ten element. To da ci 100 największych elementów. Jest to liniowe na całej długości listy; to jest najlepsze możliwe.

Istnieją bardziej wyrafinowane algorytmy. A heap, na przykład, jest bardzo podatny na ten problem. Algorytm oparty na sterty to n log k, gdzie n jest długością listy, a k to liczba największych elementów, które chcesz wybrać.

Istnieje dyskusja na temat tego problem na stronie Wikipedia dla algorytmów wyboru.

Edytuj: Inny plakat zwrócił uwagę, że Python ma wbudowane rozwiązanie tego problemu. Oczywiście jest to znacznie łatwiejsze niż toczenie własne, ale zachowam ten post na wypadek, gdybyś chciał się dowiedzieć, jak działają takie algorytmy.

Answer 3

Można użyć struktury danych sterty. Kupa niekoniecznie zostanie zamówiona, ale jest to dość szybki sposób przechowywania pół uporządkowanych danych, a ma ona zaletę najmniejszego elementu, zawsze będącego pierwszym elementem w stercie.

Sterty mają dwie podstawowe operacje, które pomogą Ci: Dodaj i zamień.

Zasadniczo robisz to, dodając do niego przedmioty, aż dojdziesz do 100 pozycji (twój najwyższy numer N na twoje pytanie). Następnie wymieniasz pierwszy element na każdy nowy element, o ile nowy element jest większy niż pierwszy.

Za każdym razem, gdy pierwszy przedmiot zostanie zastąpiony czymś większym, wewnętrzny kod w stercie dostosuje zawartość sterty, tak aby nowy element nie był najmniejszy, zostanie spieniony do sterty, a najmniejszy element ". "w dół" do pierwszego elementu, gotowy do wymiany po drodze.

Answer 4

Najlepszym sposobem, aby to zrobić, jest utrzymanie sortowanej priorytetowej sterty, z której wyskakuje, gdy znajdzie się w niej 100 wpisów.

Chociaż nie obchodzi Cię, czy wyniki są posortowane, intuicyjnie oczywiste, że dostaniesz to za darmo. Aby wiedzieć, że masz 100 najlepszych, musisz uporządkować bieżącą listę najwyższych numerów w porządku za pomocą wydajnej struktury danych. Struktura ta będzie znała minimalne, maksymalne i względne położenie każdego elementu w jakiś naturalny sposób, dzięki czemu możesz potwierdzić jego położenie obok sąsiadów.

Jak już wspomniano w Pythonie, należy użyć heapq. W Javie kolejka priorytetowa: http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 5

Oto rozwiązanie Użyłem że jest niezależna od bibliotek i że będzie działać w dowolnym języku programowania, który ma tablic:

Inicjalizacja:

Make an array of 100 elements and initialise all elements 
with a low value (less than any value in your input list). 

Initialise an integer variable to 0 (or any value in 
[0;99]), say index_minvalue, that will point to the 
current lowest value in the array. 

Initialise a variable, say minvalue, to hold the current 
lowest value in the array. 

Dla każdego value, say current_value, na liście wejściowej:

if current_value > minvalue 

    Replace value in array pointed to by index_minvalue 
    with current_value 

    Find new lowest value in the array and set index_minvalue to 
    its array index. (linear search for this will be OK as the array 
    is quickly filled up with large values) 

    Set minvalue to current_value 

else 
    <don't do anything!> 

min. wartość wil Szybko uzyskuję wysoką wartość, a zatem większość wartości na liście wejściowej będzie musiała być porównana tylko z wartością min. (wynik porównania będzie w większości fałszywy).

Answer 6

Dla algorytmów weenies na widowni: można to zrobić za pomocą prostego zmienności na algorytmie Find Tony Hoare w:

find(topn, a, i, j) 
    pick a random element x from a[i..j] 
    partition the subarray a[i..j] (just as in Quicksort) 
    into subarrays of elements <x, ==x, >x 
    let k be the position of element x 
    if k == 0 you're finished 
    if k > topn, call find(topn, a, i, k) 
    if k < topn, call find(topn-k, k, j) 

Algorytm ten stawia największe topn elementów w pierwszych topn elementów tablicy a, bez ich sortowania. Oczywiście, jeśli chcesz je posortować, lub dla czystej prostoty, kupa jest lepsza, a wywoływanie funkcji biblioteki jest jeszcze lepsze. Ale to fajny algorytm.