Algorytm dla „k” najczęściej występujących liczb

Szukałem najbardziej wydajnego algorytmu (streaming?), Który mówi mi „k” najczęściej występujące elementy w strumieniu danych w dowolnym momencie. Ten post: Algorytmy strumienia danych „Dziel i rządź” zainteresowały mnie.

Załóżmy na przykład, że istnieją liczby: (4,3,5,1,6,2,4,3,3,8,8,9,1) i szukam 3 najczęściej występujących liczb (powiedzmy), to powinienem otrzymaj (3,4,1) jako odpowiedź.

Próbowałem szukać w Internecie, ale nie mogłem znaleźć żadnego miejsca, które dałoby takie podejście i powiedziałoby, że to najlepsze. Trywialnym rozwiązaniem byłoby użycie sterty lub zbalansowanego drzewa binarnego, ale myślę, że jest lepszy sposób i chciałem wiedzieć, czy gdzieś jest to udokumentowane.

Edycja: szukam algorytmu, który zawsze daje poprawną odpowiedź, w przeciwieństwie do algorytmu appromiksacji (wiele z nich pojawia się w wynikach wyszukiwania), które opierają się na dystrybucji danych w taki czy inny sposób

ds.algorithms online-algorithms data-streams dhruvbird
źródło

W rzeczywistości istnieją trzy rodzaje algorytmów: dokładne, przybliżone i „zależne od danych”. Wykluczyłeś ostatni rodzaj, ale czy dozwolone są przybliżone algorytmy, które NIE zależą od dystrybucji danych? jak wskazałem, jeśli nie, masz kłopoty z powodu znanych dolnych granic tego problemu w ustawieniu strumienia.

Suresh Venkat

Byłem ciekawy, czy algorytmy wykorzystujące ograniczoną pamięć (algorytmy przesyłania strumieniowego) mogą faktycznie robić to, co chciałem i wydaje się, że nie mogą, tak jak wskazałeś. Również, czy znany jest nieprzesyłający algorytm dokładny, który rozwiązuje problem w O (n) gwarantowanym najgorszym przypadku, o którym tu wspomniano (cytowany w artykule Cormode i Hadjileftheriou z podanego linku): citeseerx.ist.psu. edu / viewdoc / summary? doi = 10.1.1.106.7889

dhruvbird

Odpowiedzi:

$k=1$ $o(n)$

$n/k$

$k$ $k$

Suresh Venkat
źródło

+1. Myślę, że> 50% algorytmu czasu jest dobrze znanym (algorytm większościowy), jak wspomniałeś

dhruvbird

Dzięki!! Artykuł Cormode i Hadjileftheriou, o którym wspomniałeś, cytuje ten artykuł: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889, który ma tę samą technikę, o której myślałem. Utrzymuje 2 powiązane listy; jeden po częstotliwości, aw nim kolejna lista wszystkich elementów o tej samej częstotliwości.

dhruvbird

czy możesz rozwinąć algorytm ponad 50 procent? i puzzle Google? Nie mogę podążać za tym niedbałym rozumowaniem, ponieważ właśnie go dotknąłeś i nie w pełni wykorzystałeś „dobrze znaną sztuczkę”. Dzięki.

Oto link: userweb.cs.utexas.edu/users/misra/scannedPdf.dir/…

Suresh Venkat

To jest komentarz (za mało reputacji) na link Suresh Venkat userweb.cs.utexas.edu/users/misra/scannedPdf.dir/… : Wygląda na to, że przedstawiony tam algorytm wymaga drugiego przejścia przez dane, co jest niedozwolone tutaj. W rzeczywistości nie widzę, jak może istnieć algorytm jednoprzebiegowy z wymaganiami dotyczącymi przestrzeni O (1).

TonyK

Polecam również przeczytanie sekcji 8.1.3 „Częste wyszukiwanie wzorców w strumieniach danych” następującej książki:

Jiawei Han, Micheline Kamber. Data Mining --- Concepts and Techniques, drugie wydanie, Morgan Kaufmann Publishers , 2006.

Wprowadza algorytm znany jako Lossy Counting , który aproksymuje częste przedmioty (przedmioty, których wsparcie jest powyżej niektórych min_support ) z dowolną precyzją.

Nie dokładnie to, czego chcesz, ale pomyślałem, że to może pomóc.

MS Dousti
źródło

może możesz mi pomóc tutaj w

Ben