Datenstromalgorithmus - Versionsgeschichte

Boehm: typog

2022-07-18T21:49:57Z

typog

← Nächstältere Version		Version vom 18. Juli 2022, 23:49 Uhr
Zeile 9:		Zeile 9:
	Man modelliert die kontinuierlich anfallenden Daten als Strom – eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.		Man modelliert die kontinuierlich anfallenden Daten als Strom – eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.

	Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d. h. ein ~~"Springen"~~ auf den Eingabezeichen, ist nicht erlaubt.		Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d. h. ein „Springen“ auf den Eingabezeichen, ist nicht erlaubt.

	Im Datenstromszenario werden wegen der Menge der anfallenden Daten im Wesentlichen zwei Effizienzforderungen gestellt: Die Speicherplatzkomplexität des Datenstromalgorithmus soll sublinear, idealerweise [[Logarithmus\|logarithmisch]] oder polylogarithmisch sein, ebenso wie die Rechenzeit ''pro Eingabezeichen''.		Im Datenstromszenario werden wegen der Menge der anfallenden Daten im Wesentlichen zwei Effizienzforderungen gestellt: Die Speicherplatzkomplexität des Datenstromalgorithmus soll sublinear, idealerweise [[Logarithmus\|logarithmisch]] oder polylogarithmisch sein, ebenso wie die Rechenzeit ''pro Eingabezeichen''.
Zeile 26:		Zeile 26:
	=== Fehlende Zahl ===		=== Fehlende Zahl ===

	Sei <math>\pi</math> eine [[Permutation]] der [[Menge (Mathematik)\|Zahlenmenge]] <math>\{1, ~~...~~, n\}</math> mit einem fehlenden Element <math>s</math>.		Sei <math>\pi</math> eine [[Permutation]] der [[Menge (Mathematik)\|Zahlenmenge]] <math>\{1, \dots, n\}</math> mit einem fehlenden Element <math>s</math>.

	Eine einfache Methode zur Bestimmung der fehlenden Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.		Eine einfache Methode zur Bestimmung der fehlenden Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.

	Wären alle Zahlen <math>1, ~~...~~, n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.		Wären alle Zahlen <math>1, \dots, n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]]
			:<math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.
	Bildet man daher die Summe der im Strom enthaltenen <math>n-1</math> Elemente in <math>\pi</math>, so kann man nach Lesen der gesamten Eingabe die gesuchte Zahl <math>s</math> mit <math>s = \frac{n(n + 1)}{2} - \sum{\pi}</math> bestimmen.		Bildet man daher die Summe der im Strom enthaltenen <math>n-1</math> Elemente in <math>\pi</math>, so kann man nach Lesen der gesamten Eingabe die gesuchte Zahl <math>s</math> mit
			:<math>s = \frac{n(n + 1)}{2} - \sum{\pi}</math>
			bestimmen.
	Dieser Algorithmus muss zur Berechnung der Summe und zur anschließenden Bestimmung von <math>s</math> nur eine Zahl speichern und der Speicherplatz beträgt damit nur O(log n). Er ist damit ganz offensichtlich effizienter.		Dieser Algorithmus muss zur Berechnung der Summe und zur anschließenden Bestimmung von <math>s</math> nur eine Zahl speichern und der Speicherplatz beträgt damit nur <math>\mathcal O(\log(n))</math>. Er ist damit ganz offensichtlich effizienter.

	== Siehe auch ==		== Siehe auch ==

Aka: /* Weblinks */ https

2021-01-12T14:52:17Z

Weblinks: https

