Najszybsza i najskuteczniejsza metoda wyszukiwania pierwszych 3 liczb?

Question

Obecnie mam tablicę około 8-10 liczb, które zmieniają się okresowo.

Tak więc co 5-10 sekund liczby są aktualizowane.

Potrzebuję uzyskać 3 pierwsze cyfry w tablicy co 10 sekund.

Wszystko to odbywa się na urządzeniu mobilnym.

Tablica jest RSSI aktualnie skanowanych punktów dostępowych, więc w moim biurze jej zwykle około 10, ale w dziedzinie testowania mogłaby wzrosnąć do około 50.

Na minutę iterację tablicy 3 razy i za każdym razem wyjmuję trzy najwyższe liczby i umieszczam je w trzech wcześniej zadeklarowanych zmiennych.

Moje pytanie brzmi: co powinienem zrobić, aby zwiększyć szybkość i wydajność w tym przypadku?

Answer 1

Liczby to tylko 10 - nie rób nic. Jest już wystarczająco wydajny.

Jeśli rozmiar się zwiększy, można użyć numeru max-heap do przechowywania numerów.

Answer 2

Dlaczego nie używać metody Arrays.sort, która wykorzystuje, o ile wiem, quick sort pod maską.

Paul

EDIT: zweryfikowane Używa tuned quick sort

Answer 3

Twój algorytm jest już O (n), szybkiego sortowania jest> O (n log n), więc nie jest to z pewnością sposób, aby to zrobić. Możesz zwiększyć prędkość do O (log n), jeśli używasz struktury drzewa, np. Drzewa AVL. Tylko w przypadku tablic, twój bieżący jest najszybszy sposób to zrobić.

Answer 4

Obecny algorytm wymaga 3 * n porównań. Można wykonać odmianę Sortowanie przez wstawianie do poprawy, że:

1. Put 3 pierwsze pozycje tablicy wejście w tablicy wyjściowej, sortować je
2. iterację reszty elementów tablicy wejściowej,
   1. umieścić każdy element w tablicy wyjściowej we właściwej pozycji
   2. Trim tablicę wyjściową 3 produkty

Wymaga to 2 * n porównań. (Nie jestem pewien, czy warto tej dodatkowej złożoności).

Answer 5

Myślę, że w ogólnym przypadku powinieneś użyć algorytmu QuickSelect opartego na QuickSort i, w czasie O (n) modyfikuje twoją tablicę inline i "quasi-sort" to.

Powiedz, że twoja tablica jest A [1..10] i nie posortowana, przez wywołanie QuickSelect (A, 7) pytasz "Jaka jest liczba, która w sortowanej tablicy powinna znajdować się na siódmej pozycji?", i to jest to samo, co powiedzenie "Która liczba jest trzecia większa w tym konkretnym zestawieniu?".Teraz najważniejsze jest to, że QuickSelect zapewnia, że ​​po tym wywołaniu A [i] < = A [7] dla wszystkich 0 < i < 7 i że A [7] < = A [j] dla wszystkich 7 < j. Więcej informacji na wikipedia Quick Selection Algorithm.

Anyways jak rozmiar jest tylko 10, można użyć wstawiania-sort (najgorszy przypadek O (n^2), ale działa dobrze z małymi tablicami), a następnie dostać trzy pierwsze/ostatnie elementy

EDIT: - Struktury drzew są przesadą dla zaledwie dziesięciu elementów, a ogólnie rzecz biorąc wymaga kompromisu między czasem a przestrzenią (potrzebujesz dużo wskazówek). - QuickSelect ma scenariusz O (n^2) najgorszego przypadku, ale "Median-of-Medians" "Osiąga taki sam wynik w najgorszym przypadku O (n)