examples - algorithms book
Log combing algorithm (6)
Obtenemos estos ~ 50GB de archivos de datos que constan de códigos de 16 bytes, y quiero encontrar cualquier código que ocurra el 1/2% del tiempo o más. ¿Hay alguna manera de hacerlo en un solo paso sobre los datos?
Editar: hay toneladas de códigos; es posible que cada código sea diferente.
EPILOGO: He seleccionado a Darius Bacon como la mejor respuesta, porque creo que el mejor algoritmo es una modificación del elemento de la mayoría al que se vinculó. El algoritmo de la mayoría debe ser modificable para usar solo una pequeña cantidad de memoria, como 201 códigos para obtener el 1/2%, creo. Básicamente, simplemente recorre la corriente contando hasta 201 códigos distintos. Tan pronto como encuentre 201 códigos distintos, soltará uno de cada código (resta 1 de los contadores, olvidando cualquier cosa que se convierta en 0). Al final, ha caído como máximo N / 201 veces, por lo que cualquier código que ocurra más veces debe estar disponible.
Pero es un algoritmo de dos pasos, no uno. Necesitas un segundo pase para contar los conteos de los candidatos. En realidad, es fácil ver que cualquier solución a este problema debe usar al menos 2 pases (el primer lote de elementos que cargues podría ser diferente y uno de esos códigos podría llegar a ser exactamente el 1/2%)
¡Gracias por la ayuda!
Eso depende de cuántos códigos diferentes existan y cuánta memoria tenga disponible.
Mi primera idea sería construir una tabla hash de contadores, con los códigos como claves. Pasa por el archivo completo, aumentando el contador del código respectivo y contando el número total. Finalmente, filtre todas las claves con contadores que excedan (* contador general 1/200).
Si los archivos consisten únicamente en códigos de 16 bytes y usted sabe qué tamaño tiene cada archivo, puede calcular la cantidad de códigos en cada archivo. Luego puede encontrar el umbral de 0.5% y seguir cualquiera de las otras sugerencias para contar las ocurrencias de cada código, registrando cada uno cuya frecuencia cruza el umbral.
esto dependerá de la distribución de los códigos. si hay un número suficientemente pequeño de códigos distintos, puede crear un http://en.wikipedia.org/wiki/Frequency_distribution en el núcleo con un mapa. de lo contrario, probablemente tendrá que crear un http://en.wikipedia.org/wiki/Histogram y luego hacer múltiples pasadas sobre las frecuencias de examen de datos de los códigos en cada segmento.
¿El contenido de cada archivo representa un solo conjunto de datos, o hay un límite arbitrario entre los archivos? En el último caso, y suponiendo una distribución bastante constante de códigos a lo largo del tiempo, puede simplificar su vida dividiendo cada archivo en fragmentos más pequeños y manejables. Como beneficio adicional, obtendrás resultados preliminares más rápido y podrás pasar al siguiente proceso más temprano.
Ordene trozos del archivo en la memoria, como si estuviese ejecutando y ordenando de forma externa. Sin embargo, en lugar de escribir todos los códigos ordenados en cada fragmento, puede simplemente escribir cada código distinto y el número de ocurrencias en ese fragmento. Finalmente, combine estos registros de resumen para encontrar el número de ocurrencias de cada código.
Este proceso escala a cualquier tamaño de datos, y solo hace una pasada sobre los datos de entrada. Es posible que se requieran varias fusiones, dependiendo de la cantidad de archivos de resumen que quiera abrir a la vez.
Ordenar el archivo le permite contar el número de ocurrencias de cada código utilizando una cantidad fija de memoria, independientemente del tamaño de la entrada.
También conoce el número total de códigos (dividiendo el tamaño de entrada por un tamaño de código fijo o contando el número de códigos de longitud variable durante el paso de clasificación en un problema más general).
Entonces, usted sabe la proporción de la entrada asociada con cada código.
Esto es básicamente el sort * | uniq -c tubería sort * | uniq -c sort * | uniq -c
Si cada código aparece solo una vez, no hay problema; solo necesitas poder contarlos.
Metwally et al., Computación eficiente de elementos frecuentes y Top-k en flujos de datos (2005) . Hubo algunos otros documentos relevantes que leí para mi trabajo en Yahoo que no puedo encontrar ahora; pero esto parece un buen comienzo.
Editar: Ah, mira este artículo de Brian Hayes . Esboza un algoritmo exacto debido a Demaine et al., Con referencias. Lo hace de una sola pasada con muy poca memoria, produciendo un conjunto de elementos, incluidos los frecuentes que estás buscando, si es que existen. Obtener los recuentos exactos requiere un segundo pase (ahora tratable).