Datenstromalgorithmus
Die Informatik bezeichnet mit Datenstromalgorithmus einen Algorithmus, der die Daten eines Datenstroms sequenziell bearbeitet und dabei nur eine kleine Zusammenfassung speichert.
Anwendung
Viele heutige Anwendungen in der Informatik machen auf Grund der extrem großen, kontinuierlich angelieferten Datenmenge, die Verarbeitung eines Datenstroms erforderlich. Dies ist beispielsweise bei der Erfassung von Routingdaten in Netzwerken, bei Aufzeichnungen von Telekommunikationsdaten, bei Banktransaktionen oder bei Börsentickern der Fall. Die dort anfallenden Daten haben kein Ende und müssen deshalb sequentiell ausgewertet werden. Auch ist die Datenmenge zumeist so hoch, dass sie von nicht auf ein Mal ausgewertet werden könnte.
Beispiel: Fehlende Zahl
Sei eine Permutation der Zahlenmenge mit einem fehlenden Element .
Ein einfache Methode zur Bestimmung der fehlendes Zahl wäre, alle Zahlen zu sammeln, zu sortieren und diese geordnete Menge dann der Reihe nach auf das fehlende Element zu durchsuchen. Dazu müssten aber wie beschrieben alle Zahlen gespeichert werden. Der Speicherverbrauch dieses Algorithmus beträgt dann Bytes, wenn angenommen wird, das jede Zahl als 32-Bit Integer gespeichert wird. So müsste man bspw. für ca. 3,7 GB Speichern. Um eine angemessene Performance zu erreichen müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist auf Grud des großen Datenvolumens bei den meisten PCs nicht möglich. Somit müsste auf die Festplatte zurückgegriffen werden, was jedoch diesen Algorithmus extrem verlangsammt.
Wie sich mathematisch beweisen lässt, ist die Bestimmung der fehlenden Zahl jedoch auch mit folgendem Datenstromalgorithmus möglich:
Dieser Algorithmus muss zur Berechnung der Summe und anschließend daraus s nur eine Zahl speichern und ist damit offensichtlich effizienter.
Siehe auch
Weblinks
"Data Streams: Algorithms and Applications" von S. Muthukrishnan (Postscript)