¿Qué es un buen algoritmo para la estimación de la mediana de una enorme leer-una vez que el conjunto de datos?

Question

Estoy buscando un buen algoritmo (el significado de los cálculos mínimos, mínimos requisitos de almacenamiento) para calcular la mediana de un conjunto de datos es demasiado grande para almacenar, de tal manera que cada valor se puede leer sólo una vez (a menos que explícitamente almacenar ese valor). No hay límites en los datos que pueden ser asumidos.

Aproximaciones están bien, siempre y cuando la exactitud es conocido.

Alguna sugerencia?

Answer 1

¿Algo así como un agrupamiento procedimiento? Supongamos (para fines de ilustración) que sabe que los valores están entre 1 y 1 millón de dólares. Configurar N papeleras, de tamaño S. Así que si S=10000, tendría 100 contenedores de basura, correspondiente a los valores de [1:10000, 10001:20000, ... , 990001:1000000]

A continuación, paso a través de los valores. En lugar de almacenar cada valor, incrementar el contador en el adecuado reciclaje. Utilizando el punto medio de cada intervalo como una estimación, usted puede hacer una aproximación razonable de la mediana. Se puede escalar hasta el fina o gruesa de una resolución en la que desee cambiar el tamaño de los recipientes. Usted está limitado sólo por la cantidad de memoria que tiene.

Ya que no sé cómo de grande sus valores puede conseguir, solo tienes que elegir un tamaño de un recipiente lo suficientemente grande que usted no es probable que se ejecute fuera de la memoria, mediante una rápida vuelta-de-la-envoltura cálculos. También puede almacenar los contenedores escasamente, de tal forma que solo agregar una bandeja si contiene un valor.

Editar:

El enlace ryfm ofrece un ejemplo de hacer esto, con el paso adicional de utilizar el acumulado de los porcentajes para estimar con mayor precisión el punto dentro de la mediana de reciclaje, en lugar de utilizar medios. Esta es una buena mejora.

Answer 2

Me re-directo a mi respuesta a semejante pregunta. En pocas palabras, es un leen una vez, 'sobre la marcha' algoritmo con $O(n)$ peor de los casos la complejidad para calcular el (exacta) de la mediana.

Answer 3

He implementado el P-Square Algoritmo para el Cálculo Dinámico de Cuantiles y los Histogramas sin Almacenar las Observaciones en una casa de módulo de Python que escribí llamado LiveStats. Debería resolver su problema de una manera bastante eficaz.

Answer 4

El Rivest-Tarjan-algoritmo de Selección (también llamado a veces la mediana de las medianas algoritmo) te permitirá calcular la mediana elemento lineal de tiempo sin ningún tipo de clasificación. Para conjuntos de datos grandes, esto puede ser un poco más rápido que log-lineal de la clasificación. Sin embargo, no va a resolver su memoria de almacenamiento de problema.