Najczęściej powtarzające się liczby na olbrzymiej liście liczb

Question

Mam plik, który ma wiele losowych liczb całkowitych (około miliona), z których każda oddzielona jest białą spacją. Muszę znaleźć 10 najczęściej występujących numerów w tym pliku. Jaki jest najbardziej efektywny sposób na to w java? Mogę myśleć o 1. Utwórz mapę skrótu, klucz jest liczbą całkowitą z pliku, a wartość jest liczbą. Dla każdej liczby w pliku sprawdź, czy ten klucz już istnieje w mapie mieszania, jeśli tak, wartość ++, w przeciwnym razie wprowadź nowy wpis w haszcie 2. Zrób BST, każdy węzeł jest liczbą całkowitą z pliku. Dla każdej liczby całkowitej z pliku sprawdź, czy istnieje węzeł w BST, jeśli tak, zrób wartość ++, wartość jest częścią węzła.

Czuję, że mapa hash jest lepszym rozwiązaniem, jeśli mogę wymyślić dobrą funkcję mieszającą, Czy ktoś może mi zaproponować, co jest najlepsze? Czy jest jakiś inny skuteczny algo, którego mogę użyć?

Answer 1

Java obsługuje mieszanie. Nie musisz pisać funkcji skrótu. Po prostu zacznij przesuwać rzeczy na mapie skrótów.

Ponadto, jeśli jest to coś, co należy uruchomić tylko raz (lub tylko sporadycznie), nie należy optymalizować obu tych funkcji. Będzie wystarczająco szybki. Tylko przeszkadza, jeśli jest to coś, co będzie działać w aplikacji.

Answer 2

Edit # 2:

Dobra, ja spieprzyłem własną pierwszą zasadę - nigdy zoptymalizować przedwcześnie. Najgorszym z tego powodu jest prawdopodobnie użycie programu HashMap o szerokim zakresie - więc właśnie to zrobiłem. Ciągle trwa sekundę, więc zapomnij o wszystkim innym i po prostu to zrób.

Zrobię dla siebie ZALECENIE, aby ZAWSZE przetestować szybkość, zanim zacznę martwić się o skomplikowane implementacje.

(Poniżej jest starszy nieaktualne post, który nadal może być ważne, jeśli ktoś miał o wiele więcej punktów niż milion)

HashSet będzie działać, ale jeśli całkowitymi mają rozsądny zakres (powiedzmy, 1-1000) bardziej wydajne byłoby utworzenie tablicy 1000 liczb całkowitych, a dla każdego ze swoich milionów liczb całkowitych, inkrementacja tego elementu tablicy. (W zasadzie taki sam pomysł jak HashMap, ale zoptymalizowanie kilku niewiadomych, z którymi Hash musi się liczyć, powinno zrobić to kilka razy szybciej).

Można również utworzyć drzewo. Każdy węzeł w drzewie zawierałby (wartość, liczbę), a drzewo byłoby uporządkowane według wartości (niższe wartości po lewej, wyższe po prawej). Przejdź do swojego węzła, jeśli nie istnieje - włóż go - jeśli tak, po prostu zwiększ liczbę.

Zasięg i rozkład wartości określałby, który z tych dwóch (lub zwykły skrót) byłby lepszy. Myślę, że zwykły hash nie miałby wielu "zwycięskich" przypadków (musiałby to być szeroki zakres i "pogrupowane" dane, a nawet wtedy drzewo mogłoby wygrać.)

Ponieważ jest to dość trywialne - I zalecamy wdrożyć więcej niż jedno rozwiązanie i testów prędkości przed rzeczywistego zestawu danych

Edycja. RE komentarzu

TreeMap będzie działać, ale byłoby jeszcze dodać warstwę zadnie (i to tak niezwykle łatwe i przyjemne zaimplementuj siebie) .Jeśli używasz implementacji zasobów, musisz używać liczb całkowitych i stale konwertować do i od int dla każdego wzrostu.Istnieje indirection wskaźnika do Integer i fakt, że przechowujesz na najmniej dwa razy tyle obiektów. To nie uwzględnia nawet żadnych kosztów dla wywołań metod, ponieważ powinny one mieć dowolne szczęście.

Zwykle byłaby to optymalizacja (zła), ale kiedy zaczynasz zbliżać się do setek tysięcy węzłów, czasami musisz zapewnić wydajność, więc wbudowana TreeMap będzie nieefektywna z tych samych powodów, dla których wbudowany program HashSet.

Answer 3

Dlaczego warto używać hashtable? Po prostu użyj tablicy o takim samym rozmiarze jak zakres liczb. Wtedy nie tracisz czasu na wykonywanie funkcji haszowania. Następnie posortuj wartości po zakończeniu. O (N log N)

Answer 4

Jest źródłem java.lang.Integer.hashCode(), czyli funkcję mieszającą, która zostanie użyta, jeśli przechowywać swoje wpisy jako HashMap<Integer, Integer>:

public int hashCode() { 
return value; 
} 

Więc innymi słowy, The (domyślnie) wartość skrótu java.lang.Integer jest samą liczbą całkowitą.

Co jest bardziej skuteczne?

Answer 5

1. Przeznaczyć tablicę/wektor o takim samym rozmiarze jak liczba elementów wejściowych masz
2. Wypełnij tablicę z pliku z numerami, numer jeden na element
3. umieścić listę w kolejności
4. Iteruj listę i śledź 10 pierwszych przebiegów liczb, które napotkałeś.
5. Wypisz dziesięć pierwszych przebiegów na końcu.