← Nächstältere Version		Version vom 12. Januar 2021, 16:52 Uhr
Zeile 38:		Zeile 38:

	== Weblinks ==		== Weblinks ==
	* [~~http~~://~~athos~~.rutgers.edu/~muthu/stream-1-1.ps "Data Streams: Algorithms and Applications" von S. Muthukrishnan (Postscript)]		* [https://www.cs.rutgers.edu/~muthu/stream-1-1.ps "Data Streams: Algorithms and Applications" von S. Muthukrishnan (Postscript)]

	[[Kategorie:Algorithmus]]		[[Kategorie:Algorithmus]]

Aka: Halbgeviertstrich

2018-10-18T15:25:05Z

Halbgeviertstrich

← Nächstältere Version		Version vom 18. Oktober 2018, 17:25 Uhr
Zeile 7:		Zeile 7:
	== Mathematische Sichtweise und Effizienzanforderungen ==		== Mathematische Sichtweise und Effizienzanforderungen ==

	Man modelliert die kontinuierlich anfallenden Daten als Strom - eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.		Man modelliert die kontinuierlich anfallenden Daten als Strom – eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.

	Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d. h. ein "Springen" auf den Eingabezeichen, ist nicht erlaubt.		Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d. h. ein "Springen" auf den Eingabezeichen, ist nicht erlaubt.
Zeile 17:		Zeile 17:
	Denn ein Datenstromalgorithmus darf wegen des nur sublinearen Speicherplatzes nicht die gesamte Eingabe speichern, sondern nur eine Zusammenfassung des bisher Gesehenen. Man sagt, der Algorithmus speichert eine Skizze (Sketch) der bisher gesehenen Eingabe.		Denn ein Datenstromalgorithmus darf wegen des nur sublinearen Speicherplatzes nicht die gesamte Eingabe speichern, sondern nur eine Zusammenfassung des bisher Gesehenen. Man sagt, der Algorithmus speichert eine Skizze (Sketch) der bisher gesehenen Eingabe.

	Im folgenden Beispiel wird ein Algorithmus vorgestellt, der das gegebene Problem exakt lösen kann.		Im folgenden Beispiel wird ein Algorithmus vorgestellt, der das gegebene Problem exakt lösen kann.

	== Beispiele ==		== Beispiele ==
Zeile 30:		Zeile 30:
	Eine einfache Methode zur Bestimmung der fehlenden Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.		Eine einfache Methode zur Bestimmung der fehlenden Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.

	Wären alle Zahlen <math>1, ..., n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.		Wären alle Zahlen <math>1, ..., n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.
	Bildet man daher die Summe der im Strom enthaltenen <math>n-1</math> Elemente in <math>\pi</math>, so kann man nach Lesen der gesamten Eingabe die gesuchte Zahl <math>s</math> mit <math>s = \frac{n(n + 1)}{2} - \sum{\pi}</math> bestimmen.		Bildet man daher die Summe der im Strom enthaltenen <math>n-1</math> Elemente in <math>\pi</math>, so kann man nach Lesen der gesamten Eingabe die gesuchte Zahl <math>s</math> mit <math>s = \frac{n(n + 1)}{2} - \sum{\pi}</math> bestimmen.
	Dieser Algorithmus muss zur Berechnung der Summe und zur anschließenden Bestimmung von <math>s</math> nur eine Zahl speichern und der Speicherplatz beträgt damit nur O(log n). Er ist damit ganz offensichtlich effizienter.		Dieser Algorithmus muss zur Berechnung der Summe und zur anschließenden Bestimmung von <math>s</math> nur eine Zahl speichern und der Speicherplatz beträgt damit nur O(log n). Er ist damit ganz offensichtlich effizienter.

Aka: Abkürzung korrigiert

2018-02-13T18:40:24Z

Abkürzung korrigiert

← Nächstältere Version		Version vom 13. Februar 2018, 20:40 Uhr
Zeile 9:		Zeile 9:
	Man modelliert die kontinuierlich anfallenden Daten als Strom - eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.		Man modelliert die kontinuierlich anfallenden Daten als Strom - eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.

	Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d.h. ein "Springen" auf den Eingabezeichen, ist nicht erlaubt.		Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d. h. ein "Springen" auf den Eingabezeichen, ist nicht erlaubt.

	Im Datenstromszenario werden wegen der Menge der anfallenden Daten im Wesentlichen zwei Effizienzforderungen gestellt: Die Speicherplatzkomplexität des Datenstromalgorithmus soll sublinear, idealerweise [[Logarithmus\|logarithmisch]] oder polylogarithmisch sein, ebenso wie die Rechenzeit ''pro Eingabezeichen''.		Im Datenstromszenario werden wegen der Menge der anfallenden Daten im Wesentlichen zwei Effizienzforderungen gestellt: Die Speicherplatzkomplexität des Datenstromalgorithmus soll sublinear, idealerweise [[Logarithmus\|logarithmisch]] oder polylogarithmisch sein, ebenso wie die Rechenzeit ''pro Eingabezeichen''.

BlueBreezeWiki: + fr

2015-09-23T06:15:44Z

+ fr

← Nächstältere Version		Version vom 23. September 2015, 08:15 Uhr
Zeile 42:		Zeile 42:
	[[Kategorie:Algorithmus]]		[[Kategorie:Algorithmus]]
	[[en:streaming algorithm]]		[[en:streaming algorithm]]
			[[fr:Algorithme de fouille de flots de données]]

2A02:AA13:E100:3780:BA76:3FFF:FEE9:6CCF am 1. September 2015 um 19:18 Uhr

2015-09-01T19:18:49Z

← Nächstältere Version		Version vom 1. September 2015, 21:18 Uhr
Zeile 41:		Zeile 41:

	[[Kategorie:Algorithmus]]		[[Kategorie:Algorithmus]]
			[[en:streaming algorithm]]

141.58.55.153: /* Fehlende Zahl */

2014-02-06T17:39:18Z

Fehlende Zahl

← Nächstältere Version		Version vom 6. Februar 2014, 19:39 Uhr
Zeile 28:		Zeile 28:
	Sei <math>\pi</math> eine [[Permutation]] der [[Menge (Mathematik)\|Zahlenmenge]] <math>\{1, ..., n\}</math> mit einem fehlenden Element <math>s</math>.		Sei <math>\pi</math> eine [[Permutation]] der [[Menge (Mathematik)\|Zahlenmenge]] <math>\{1, ..., n\}</math> mit einem fehlenden Element <math>s</math>.

	~~Ein~~ einfache Methode zur Bestimmung der ~~fehlendes~~ Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.		Eine einfache Methode zur Bestimmung der fehlenden Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.

	Wären alle Zahlen <math>1, ..., n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.		Wären alle Zahlen <math>1, ..., n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.

193.101.24.3 am 9. September 2013 um 11:24 Uhr

2013-09-09T11:24:25Z

← Nächstältere Version		Version vom 9. September 2013, 13:24 Uhr
Zeile 1:		Zeile 1:
	In der [[Informatik]] ist ein '''Datenstromalgorithmus''' ein [[Algorithmus]], der die Daten eines oder mehrerer [[Datenstrom\|Datenströme]]s sequenziell liest und dabei direkt („online“) verarbeitet.		In der [[Informatik]] ist ein '''Datenstromalgorithmus''' ein [[Algorithmus]], der die Daten eines oder mehrerer [[Datenstrom\|Datenströme]] sequenziell liest und dabei direkt („online“) verarbeitet.

	== Anwendung ==		== Anwendung ==

Woches: /* Literatur */ fix

2013-08-04T06:57:24Z

Literatur: fix

← Nächstältere Version		Version vom 4. August 2013, 08:57 Uhr
Zeile 36:		Zeile 36:
	== Siehe auch ==		== Siehe auch ==
	* [[Platzkomplexität]]		* [[Platzkomplexität]]

	== Literatur ==

	== Weblinks ==		== Weblinks ==

Aka: zu großen Zeilenabstand entfernt

2013-03-11T20:48:55Z

zu großen Zeilenabstand entfernt

← Nächstältere Version		Version vom 11. März 2013, 22:48 Uhr
Zeile 38:		Zeile 38:

	== Literatur ==		== Literatur ==


	== Weblinks ==		== Weblinks ==

← Nächstältere Version		Version vom 6. Februar 2014, 19:39 Uhr
Zeile 28:		Zeile 28:
	Sei <math>\pi</math> eine [[Permutation]] der [[Menge (Mathematik)\|Zahlenmenge]] <math>\{1, ..., n\}</math> mit einem fehlenden Element <math>s</math>.		Sei <math>\pi</math> eine [[Permutation]] der [[Menge (Mathematik)\|Zahlenmenge]] <math>\{1, ..., n\}</math> mit einem fehlenden Element <math>s</math>.

	~~Ein~~ einfache Methode zur Bestimmung der ~~fehlendes~~ Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.		Eine einfache Methode zur Bestimmung der fehlenden Zahl wäre, alle Zahlen zu sammeln, zu [[Sortierverfahren\|sortieren]] und diese geordnete [[Menge (Mathematik)\|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 <math>n \cdot 4</math> Bytes, wenn angenommen wird, dass jede Zahl als 32-Bit [[Integer (Datentyp)\|Integer]] gespeichert wird. So müsste man bspw. für <math>n = 1.000.000.000</math> ca. 3,7 GB speichern. Um eine angemessene Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.

	Wären alle Zahlen <math>1, ..., n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.		Wären alle Zahlen <math>1, ..., n</math> im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der [[Gaußsche Summenformel\|Gaußschen Summenformel]] <math>\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}</math>.