Ist jeder Linearzeit-Algorithmus ein Streaming-Algorithmus?

Drüben bei dieser Frage um die Inversionszählung , ich fand ein Papier , das für alle (genau) eine untere Schranke für Speicherkomplexität beweist Streaming - Algorithmen . Ich habe behauptet, dass diese Schranke sich auf alle linearen Zeitalgorithmen erstreckt. Dies ist ein bisschen fett, da im Allgemeinen ein linearer Zeitalgorithmus nach Belieben herumspringen kann (Direktzugriff), was ein Streaming-Algorithmus nicht kann; Es muss die Elemente in der richtigen Reihenfolge untersuchen. Ich kann mehrere Durchläufe durchführen, aber nur konstant viele (für lineare Laufzeit).

Daher meine Frage:

Kann jeder Linearzeitalgorithmus als Streaming-Algorithmus mit konstant vielen Durchläufen ausgedrückt werden?

Zufälliger Zugriff scheint zu verhindern, dass eine (einfache) Konstruktion eine positive Antwort liefert, aber ich konnte auch kein Gegenbeispiel finden.

Abhängig vom Maschinenmodell ist der wahlfreie Zugriff möglicherweise nicht einmal ein Problem, was die Laufzeit betrifft. Ich würde mich für Antworten zu diesen Modellen interessieren:

• Turingmaschine, flacher Eingang
• RAM, Eingabe als Array
• RAM, Eingabe als verkettete Liste

Damit Streaming-Algorithmen sinnvoll sind, müssen sie mit einem wesentlich geringeren Arbeitsbereich als die Eingabe selbst arbeiten. Wenn Sie beispielsweise den gleichen Arbeitsbereich wie die Eingabe zulassen, können Sie jeden Algorithmus einfach als "Single-Pass-Streaming-Algorithmus" angeben, der die Eingabe zunächst in einem Durchgang in den Arbeitsbereich kopiert und dann nur die Arbeit verwendet Raum.

Ich denke, dass es typisch ist, den Arbeitsbereich auf höchstens polylogarithmisch in der Eingabegröße zu beschränken, wenn es um Streaming-Algorithmen geht. Unter dieser Annahme hat die Medianauswahl keinen O (1) -Pass-Streaming-Algorithmus nach Munro und Paterson [MP80]: Jeder P- Pass-Streaming-Algorithmus für die Medianauswahl an N Elementen muss Ω ( N ^{1 / P} speichern ) Elemente. Andererseits verfügt die Medianauswahl über einen bekannten deterministischen linearen Zeitalgorithmus [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest und Robert E. Tarjan. Fristen für die Auswahl. Journal of Computer and System Sciences , 7 (4): 448–461, Aug. 1973. DOI: 10.1016 / S0022-0000 (73) 80033-9

[MP80] J. Ian Munro und Mike S. Paterson. Auswahl und Sortierung mit begrenztem Speicherplatz. Theoretical Computer Science , 12 (3): 315–323, November 1980. DOI: 10.1016 / 0304–3975 (80) 90061–4

Im Streaming-Modell dürfen Sie nur konstante oder polylogarithmische Zusatzdaten speichern, während Sie die Eingabe durchsuchen. Wenn Sie einen linearen Zeitalgorithmus in Betracht ziehen
, der dem Paradigma der Division und Überwindung folgt , müssen Sie mehr Informationen speichern und / oder Ihre Daten so oft durchsuchen, wie die Tiefe der Rekursion beträgt.

Ein Beispiel ist der DC3-Algorithmus zum Aufbau des Suffix-Arrays eines Textes (im RAM-Modell als Array angegeben). Um ein Suffix-Array zu erstellen, gruppieren Sie die Zeichen in Triplets, sodass Sie einen Text mit neuen Superzeichen erhalten . Sie können dies mit einem Versatz von 0 , 1 , 2 tun , was zu drei neuen Texten T 1 , T 2 , T 3 führt . Interessanterweise können Sie das Suffix-Array berechnen, wenn Sie das Suffix-Array von T 1 ⋅ T 2 in linearer Zeit haben. Daher braucht der Algorithmus$T$$0,1,2$$T_1,T_2,T_3$$T_1\cdot T_2$

Zeit. Diese Rekursion löst sich eindeutig zu . Ich verstehe nicht, wie dies in einen Streaming-Algorithmus umgewandelt werden kann.$t(n)=O(n)$

Ein weiteres bekanntes Beispiel ist der klassische Auswahlalgorithmus für die lineare Zeit .

$P$

• $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)$

Selbst in der einfachsten Definition von "Streaming-Algorithmus" (ein Algorithmus, der nach jeder inkrementellen Iteration in der Quelle die sofortige Kenntnis des nächsten inkrementellen Teils des Ergebnisses ergibt), kann ich mir ein paar lineare Algorithmen vorstellen, die dies nicht tun benimm dich so. Hashing-Algorithmen sind sehr umfangreich. FNV-1a ist linear zur Anzahl der Bytes in der Quelle, aber wir kennen keinen Teil des endgültigen Hashs, bis die vollständige Quelle verarbeitet wurde.

RadixSort alias BucketSort ist O (N) (technisch O (NlogM), wobei M der Maximalwert in den N Elementen ist, der als klein angesehen wird) und muss vollständig ausgeführt werden, um zu gewährleisten, dass sich jedes einzelne Element an seinem endgültigen Platz befindet.

Um ein "Streaming" -Algorithmus zu sein, muss ein Algorithmus im einfachsten Fall die folgenden zwei Eigenschaften aufweisen, von denen keine ausdrücklich zeitgebunden ist:

• Besser als O (N) Raumkomplexität (äquivalent ausgedrückt, muss die gesamte Quelle nicht bekannt sein und das gesamte Ergebnis muss nicht gespeichert werden)
• O (N) I / O-Beziehung (der Algorithmus erzeugt eine Reihe von Ausgaben, die linear proportional zu seinen Eingaben sind)

Daher ist die Hauptklasse von Algorithmen, die Daten streamen, die von Algorithmen, die "Projektionen" ausführen (inkrementelle Transformationen von einem Eingang zu X> 0 Ausgängen).