Algorytm strumienia danych

W informatyce , a jest strumień danych algorytm jest algorytmem , dane z jednego lub większej liczby strumieni danych sekwencyjnie czyta, a tym samym bezpośrednio ( „online”) procesy.

podanie

Wiele współczesnych aplikacji w informatyce wymaga przetwarzania strumienia danych ze względu na niezwykle dużą, stale dostarczaną ilość danych . Dzieje się tak na przykład podczas rejestrowania danych trasowania w sieciach, podczas rejestrowania danych telekomunikacyjnych, podczas transakcji bankowych lub przy indeksach giełdowych .

Perspektywa matematyczna i wymagania dotyczące sprawności

Ciągle gromadzone dane są modelowane jako strumień - sekwencja znaków wejściowych, których długość jest często nieznana, ale zakłada się, że jest bardzo duża.

Algorytm przetwarzający strumień może odczytywać tylko znak po znaku strumienia, dostęp losowy, tj. H. „Skakanie” do wprowadzanych znaków jest niedozwolone.

W scenariuszu przepływu danych istnieją zasadniczo dwa wymagania dotyczące wydajności ze względu na ilość generowanych danych: Złożoność przestrzeni dyskowej algorytmu przepływu danych powinna być nieliniowa, najlepiej logarytmiczna lub polilogarytmiczna, a także czas obliczeniowy na znak wejściowy .

Pewne problemy można zatem rozwiązać precyzyjnie za pomocą algorytmów przepływu danych, ponieważ można odczytać całe wejście. Niemniej jednak podliniowa przestrzeń magazynowa i podliniowy czas obliczeniowy na znak wejściowy to wymagania dotyczące wydajności, które często prowadzą do tego, że nie jest to możliwe i można podać tylko przybliżone rozwiązania i należy zastosować randomizację.

Ponieważ algorytm strumienia danych może nie zapisywać całego wejścia z powodu podliniowej przestrzeni magazynowej, a jedynie podsumowanie tego, co zostało do tej pory zaobserwowane. Mówi się, że algorytm zapisuje szkic dotychczasowych danych wejściowych.

W poniższym przykładzie przedstawiono algorytm, który może dokładnie rozwiązać dany problem.

Przykłady

Liczba elementów

Liczbę elementów w strumieniu danych można łatwo określić za pomocą licznika. Zapotrzebowanie na pamięć można dodatkowo zmniejszyć za pomocą algorytmów losowych.

Brakujący numer

Pozwolić permutacją do liczby z jednym brakującym elementem . ${\ displaystyle \ pi}$ ${\ displaystyle \ {1, ..., n \}}$ ${\ displaystyle s}$

Prostym sposobem na znalezienie brakującej liczby byłoby zebranie wszystkich liczb, posortowanie ich, a następnie przeszukanie po kolei uporządkowanego zestawu w poszukiwaniu brakującego elementu. Jednak aby to zrobić, wszystkie numery musiałyby zostać zapisane zgodnie z opisem. Zużycie pamięci przez ten algorytm wynosi bajty, jeśli zakłada się, że każda liczba jest przechowywana jako 32-bitowa liczba całkowita . Na przykład musiałbyś zaoszczędzić około 3,7 GB. Aby osiągnąć odpowiednią wydajność, dane te musiałyby być przechowywane w pamięci głównej, ale nie jest to możliwe w przypadku większości komputerów PC ze względu na dużą ilość danych. Oznacza to, że należałoby uzyskać dostęp do dysku twardego, co jednak powoduje, że algorytm ten jest wyjątkowo powolny. ${\ Displaystyle n \ cdot 4}$ ${\ displaystyle n = 1 000 000 000}$

Gdyby wszystkie liczby były zawarte w strumieniu danych, suma elementów strumienia byłaby zgodna z formułą sumy Gaussa . Dlatego biorąc pod uwagę sumę mocy zawartej w elementach , można więc określić liczbę poszukiwaną po odczytaniu całego wejścia do ustalenia. Ten algorytm musi tylko zapisać jedną liczbę, aby obliczyć sumę, a następnie ją określić, a zatem przestrzeń pamięci wynosi tylko O (log n). Jest to oczywiście bardziej wydajne. ${\ displaystyle 1, ..., n}$ ${\ Displaystyle \ sum _ {i = 1} ^ {n} i = {\ Frac {n (n + 1)} {2}}}$ ${\ displaystyle n-1}$ ${\ displaystyle \ pi}$ ${\ displaystyle s}$ ${\ Displaystyle s = {\ Frac {n (n + 1)} {2}} - \ suma {\ pi}}$ ${\ displaystyle s}$