W ramach udoskonalania w kroku 4 wystarczy przejść do przodu w szeregu w krokach odpowiadających dziesięciokrotnemu najdłuższemu biegowi. Każde uruchomienie dłuższe niż to pokrywa się z próbkowaniem. Jeśli dziesiąty najdłuższy bieg ma długość 100 elementów, wystarczy wypróbować element 100, 200, 300 i w każdym punkcie policzyć bieg liczb całkowitych, które można tam znaleźć (zarówno w przód, jak iw tył). Każdy bieg dłuższy niż 10. najdłuższy z pewnością pokryje się z próbkowaniem.

Powinieneś zastosować tę optymalizację, gdy twoja 10-ta długość przebiegu jest bardzo długa w porównaniu do innych serii w macierzy.

Mapa jest przesadna dla tego pytania, chyba że masz bardzo mało unikalnych numerów, każdy z dużą liczbą powtórzeń.

NB: Podobny do odpowiedzi gshauger, lecz uregulowana

Answer 6

Jeśli trzeba uczynić go jak najbardziej skuteczny, należy użyć tablicę int, z pozycji reprezentujących wartość i treść reprezentujący liczbę. W ten sposób unikniesz autoboxingu i rozpakowywania, najbardziej prawdopodobnego zabójcy standardowej kolekcji Java.

Jeśli zakres liczb jest zbyt duży, spójrz na PJC i jego implementacje IntKeyIntMap. Unika także autoboxingu. Nie wiem, czy będzie to dla ciebie wystarczająco szybkie.

Answer 7

Prawidłowy sposób to zrobić z połączoną listą. Kiedy wstawiasz element, przechodzisz w dół na połączoną listę, jeśli tam zwiększasz liczbę węzłów, w przeciwnym razie tworzysz nowy węzeł z liczbą 1. Po wstawieniu każdego elementu masz posortowaną listę elementów w O (n * log (n)).

Dla twoich metod robisz n wstawek, a następnie sortujesz w O (n * log (n)), więc twój współczynnik złożoności jest wyższy.

Answer 8

Jeśli zakres liczb jest mały (na przykład 0-1000), należy użyć tablicy. W przeciwnym razie użyj wartości HashMap<Integer, int[]>, w której wartościami są wszystkie tablice o długości 1. Powinieneś znacznie szybciej zwiększać wartość w tablicy prymitywów niż tworzyć nową liczbę całkowitą za każdym razem, gdy chcesz zwiększyć wartość. Nadal tworzysz obiekty Integer dla kluczy, ale trudno tego uniknąć. Nie jest możliwe stworzenie tablicy 2^31-1 intów, mimo wszystko.

Jeśli wszystkie dane wejściowe są znormalizowane, więc nie masz wartości takich jak 01 zamiast 1, użyj ciągów znaków jako klawiszy na mapie, aby nie trzeba było tworzyć kluczy Integer.

Answer 9

HashMap

Milion liczb całkowitych nie jest naprawdę dużo, nawet dla języków tłumaczeń, ale przede wszystkim do szybkiego języku takich jak Java. Prawdopodobnie ledwo zauważysz czas wykonania. Najpierw spróbuję tego i przejdę do czegoś bardziej skomplikowanego, jeśli uznasz to za zbyt powolne.

będzie prawdopodobnie trwać dłużej robić dzielenie ciąg parsowania i konwersji do liczb niż nawet najprostszy algorytm, aby znaleźć częstotliwości za pomocą HashMap.

Answer 10

Użyj HashMap do tworzenia zbioru danych (par value-count) w pamięci, jak przechodzić plik. HashMap powinien dawać ci dostęp do elementów w pobliżu O (1) podczas tworzenia zbioru danych (technicznie, w najgorszym przypadku HashMap to O (n)). Po zakończeniu wyszukiwania pliku użyj Collections.sort() na wartości Collection zwróconej przez HashMap.values ​​(), aby utworzyć posortowaną listę par wartości. Korzystanie z Collections.sort() jest gwarantowane O (nLogn). Na przykład:

public static class Count implements Comparable<Count> { 
    int value; 
    int count; 
    public Count(int value) { 
     this.value = value; 
     this.count = 1; 
    } 
    public void increment() { 
     count++; 
    } 
    public int compareTo(Count other) { 
     return other.count - count; 
    } 
} 

public static void main(String args[]) throws Exception { 
    Scanner input = new Scanner(new FileInputStream(new File("..."))); 
    HashMap<Integer, Count> dataset = new HashMap<Integer, Count>(); 
    while (input.hasNextInt()) { 
     int tempInt = input.nextInt(); 
     Count tempCount = dataset.get(tempInt); 
     if (tempCount != null) { 
      tempCount.increment(); 
     } else { 
      dataset.put(tempInt, new Count(tempInt)); 
     } 
    } 

    List<Count> counts = new ArrayList<Count>(dataset.values()); 
    Collections.sort(counts); 

Answer 11

Faktycznie, jest O (n) algorytm robi dokładnie to, co chcesz zrobić. Twój przypadek użycia jest podobny do pamięci podręcznej LFU, w której licznik dostępu elementu określa, czy jest on przechowywany w pamięci podręcznej, czy jest z niego eksmitowany.

http://dhruvbird.blogspot.com/2009/11/o1-approach-to-lfu-page-replacement.html