Czy każdy algorytm czasu liniowego jest algorytmem przesyłania strumieniowego?

14

Powyżej na to pytanie o liczeniu inwersji , ja znalazłem papier , który okazuje się dolną granicę przestrzeni złożoności dla wszystkich (dokładne) algorytmy strumieniowe . Twierdziłem, że to ograniczenie obejmuje wszystkie liniowe algorytmy czasowe. Jest to nieco odważne, ponieważ ogólnie algorytm czasu liniowego może skakać do woli (dostęp losowy), czego nie może algorytm przesyłania strumieniowego; musi badać elementy w kolejności. Mogę wykonywać wiele przejść, ale tylko ciągle wiele (dla liniowego środowiska uruchomieniowego).

Dlatego moje pytanie:

Czy każdy algorytm czasu liniowego może być wyrażony jako algorytm przesyłania strumieniowego z ciągłą liczbą przejść?

Losowy dostęp zdaje się uniemożliwiać (prostą) konstrukcję potwierdzającą pozytywną odpowiedź, ale nie byłem w stanie wymyślić kontrprzykładu.

W zależności od modelu maszyny losowy dostęp może nawet nie stanowić problemu, jeśli chodzi o środowisko wykonawcze. Byłbym zainteresowany odpowiedziami na te modele:

Maszyna Turinga, płaski wkład
RAM, dane wejściowe jako tablica
RAM, wprowadź jako listę połączoną

algorithms streaming-algorithm simulation lower-bounds Raphael
źródło

jak widać w odpowiedziach, „algorytmy przesyłania strumieniowego” często oznaczają małe (przestrzeń polilogu). ale biorąc pod uwagę motywację, pytanie myślę, że powinno być: czy każdy liniowy algorytm czasu, który wykorzystuje

słowa roboczym być przekształcany do streamingu zastosowania algorytmu

słowa kosmicznej. więc kontrprzykład byłby problemem, który można rozwiązać za pomocą spacji

z losowym dostępem, podczas gdy dowolny algorytm przesyłania strumieniowego z ciągłym przejściem wymaga spacji

. nie podano jeszcze takiego przykładu

s

$s$

O (s)

$O(s)$

o (n)

$o(n)$

Ω (n)

$\Omega(n)$

Sasho Nikolov

@SashoNikolov: W rzeczywistości cała kwestia miejsca jest styczna. Moje pytanie dotyczy głównie środowiska uruchomieniowego. Gdyby odpowiedź brzmiała „tak”, wówczas udowodnione w artykule dolne granice (dotyczące złożoności przestrzeni) miałyby zastosowanie do wszystkich algorytmów czasu liniowego. To, że dolna granica dotyczy przestrzeni kosmicznej, jest przypadkowe, ale nie samo w sobie stanowi sedno pytania.

Raphael

Nie rozumiem. To proste, aby liniowy algorytm czasu był „strumieniowaniem jednoprzebiegowym” z nieograniczoną przestrzenią. Twoje pytanie ma sens tylko wtedy, gdy w formie „czy algorytm dostępu liniowego w czasie może być stale przesyłany strumieniowo, zachowując w przybliżeniu miarę złożoności

”. Więc powinieneś wybrać miarę złożoności, o / w nie ma to sensu.

μ

$\mu$

Sasho Nikolov,

@SashoNikolov: Nie wiedziałem, że „algorytm przesyłania strumieniowego” ma takie problemy definicyjne. Biorąc pod uwagę, że wykazują one dolną granicę przestrzeni liniowej dla algorytmów przesyłania strumieniowego, założyłem, że przestrzeń nie była rdzeniem definicji. Ale myślę, że możesz przetłumaczyć to na „Nie ma algorytmu przesyłania strumieniowego ...”. Jednak co z tą definicją: „Algorytm przesyłania strumieniowego jest algorytmem, który otrzymuje wejściowy (listę) jeden element na raz. Dla każdego nowego elementu może wykonać obliczenia w

. Po ciągłym wielu takich przejściach , musi wydać odpowiedź po dodatkowym czasie

