On 2012-11-24, slawek <s...@h...pl> wrote:
> Nie jest. Oczywiście - sortowanie to w pewnym sensie "brute force" - da się
> i sortując a potem zliczając, tyle że nie wydaje się, aby to był najlepszy
> algorytm (delikatnie rzecz ujmując).

Bo to nie jest docelowy algorytm (choć może być). To jest tylko pewne
oszacowanie złożoności problemu.

Algorytmów do takiego problemu można wymyślić dużo (wiadomo ile).
Oczywiście sortowanie explicite można zastąpić drzewami, ale de facto
sprowadza się to do podobnych operacji. Dlatego napisałem, że jest to
równoważne sortowaniu (bo trzeba te elementy porównać i jakoś umożliwić
szybkie odwoływanie się do już "zaliczonych", a o to właśnie chodzi
w sortowaniu). Kolejnym podejściem jest hash'owanie.

Jeśli zakładasz, że po danych możesz przejść tylko raz i nie możesz
ich wszystkich zapisać, bo analizujesz "na żywo" (standardowa sytuacja
w fizyce, więc może to właśnie Cię dotyczy), to musisz przechowywać
zliczenia historyczne (przynajmniej tych elementów, które jeszcze mogą
"wygrać"). To jest po prostu nie do przeskoczenia w ogólnym przypadku.

pozdrawiam,
PK

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:k8qh5v$rad$...@n...news.atman.pl...
> W każdym razie naszą operację szacujemy na 15-20 minut.
> Długo, trzeba by poprawić.
>
> Ale zaczyna być ciekawie:)

Właśnie wyguglałem:
http://www.mathcs.emory.edu/~cheung/papers/StreamDB/
Frequency-count/FrequentStream.pdf

do góry

On 2012-11-24, slawek <s...@h...pl> wrote:
> Poczytaj sobie np. to
>
> http://www.mathcs.emory.edu/~cheung/papers/StreamDB/
Frequency-count/FrequentStream.pdf

Pierwsze zdanie abstraktu:
"We present a 1-pass algorithm for ESTIMATING the most frequent items
in a data stream (...)".

Twój problem brzmiał "znaleźć najczęściej występującą sekwencję zwaną
podciągiem".

pozdrawiam,
PK

do góry

Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..
> Też liczyłem, że coś powie (przecież dałem mu całą noc!). Ale świat
> toczy się dalej, więc lepiej to przyciąć od razu i bujać się z czymś
> innym :).

To pobujaj się z tym:
http://www.cs.yale.edu/homes/el327/datamining2011aFi
les/ASimpleAlgorithmForFindingFrequentElementsInStre
amsAndBags.pdf

do góry

Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..
> On 2012-11-24, slawek <s...@h...pl> wrote:
>> Poczytaj sobie np. to
>>
>> http://www.mathcs.emory.edu/~cheung/papers/StreamDB/
Frequency-count/FrequentStream.pdf
>
> Pierwsze zdanie abstraktu:
> "We present a 1-pass algorithm for ESTIMATING the most frequent items
> in a data stream (...)".
>
> Twój problem brzmiał "znaleźć najczęściej występującą sekwencję zwaną
> podciągiem".

Tu masz jeszcze
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10
.1.1.162.1712&rep=rep1&type=pdf

Jest nawet coś o zastosowaniach w marketingu - więc temat dość praktyczny
się okazuje.

do góry

On 24.11.2012 14:13, bartekltg wrote:
> W każdym razie naszą operację szacujemy na 15-20 minut.
> Długo, trzeba by poprawić.
>
> Ale zaczyna być ciekawie:)

Jest sobie OzSort, który sortuje 250GB danych (100 bajtowe bloki, 10B
klucza, 90B payload) w 30 minut na nie_tak_drogim sprzęcie.

>
> To drzewo dużo miejsca nam nie oszczędza, ale zawsze.
> Nie zaszkodzi spróbować, ale dla losowego ta heurystyka
> zadziała?

Zadziała dopóki różnych wartości jest dostatecznie mało. Każdy wpis do
drzewa to 5 bajtów na poziom (klucz na k-tym poziomie+wskaźnik/licznik
na końcu). Jeżeli dobrze szacuję to wyszukiwanie binarne max 16*8
operacji, wstawianie max 16*255 operacji(nie licząc tego, że
potrzebujemy alokator). Wychodzi około 6 milionów wpisów na 512MB ram.
Dopóki liczba różnych wartości jest mniejsza od maksymalnego drzewa -
powinno działać. Dla losowych raczej nie.


--
Pozdrawiam
Michoo

do góry

On 24.11.2012 14:48, slawek wrote:
>
> Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
> dyskusyjnych:k8qh5v$rad$...@n...news.atman.pl...
>> W każdym razie naszą operację szacujemy na 15-20 minut.
>> Długo, trzeba by poprawić.
>>
>> Ale zaczyna być ciekawie:)
>
> Właśnie wyguglałem:
> http://www.mathcs.emory.edu/~cheung/papers/StreamDB/
Frequency-count/FrequentStream.pdf

To rozwiązuje inny problem niż przedstawiłeś.

--
Pozdrawiam
Michoo

do góry

On 2012-11-24, slawek <s...@h...pl> wrote:
>
> Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
> dyskusyjnych:s...@n...notb-home.
..
>> o klasę problemów i klasę złożoności. W szczególności: rozwiązanie
>> Twojego problemu będzie miało złożoność nie mniejszą niż sortowanie,
>
> Jeżeli będziemy upierali się aby porównywać dane - oczywiście. A czy to na
> pewno trzeba robić? Ot, pytanie!

