Najbardziej skuteczny sposób zliczania wystąpień?

Question

Próbuję obliczyć entropię i wzajemne informacje ogromną liczbę razy w kodzie krytycznym pod względem wydajności. Jako etap pośredni muszę policzyć liczbę wystąpień każdej wartości. Na przykład:

uint[] myArray = [1,1,2,1,4,5,2]; 
uint[] occurrences = countOccurrences(myArray); 
// Occurrences == [3, 2, 1, 1] or some permutation of that. 
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5. 

oczywiście oczywistych sposobów, aby to zrobić albo są za pomocą tablicy asocjacyjnej lub sortując tablicę wejściowego używając „standard” jak algorytm sortowania szybkiego sortowania. W przypadku małych liczb całkowitych, takich jak bajty, kod jest obecnie wyspecjalizowany w używaniu zwykłej starej tablicy.

Czy istnieje inteligentny algorytm do wykonania tej czynności wydajniej niż tablica skrótów lub "standardowy" algorytm sortowania, taki jak asocjacyjna implementacja macierzy, która zdecydowanie faworyzuje aktualizacje względem wstawień lub algorytm sortowania, który świeci, gdy dane mają dużo więzi?

Uwaga: Nie rozseparowane liczby całkowite są tylko jednym przykładem możliwego typu danych. Zamierzam wdrożyć tutaj dość ogólne rozwiązanie, chociaż ponieważ liczby całkowite i struktury zawierające tylko liczby całkowite są częstymi przypadkami, chciałbym być zainteresowany rozwiązaniami specyficznymi dla nich, jeśli są one wyjątkowo wydajne.

Answer 1

Podaj więcej informacji o swoich danych.

• Ile jest tam przedmiotów?
• Jaka jest oczekiwana proporcja unikalnych pozycji do łącznych pozycji?
• Jaki jest rozkład rzeczywistych wartości liczb całkowitych? Czy są one zwykle na tyle małe, aby korzystać z prostej tablicy liczącej? A może skupiają się w dość wąskie grupy? Itd.

W każdym razie proponuję następujący pomysł: mergesort zmodyfikowany w celu zliczania duplikatów.

Oznacza to, że pracujesz w kategoriach nie liczb, ale par (liczba, częstotliwość) (możesz użyć do tego sprytnie wydajnej pamięci, na przykład dwóch tablic zamiast tablicy par itp.).

Zaczynasz od [(x1,1), (x2,1), ...] i jak zwykle wykonujesz mergesort, ale kiedy scalisz dwie listy zaczynające się od tej samej wartości, wstawiasz wartość do lista wyników z ich sumą wystąpień. Na swoim przykładzie:

[1:1,1:1,2:1,1:1,4:1,5:1,2:1] 
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1] 
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1] 
Merge them: (first/second/output) 
[1:2, 2:1]/[1:1, 2:1, 4:1, 5:1]/[] - we add up 1:2 and 1:1 and get 1:3 
[2:1]/[2:1, 4:1, 5:1]/[1:3] - we add up 2:1 and 2:1 and get 2:2 
[]/[4:1, 5:1]/[1:3, 2:2] 
[1:3, 2:2, 4:1, 5:1] 

To może być poprawiona znacznie stosując kilka sprytnych sztuczek, aby zrobić wstępną redukcję tablicy (uzyskać tablicę wartości: par Występowanie który jest znacznie mniejszy niż oryginał, ale suma "występowanie" dla każdej "wartości" jest równe liczbie wystąpień "wartości" w pierwotnej tablicy). Na przykład podziel tablicę na bloki ciągłe, których wartości różnią się o nie więcej niż 256 lub 65536 i użyj małej tablicy do zliczania wystąpień wewnątrz każdego bloku. W rzeczywistości ta sztuczka może być zastosowana również w późniejszych fazach scalania.

Answer 2

Z tablicą liczb całkowitych, jak w przykładzie, najbardziej efektywnym sposobem byłoby mieć tablicę z int s i indeksować ją na podstawie twoich wartości (jak wydajesz się już robić).

Jeśli nie możesz tego zrobić, nie mogę wymyślić lepszej alternatywy niż smoczek. Musisz tylko mieć szybki algorytm mieszający. Nie możesz uzyskać lepszej wydajności niż O (n), jeśli chcesz wykorzystać wszystkie swoje dane. Czy jest możliwość użycia tylko części danych, które posiadasz?

(Należy zauważyć, że do sortowania i liczenia się asymptotycznie wolniej (O (N * log (n))) w porównaniu z użyciem roztworu hashmap podstawie (O (n))).

Answer 3

mieszającej jest generalnie bardziej skalowalne, jak inna odpowiedź wskazuje. Jednak w przypadku wielu możliwych dystrybucji (i wielu przypadków rzeczywistych, w których podrzędne często są sortowane, w zależności od sposobu zestawienia całej tablicy), timsort jest często "nadnaturalnie dobry" (bliżej O (N) niż O (N log N)) - Słyszałem, że prawdopodobnie stanie się standardowym/domyślnym algorytmem sortowania w Javie przy pewnych rozsądnie bliskich przyszłych danych (od lat jest to standardowy algorytm sortowania w Pythonie).

Nie ma naprawdę dobrego sposobu na rozwiązanie takich problemów, z wyjątkiem analizy porównawczej wybranych przypadków, które są reprezentatywne dla rzeczywistego obciążenia pracą, którego można się spodziewać (z oczywistym ryzykiem, że można wybrać próbkę, która faktycznie się zdarzyła). być stronniczy/niereprezentatywny - nie jest to małe ryzyko, jeśli próbujesz zbudować bibliotekę, która będzie używana przez wielu użytkowników zewnętrznych poza Twoją kontrolą).