. ”

o (n)

$o(n)$

o (n)

$o(n)$

Raphael

@SashoNikolov: Wykluczałoby to pojęcie „skopiuj dane wejściowe i zrób wszystko”, ale ograniczyłoby to do czasu

. Czy to pasuje do zwykle oznaczanej klasy? Jeśli nie, nie sądzę, aby „strumieniowanie” można było zdefiniować w zależności od złożoności czasowej lub przestrzennej. To raczej strategia, podobnie jak Chciwy lub dziel i rządź.

o (n^{2})

$o(n^2)$

Raphael

15

Aby algorytmy przesyłania strumieniowego były znaczące, muszą pracować ze znacznie mniejszą ilością miejsca do pracy niż samo wejście. Na przykład, jeśli zezwolisz na taką samą ilość miejsca pracy jak dane wejściowe, możesz w prosty sposób określić dowolny algorytm jako „algorytm strumieniowania jednoprzebiegowego”, który najpierw kopiuje dane wejściowe do przestrzeni roboczej w jednym przejściu, a następnie używa tylko pracy przestrzeń.

Myślę, że typowe jest ograniczenie przestrzeni roboczej do co najwyżej polilogarytmicznej wielkości wejściowej, gdy mówimy o algorytmach przesyłania strumieniowego. Przy tym założeniu, wybór mediany nie ma algorytmu przesyłania strumieniowego O (1) w wyniku Munro i Patersona [MP80]: dowolny algorytm przesyłania strumieniowego P dla wyboru mediany na N elementach musi przechowywać Ω ( N ^{1 / P} ) elementy. Z drugiej strony, wybór mediany ma dobrze znany deterministyczny algorytm czasu liniowego [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest i Robert E. Tarjan. Terminy wyboru. Journal of Computer and System Sciences , 7 (4): 448–461, sierpień 1973. DOI: 10.1016 / S0022-0000 (73) 80033-9

[MP80] J. Ian Munro i Mike S. Paterson. Wybór i sortowanie z ograniczonym miejscem do przechowywania. Theoretical Computer Science , 12 (3): 315–323, listopad 1980. DOI: 10.1016 / 0304-3975 (80) 90061-4

Tsuyoshi Ito
źródło

6

W modelu przesyłania strumieniowego dozwolone jest przechowywanie tylko stałych lub polik logarytmicznych dodatkowych danych podczas skanowania danych wejściowych. Jeśli weźmiesz pod uwagę liniowy algorytm czasu
zgodny z paradygmatem dziel i podbij , musisz przechowywać więcej informacji i / lub powinieneś skanować swoje dane tyle razy, ile głębokość rekurencji.

Jednym z przykładów jest algorytm DC3 do konstruowania tablicy sufiksów tekstu (podanego jako tablica w modelu RAM). Aby zbudować tablicę sufiksów, pogrupuj znaki w trojaczki, aby otrzymać tekst z nowymi super znakami . Możesz to zrobić z przesunięciem , co daje trzy nowe teksty . Co ciekawe, możesz obliczyć tablicę przyrostków, jeśli masz tablicę przyrostków w czasie liniowym. Stąd algorytm potrzebuje $T$ $0,1,2$ $T_1,T_2,T_3$ $T_1\cdot T_2$

t (n) = t (2 / 3 n) + O (n)

$t(n)= t(2/3 \;n) + O(n)$

czas. Ta rekurencja rozwiązuje wyraźnie . Nie rozumiem, jak można to zmienić w algorytm przesyłania strumieniowego. $t(n)=O(n)$

Innym dobrze znanym przykładem jest klasyczny algorytm wyboru czasu liniowego .

A.Schulz
źródło

Oto kolejny możliwy przykład. Budowanie sterty wymaga O (n) i wykorzystuje wewnętrznie procedurę heapify opartą na dzieleniu i podbijaniu.

Massimo Cafaro,

ale to nie jest dowód, prawda? mówisz tylko, że naiwna symulacja nie zadziała. ale czasami zdarzają się zaskakujące algorytmy

Sasho Nikolov

@SashoNikolov: Mówię o tym, że nie uważam algorytmu DC3 za algorytm przesyłania strumieniowego, ponieważ wymaga on dużej pamięci operacyjnej. Być może możesz zmodyfikować algorytm do algorytmu przesyłania strumieniowego, ale wynikiem nie byłby DC3. Nie dyskutowałem, czy istnieje algorytm strumieniowy

do budowy tablicy sufiksów. To byłoby zupełnie inne pytanie.

O (n)

$O(n)$

A.Schulz,

„Nie rozumiem, jak można to zmienić w algorytm przesyłania strumieniowego”, sprawiło, że uwierzyłem, że mówisz coś więcej niż „ten algorytm nie przesyła strumieniowo bez modyfikacji”

Sasho Nikolov

4

Interpretuję twoje pytanie w następujący sposób. Załóżmy rozwiązać jakiś obliczeniowej problemu . Definiujemy: $P$

jest najmniejszym obszarem roboczym, jakimoże posiadaćdowolny algorytm losowego dostępu liniowego dlaMyślę, że dokładny model nie ma aż tak wielkiego znaczenia, ale powiedzmy, że mamy słowo RAM, które otrzymuje dane wejściowe jako tablicę tylko do odczytu o dostępie swobodnym. $R(P)$ $P$
$S(P)$ $P$

$R(P)$ $S(P)$

$n$ $[1, n-1]$ $O(\log n)$ $O(1)$ $\omega(\log n)$

$O(1/\log^2 n)$ $ps = \Omega(\sqrt{n})$ $p$ $s$ $O(\log^2 n)$

Sasho Nikolov
źródło

1

Nawet w najprostszej definicji „algorytmu przesyłania strumieniowego” (algorytmu, który po każdej inkrementalnej iteracji w źródle skutkuje natychmiastową znajomością następnego przyrostowego fragmentu wyniku), mogę wymyślić kilka algorytmów liniowych, które nie zachowuj się w ten sposób. Algorytmy mieszania są duże; FNV-1a jest liniowy względem liczby bajtów w źródle, ale nie znamy żadnej części końcowego skrótu, dopóki pełne źródło nie zostanie przetworzone.

RadixSort, czyli BucketSort, to O (N) (technicznie O (NlogM), gdzie M to maksymalna wartość w N elementach, która jest uważana za małą) i musi działać w całości, aby zagwarantować, że każdy pojedynczy element znajdzie się na ostatnim miejscu.

Aby być algorytmem „strumieniowym”, w najprostszym przypadku algorytm musi mieć następujące dwie właściwości, z których żadna nie jest wyraźnie związana z czasem:

Lepsza niż złożoność przestrzeni O (N) (podane równoważnie, całe źródło nie musi być znane i cały wynik nie musi być przechowywany)
Zależność we / wy O (N) (algorytm wytwarza szereg wyników liniowo proporcjonalnych do swoich danych wejściowych)

Dlatego główną klasą algorytmów tego strumienia są algorytmy wykonujące „projekcje” (przyrostowe transformacje jednego wejścia na X> 0 wyjść).

KeithS
źródło

Dlaczego miałby

O (\log n)

$O(\log n)$ wykorzystanie miejsca nie jest w porządku? Artykuły powiązane z drugim pytaniem bawią się przy użyciu wielu algorytmów przesyłania strumieniowego

ω (1)

$\omega(1)$ przestrzeń.

Raphael

logN też jest w porządku; Chodziło o to, że algorytm nie powinien wymagać znajomości całego wejścia lub wyjścia naraz.

KeithS,

Na

Ω (n)

$\Omega(n)$ Wymagane miejsce nie oznacza, że potrzebuje całego poręcznego wejścia (tj. nie jest to algorytm przesyłania strumieniowego). Ale rozumiem o co ci chodzi.

Raphael

Czy każdy algorytm czasu liniowego jest algorytmem przesyłania strumieniowego?

Odpowiedzi: