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