Tak. Dominanta to najczęściej występująca wartość w zbiorze. To oznacza,
że trzeba porównywać elementy (to tak z definicji).

Ale oczywiście można wykombinować podejście przybliżone. Masz ten stream
wartości. Bez problemu możesz w swoim RAM obsługiwać te M-krotki.
Wymyśl dużo różnych funkcji mających M argumentów. Obliczasz je
wszystkie na ostatniej M-krotce i przesuwasz okno o 1. Możesz
budować histogramy wartości (zmieścisz je w pamięci), a na końcu
odgadnąć na ich podstawie dane wejściowe (tzn. zbiór możliwości,
który - przy odrobinie szczęścia - będzie zawierał jakieś podobne
elementy). Jeśli Twój "stream" to np sygnał elektryczny i szukasz
najbardziej popularnego impulsu, to możesz próbować dopasowywać
jakieś patterny. To jest podejście wyciągnięte wprost z HFT, FX i AT,
czyli skrótów, które tak zbulwersowały część dyskutantów.

Ale tak naprawdę najlepiej byłoby, gdybyś podszedł do tego jak fizyk,
a nie programista. Twoje dane to pewnie wynik jakiegoś doświadczenia.
Powinieneś ogarnąc teorię stojącą za tym procesem i wyciągnąć z tego
maksymalnie dużo (na kartce czy jak wolisz: e-notesie). W najlepszym
wypadku skończysz z dobrym modelem. W najgorszym: z filtrami, które
istotnie zmniejszą Ci rozmiar problemu.
Tak naprawdę Twój stosunek ilości danych do dostępnego RAMu nie jest
w żaden sposób imponujący. LHC generuje kilkaset GB/s. Podstawowe
filtry obcinają 99.9%. I nie jest to efekt żadnej zajebistej algorytmiki
tylko lat skrupulatnego rzeźbienia w fizyce.

Ponadto przypominam, że jeśli są to dane empiryczne, a nie złośliwie
generowane, to możesz estymować na ich podzbiorze. Możesz budować
i kalibrować model na np. połowie tego streamu i potem puścić go
na reszcie.

Generalnie możesz zrobić dużo rzeczy mądrzejszych niż wymyślanie
algorytmu na siłę (szczególnie jeśli taki algorytm nie istnieje).

pozdrawiam,
PK

do góry

Dnia Sat, 24 Nov 2012 03:18:45 -0800 (PST), e...@g...com
napisał(a):

> W dniu sobota, 24 listopada 2012 04:44:05 UTC-5 użytkownik Jacek napisał:
>
>>> I obie strony sa szczesliwe.
>
>> Chyba mnie nie zrozumiałeś.
>> Chodzi o to, że przez brak krawata, jakaś _pinda_ odsieje kandydata, który
>> może być dobrym specjalistą, bo ona ma takie patrzenie na świat.
>> Nigdy nie miałem wąsów, brody, a krawat miałem kilka razy na sobie i cieszę
>> się, że pracuje sam dla siebie.
>
> Musialbym bardzo chciec. W przeciwnym wypadku pytanie jest takie:
> dlaczego witaja mnie taka pinda? Za co? I jeszcze ona o wszystkim
> decyduje w moim przypadku? No to super, dalej moze byc tylko gorzej.

Wita Ciebie pinda, bo takie firma ma założenia. Pinda jest po 100
szkoleniach, ma fakultet z psychologii, socjologi itd. Pracowała w ośmiu
firmach, ma wspaniałe referencje i w koncu wylądowała w firmie PK. A że
jakiś baran wymyślił sobie, że właśnie w pierwszym kroku rekrutuje pinda, a
później kierownicy, specjaliści etc., to tak to właśnie funkcjonuje.
Dalej (po pindzie) nie musi być wcale gorzej, lecz lepiej, bo zaczniesz
gadać z kumplami po fachu.
Edek, ja nie piszę o rzeczach z kosmosu, a o często spotykanej sytuacji w
kapitalistycnych firmach/korporacjach po pozostałościach PRLowskich
kombinatów i innych dużych fabrykach.

do góry

Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..
> Tak. Dominanta to najczęściej występująca wartość w zbiorze. To oznacza,
> że trzeba porównywać elementy (to tak z definicji).

Radix sort.

> Ale tak naprawdę najlepiej byłoby, gdybyś podszedł do tego jak fizyk,
> a nie programista. Twoje dane to pewnie wynik jakiegoś doświadczenia.

Nie. Nie ma żadnych danych.

Choć jak poguglałem, to np. znalazłem i coś takiego:
http://www.notjustrandom.com/2009/11/13/finding-freq
uent-items-in-a-data-stream/

Cyt. "It is one of the most heavily studied problems in mining data streams,
dating back to the 1980s."

Wow!

> Tak naprawdę Twój stosunek ilości danych do dostępnego RAMu nie jest
> w żaden sposób imponujący. LHC generuje kilkaset GB/s. Podstawowe

Oczywiście że nie jest!

Rozmiar starałem się trafić taki, aby było już dość trudno... ale jednak
wykonalnie na zwykłym PC. Bartek policzył (chwała mu za to), że powinno dać
się znaleźć w jakieś 20 minut. Czyli nie "natychmiast", ale zanim rozpadną
się ostatnie protony ;)

> Generalnie możesz zrobić dużo rzeczy mądrzejszych niż wymyślanie
> algorytmu na siłę (szczególnie jeśli taki algorytm nie istnieje).

Patrz wyżej - na link. Sam nie wiedziałem, że to ma jakieś praktyczne
znaczenie. A jednak: ma.

do góry