Algoritmo de flujo de datos

En informática , un algoritmo de flujo de datos es un algoritmo , los datos de uno o más flujos de datos se leen secuencialmente y, por lo tanto, se procesan directamente ("en línea").

solicitud

Muchas de las aplicaciones actuales de la informática hacen necesario procesar un flujo de datos debido a la gran cantidad de datos que se suministran continuamente . Este es el caso, por ejemplo, al registrar datos de enrutamiento en redes, al registrar datos de telecomunicaciones, durante transacciones bancarias o con tickers bursátiles .

Perspectiva matemática y requisitos de eficiencia.

Los datos que se acumulan continuamente se modelan como una secuencia, una secuencia de caracteres de entrada, cuya longitud a menudo se desconoce, pero se supone que es muy grande.

Un algoritmo que procesa el flujo solo puede leer carácter por carácter del flujo, acceso aleatorio, i. H. No se permite "saltar" a los caracteres de entrada.

En el escenario de flujo de datos, existen esencialmente dos requisitos de eficiencia debido a la cantidad de datos generados: La complejidad del espacio de almacenamiento del algoritmo de flujo de datos debe ser sub-lineal, idealmente logarítmica o polilogarítmica, así como el tiempo de cálculo por carácter de entrada .

Por lo tanto, ciertos problemas se pueden resolver con precisión con algoritmos de flujo de datos, ya que se puede leer toda la entrada. Sin embargo, el espacio de almacenamiento sublineal y el tiempo de cálculo sublineal por carácter de entrada son requisitos de eficiencia que a menudo conducen al hecho de que esto simplemente no es posible y solo se pueden dar soluciones aproximadas y se debe utilizar la aleatorización.

Porque es posible que un algoritmo de flujo de datos no guarde toda la entrada debido al espacio de almacenamiento sublineal, sino solo un resumen de lo que se ha visto hasta ahora. Se dice que el algoritmo guarda un boceto de la entrada vista hasta ahora.

En el siguiente ejemplo se presenta un algoritmo que puede resolver exactamente el problema dado.

Ejemplos

Numero de elementos

El número de elementos en un flujo de datos se puede determinar fácilmente con un contador. El requisito de memoria se puede reducir aún más con algoritmos aleatorios.

Numero faltante

Dejado ser una permutación de la serie con un elemento que falta . ${\ Displaystyle \ pi}$ ${\ Displaystyle \ {1, ..., n \}}$ ${\ Displaystyle s}$

Una forma sencilla de encontrar el número que falta sería recopilar todos los números, ordenarlos y luego buscar en ese conjunto ordenado el elemento que falta. Sin embargo, para hacer esto, todos los números deberían guardarse como se describe. El consumo de memoria de este algoritmo es de bytes si se supone que cada número se almacena como un entero de 32 bits . Por ejemplo, tendría que ahorrar alrededor de 3,7 GB. Para lograr un rendimiento adecuado, estos datos deberían almacenarse en la memoria principal, pero esto no es posible con la mayoría de las PC debido al gran volumen de datos. Esto significa que habría que acceder al disco duro, lo que, sin embargo, ralentiza enormemente este algoritmo. ${\ Displaystyle n \ cdot 4}$ ${\ Displaystyle n = 1,000,000,000}$

Si todos los números estuvieran contenidos en el flujo de datos, la suma de los elementos del flujo estaría de acuerdo con la fórmula de la suma de Gauss . Por lo tanto, tomando la suma de la potencia contenida en los elementos , por lo que puede el número buscado después de leer la entrada completa a determinar. Este algoritmo solo necesita guardar un número para calcular la suma y luego determinarla, por lo que el espacio de memoria es solo O (log n). Obviamente, es más eficiente. ${\ 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}} - \ sum {\ pi}}$ ${\ Displaystyle s}$