Clasificación externa de cadenas con restricciones de memoria, con duplicados combinados y contados, en un servidor crítico (miles de millones de nombres de archivos)

Nuestro servidor produce archivos como {c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml en su carpeta de registro. La primera parte es GUID; la segunda parte es plantilla de nombre.

Quiero contar la cantidad de archivos con la misma plantilla de nombre. Por ejemplo, tenemos

 {c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml {aa3718d1-98e2-4559-bab0-1c69f04eb7ec}-hero.xml {0c7a50dc-972e-4062-a60c-062a51c7b32c}-sign.xml 

El resultado debe ser

 sign.xml,2 hero.xml,1 

El tipo total de plantillas de nombre posibles es desconocido, posiblemente excede int.MaxValue .

La cantidad total de archivos en el servidor es desconocida, posiblemente excede int.MaxValue .

Requisitos :

El resultado final debe ordenarse por plantilla de nombre.

El servidor en el que se ejecutará la herramienta es súper crítico. Deberíamos poder contar el uso de memoria (MB) y la cantidad de archivos temporales generados, si los hay, antes de ejecutar la herramienta y sin conocer ninguna característica de la carpeta de registro.

Usamos el lenguaje C #.

Mi idea

  • Para los primeros 5000 archivos, cuente las ocurrencias, escriba el resultado en Group1.txt .
  • Para los segundos 5000 archivos, cuente las ocurrencias, escriba el resultado en Group2.txt .
  • Repita hasta que se procesen todos los archivos. Ahora tenemos un grupo de archivos de grupo.

Luego fusiono todos estos archivos de grupo.

  Group1.txt Group2.txt Group3.txt Group4.txt \ / \ / Group1-2.txt Group3-4.txt \ / Group1-4.txt 

Group1-4.txt es el resultado final.

El desacuerdo entre mi amigo y yo es cómo contamos las ocurrencias.

Sugiero usar el diccionario. La plantilla de nombre de archivo es la clave. Deje que m sea el tamaño de la partición. (En este ejemplo, es 5000). Luego la complejidad del tiempo O (m), la complejidad del espacio O (m).

Mi amigo sugiere ordenar la plantilla de nombre y luego contar la ocurrencia en una sola pasada, ya que las mismas plantillas de nombres ahora están juntas. complejidad del tiempo O (m log m), complejidad del espacio O (m).

No podemos convencernos el uno al otro. ¿Ustedes ven algún problema de los dos métodos?

IDK si se ha estudiado la clasificación externa con recuento de duplicados. Encontré un documento de 1983 (ver abajo). Por lo general, los algoritmos de clasificación se diseñan y estudian con la suposición de clasificar los objetos por claves, por lo que las claves duplicadas tienen diferentes objetos. Puede haber literatura existente sobre esto, pero es un problema muy interesante. Probablemente solo se considere una aplicación de diccionarios compactos combinados con la clasificación de fusión externa.

Diccionarios eficientes para almacenar grandes cantidades de cadenas en poca memoria es un problema muy bien estudiado. La mayoría de las estructuras de datos útiles pueden incluir datos auxiliares para cada palabra (en nuestro caso, un conteo dup).


TL: DR resumen de ideas útiles, ya que divagué en demasiados detalles sobre muchas cosas en el cuerpo principal de esta respuesta:

  • Límites de lote cuando el tamaño de su diccionario alcanza un umbral, no después de un número fijo de archivos de entrada. Si hubiera muchos duplicados en un grupo de 5000 cadenas, todavía no usará mucha memoria. Puedes encontrar más duplicados en el primer pase de esta manera.

  • Los lotes ordenados hacen que la fusión sea mucho más rápida. Puede y debe combinar muchos-> uno en lugar de fusión binaria. Use una Prioridad para descubrir qué archivo de entrada tiene la línea que debe tomar a continuación.

  • Para evitar un estallido de uso de memoria al ordenar las claves en una tabla hash, use un diccionario que pueda hacer un cruce de claves en orden. (es decir, ordena sobre la marcha). SortedDictionary (basado en un árbol binario). Esto también intercala el uso de clasificación de la CPU con la espera de E / S para obtener las cadenas de entrada.

  • Radix: ordena cada lote en salidas por el primer carácter (az, no alfabético que ordena antes que A , y no alfabético que ordena después de z ). O alguna otra opción de cubicación que distribuya bien tus llaves. Use diccionarios separados para cada cubo de radix, y vacíe solo el más grande en un lote cuando llegue al techo de la memoria. (La heurística de desalojo más elegante que la “más grande” puede valer la pena).

  • aceleración de E / S (especialmente al fusionarse), y verificar la carga de la CPU del sistema y la presión de la memoria. Adapte el comportamiento en consecuencia para asegurarse de no causar un impacto cuando el servidor está más ocupado.

  • Para archivos temporales más pequeños a costa del tiempo de CPU, use una encoding de prefijo común, o tal vez lz4.

  • Un diccionario con uso eficiente del espacio permitirá tamaños de lote más grandes (y por lo tanto una ventana de búsqueda de duplicados más grande) para el mismo límite superior de memoria. Un Trie (o mejor, Radix Trie ) podría ser ideal, ya que almacena los caracteres dentro de los nodos del árbol, con prefijos comunes almacenados solo una vez. Los gráficos de palabras acíclicas dirigidas son aún más compactos (encontrando redundancia entre subcadenas comunes que no son prefijos). Usar uno como diccionario es complicado pero probablemente posible (ver a continuación).

  • Aproveche el hecho de que no necesita eliminar ningún nodo de árbol o cadena hasta que vaya a vaciar todo el diccionario. Use una matriz de nodos cultivable y otra matriz de caracteres cultivable que empaqueta cadenas de la cabeza a la cola. (Útil para un Radix Trie (nodos multi-char), pero no un Trie regular donde cada nodo es un solo carácter).

  • Dependiendo de cómo se distribuyan los duplicados, puede o no ser capaz de encontrar muchos en el primer pase. Esto tiene algunas implicaciones, pero realmente no cambia la forma en que terminas fusionándote.


Supongo que tiene en mente alguna idea de recorrido de directorios, que puede suministrar de manera eficiente su código con un flujo de cadenas para ser uniquified y contado. Así que solo diré “cadenas” o “claves”, para hablar sobre las entradas.

Recorte tantos caracteres innecesarios como sea posible (por ejemplo, pierda el .xml si son todos .xml ).


Puede ser útil hacer el trabajo intensivo de CPU / memoria en una máquina separada, dependiendo de qué otro hardware tenga con una conexión de red rápida a su servidor de producción crítico.

Puede ejecutar un progtwig simple en el servidor que envía nombres de archivos a través de una conexión TCP a un progtwig que se ejecuta en otra máquina, donde es seguro usar mucha más memoria. El progtwig en el servidor aún podría hacer pequeños lotes de diccionario, y simplemente almacenarlos en un sistema de archivos remoto.


Y ahora, dado que ninguna de las otras respuestas realmente junta todas las piezas, esta es mi respuesta real:

Un límite superior en el uso de la memoria es fácil. Escriba su progtwig para usar un techo de memoria constante, independientemente del tamaño de entrada. Las entradas más grandes conducirán a más fases de fusión, no a más uso de memoria en ningún momento.

La mejor estimación del espacio de almacenamiento temporal de archivos que puede hacer sin mirar la entrada es un límite superior muy conservador que asume que cada cadena de entrada es única. Necesita una forma de estimar cuántas cadenas de entrada habrá. (La mayoría de los sistemas de archivos saben cuántos archivos separados contienen, sin tener que recorrer el árbol de directorios y contarlos).

Puede hacer algunas suposiciones sobre la distribución de duplicados para adivinar mejor.

Si el número , en lugar del tamaño, de los archivos reutilizables es un problema, puede almacenar varios lotes en el mismo archivo de salida, uno tras otro. Ponga los encabezados de longitud al comienzo de cada uno para permitir saltar por lotes, o escribir desviaciones de bytes en una secuencia de datos separada. Si el tamaño también es importante, consulte mi párrafo sobre cómo usar la compresión de prefijo común estilo frcode.


Como señala Ian Mercer en su respuesta, ordenar los lotes hará que fusionarlos sea mucho más eficiente. Si no lo hace, puede arriesgarse a golpear una pared donde su algoritmo no puede avanzar, o necesita hacer algo como cargar un lote, escanear otro lote para las entradas que están en el primero, y reescribir el segundo lote con solo se eliminan las posibles entradas coincidentes.

Si no clasificas tus lotes, la complejidad temporal de la primera pasada O (N), pero o tienes que ordenar en algún momento más tarde, o tus últimas etapas tienen un peor desenlace que eso es dramáticamente peor. Desea que su salida esté ordenada globalmente, por lo que, aparte de los enfoques de RadixSort, no se puede evitar una O (N log N) en alguna parte.

Con un tamaño de lote limitado, se esperan los pasos de fusión O (log N), por lo que su análisis original omitió la complejidad O (N log N) de su enfoque al ignorar lo que debe suceder después de escribir los lotes de fase1.


Las elecciones de diseño apropiadas cambian mucho dependiendo de si nuestro techo de memoria es lo suficientemente grande como para encontrar muchos duplicados dentro de un lote. Si incluso una estructura de datos compacta compleja como Trie no ayuda mucho, poner los datos en un Trie y sacarlos de nuevo para escribir un lote es una pérdida de tiempo de CPU.

Si no puede hacer mucha eliminación de duplicados dentro de cada lote de todos modos, entonces necesita optimizar para juntar las posibles combinaciones de teclas para la próxima etapa. Su primera etapa podría agrupar cadenas de entrada por primer byte, en hasta 252 o más archivos de salida (no todos los 256 valores son caracteres de nombre de archivo legales), o en 27 archivos de salida (alfabeto + misc), o 26 + 26 + 1 para mayúsculas / minúsculas + no alfabético. Los archivos temporales pueden omitir el prefijo común de cada cadena.

Entonces la mayoría de estos lotes de primera etapa deberían tener una densidad duplicada mucho más alta. En realidad, esta distribución de entradas de Radix en cubos de salida es útil en cualquier caso, ver más abajo.

Debería ordenar las salidas de la primera etapa en partes, para dar al paso siguiente una ventana de búsqueda de duplicados mucho más amplia para la misma RAM.


Voy a pasar más tiempo en el dominio donde puede encontrar una cantidad útil de duplicados en la transmisión inicial, antes de usar hasta ~ 100MiB de RAM, o lo que elija como límite superior.

Obviamente, agregamos cadenas a algún tipo de diccionario para buscar y contar duplicados sobre la marcha, mientras que solo requiere suficiente almacenamiento para el conjunto de cadenas únicas. Solo almacenar cadenas y luego ordenarlas sería significativamente menos eficiente, porque alcanzaríamos nuestro límite de RAM mucho antes sin la detección de duplicados sobre la marcha.

Para minimizar el trabajo de fase2, phase1 debe encontrar y contar tantos duplicados como sea posible, reduciendo el tamaño total de los datos de p2. También es bueno reducir la cantidad de trabajo de fusión para la fase2. Los lotes más grandes ayudan con ambos factores , por lo que es muy útil acercarse lo más posible a su techo de memoria en la fase 1. En lugar de escribir un lote después de un número constante de cadenas de entrada, hágalo cuando su consumo de memoria se acerque al límite elegido. Los duplicados se cuentan y se descartan, y no requieren almacenamiento adicional.

Una alternativa a la contabilidad de memoria precisa es rastrear las cadenas únicas en su diccionario, lo cual es fácil (y lo realiza la implementación de la biblioteca). Acumular la longitud de las cadenas añadidas también puede proporcionarle una buena estimación de la memoria utilizada para almacenar las cadenas. O simplemente haga una suposición sobre la distribución de la longitud de la cadena. Primero, haga que su tabla hash tenga el tamaño correcto para que no tenga que crecer mientras agrega elementos, por lo que se detiene cuando está 60% lleno (factor de carga) o algo así.


Una estructura de datos con uso eficiente del espacio para el diccionario aumenta nuestra ventana de búsqueda de duplicados para un límite de memoria determinado. Las tablas Hash se vuelven muy ineficientes cuando su factor de carga es demasiado alto, pero la tabla hash solo tiene que guardar punteros en las cadenas. Es el diccionario más familiar y tiene una implementación de biblioteca.

Sabemos que vamos a querer ordenar nuestro lote una vez que hayamos visto suficientes claves únicas, por lo que podría tener sentido utilizar un diccionario que pueda atravesarse en orden ordenado. La ordenación sobre la marcha tiene sentido porque las claves entrarán lentamente , limitadas por IO de disco, ya que estamos leyendo los metadatos del sistema de archivos. Una desventaja es si la mayoría de las claves que vemos son duplicadas, entonces estamos haciendo muchas búsquedas O (log por lotes), en lugar de muchas búsquedas O (1). Y es más probable que una clave sea un duplicado cuando el diccionario es grande, por lo que la mayoría de esas consultas O (log tamaño de lote) tendrán un tamaño de lote cercano al máximo, no distribuido uniformemente entre 0 y máx. Un árbol paga la sobrecarga O (log n) de cada búsqueda, independientemente de si la clave resultó ser única o no. Una tabla hash solo paga el costo de clasificación al final después de eliminar los duplicados. Entonces, para un árbol es O (total_keys * log unique_keys), la tabla hash es O (unique_keys * log unique_keys) para ordenar un lote.

Una tabla hash con factor de carga máximo establecido en 0.75 o algo puede ser bastante denso, pero tener que ordenar los KeyValuePair antes de escribir un lote probablemente KeyValuePair el uso del diccionario estándar. No necesita copias de las cadenas, pero probablemente terminará copiando todos los punteros (refs) para raspar el espacio para una clasificación in situ, y tal vez también cuando los saque de la tabla hash antes de ordenar. (O en lugar de solo punteros, KeyValuePair, para evitar tener que volver atrás y buscar cada cadena en la tabla hash). Si los picos cortos de gran consumo de memoria son tolerables, y no hacen que intercambie / página al disco, podría estar bien. Esto es evitable si puede hacer una ordenación in situ en el búfer utilizado por la tabla hash, pero dudo que eso pueda suceder con contenedores de biblioteca estándar.

Un chorro constante de uso de CPU para mantener el diccionario ordenado en las teclas de velocidad disponibles es probablemente mejor que las ráfagas infrecuentes de uso de CPU para ordenar todas las claves de un lote, además de la explosión de consumo de memoria.

La biblioteca estándar .NET tiene SortedDictionary , que según los documentos se implementa con un árbol binario. No verifiqué si tenía una función de reequilibrio, o usa un árbol rojo-negro, para garantizar el peor rendimiento de O (log n). No estoy seguro de la cantidad de memoria que tendría. Si se trata de una tarea única, recomiendo usar esto para implementarlo rápida y fácilmente. Y también para una primera versión de un diseño más optimizado para uso repetido. Probablemente encontrará que es lo suficientemente bueno, a menos que pueda encontrar una buena implementación de la biblioteca de Tries.


Estructuras de datos para diccionarios ordenados y eficientes en memoria

Cuanto más eficiente es la memoria del diccionario, más dúplex podemos encontrar antes de tener que escribir un lote y eliminar el diccionario. Además, si se trata de un diccionario ordenado, mayores serán nuestros lotes aunque no puedan encontrar duplicados.

Un impacto secundario de la elección de la estructura de datos es la cantidad de tráfico de memoria que generamos mientras se ejecuta en el servidor crítico. Una matriz ordenada (con tiempo de búsqueda O (log n) (búsqueda binaria) y O (n) tiempo de inserción (elementos aleatorios para hacer espacio)) sería compacta. Sin embargo, no solo sería lento, sino que saturaría el ancho de banda de la memoria con memmove la mayor parte del tiempo. El uso del 100% de la CPU al hacerlo tendría un mayor impacto en el rendimiento del servidor que el uso de la CPU al 100% al buscar en un árbol binario. No sabe dónde cargar el siguiente nodo hasta que se carga el nodo actual, por lo que no puede canalizar las solicitudes de memoria. Los errores en la derivación de las comparaciones en la búsqueda de árbol también ayudan a moderar el consumo del ancho de banda de memoria que comparten todos los núcleos. (¡Correcto, algunos progtwigs de uso de CPU 100% son peores que otros!)

Es bueno si vaciar nuestro diccionario no deja la memoria fragmentada cuando la vaciémos. Sin embargo, los nodos de árbol serán de tamaño constante, por lo que un grupo de agujeros dispersos será utilizable para futuras asignaciones de nodos de árbol. Sin embargo, si tenemos diccionarios separados para múltiples cubos radix (ver a continuación), las cadenas de teclas asociadas con otros diccionarios pueden mezclarse con nodos de árbol. Esto podría ocasionar que malloc tenga dificultades para reutilizar toda la memoria liberada, lo que podría boost el uso real de la memoria visible por el sistema operativo por algún pequeño factor. (A menos que la recolección de basura en el tiempo de ejecución de C # realice la compactación, en cuyo caso se trata la fragmentación).

Ya que nunca necesita eliminar nodos hasta que desee vaciar el diccionario y eliminarlos todos, puede almacenar sus nodos Tree en una matriz cultivable. Por lo tanto, la gestión de memoria solo tiene que realizar un seguimiento de una gran asignación, reduciendo la sobrecarga de contabilidad en comparación con malloc de cada nodo por separado. En lugar de punteros reales, los punteros secundarios izquierdo / derecho podrían ser índices de matriz. Esto le permite usar solo 16 o 24 bits para ellos. (Un Heap es otro tipo de árbol binario almacenado en una matriz, pero no se puede utilizar de manera eficiente como un diccionario. Es un árbol, pero no un árbol de búsqueda ).

El almacenamiento de las claves de cadena para un diccionario normalmente se haría con cada cadena como un objeto asignado por separado, con punteros a ellas en una matriz. Como nuevamente, nunca necesita eliminar, crecer o incluso modificar uno hasta que esté listo para eliminarlos todos, puede empaquetarlos cara a cara en una matriz char, con un byte cero de finalización al final de cada uno. De nuevo, esto ahorra una gran cantidad de contabilidad, y también hace que sea fácil hacer un seguimiento de cuánta memoria está en uso para las cadenas de teclas, lo que le permite acercarse de manera segura a la parte superior de la memoria elegida.

Trie / DAWG para un almacenamiento aún más compacto

Para un almacenamiento aún más denso de un conjunto de cadenas, podemos eliminar la redundancia de almacenar todos los caracteres de cada cadena, ya que probablemente haya muchos prefijos comunes.

A Trie almacena las cadenas en la estructura de árbol, lo que le proporciona compresión de prefijo común. Se puede atravesar en orden ordenado, por lo que se ordena sobre la marcha. Cada nodo tiene tantos hijos como diferentes caracteres siguientes en el conjunto, por lo que no es un árbol binario. AC # La implementación parcial (eliminación no escrita) se puede encontrar en esta respuesta SO , a una pregunta similar a esta pero que no requiere lotes / clasificación externa.

Los nodos necesitan almacenar potencialmente muchos punteros secundarios, por lo que cada nodo puede ser grande. O cada nodo podría ser de tamaño variable, sosteniendo la lista de pares nextchar: ref dentro del nodo, si C # lo hace posible. O como dice el artículo de Wikipedia, un nodo puede ser realmente un árbol de búsqueda binaria o de lista enlazada, para evitar perder espacio en nodos con pocos hijos. (Los niveles inferiores de un árbol tendrán mucho de eso.) Los marcadores / nodos de final de palabra son necesarios para distinguir entre subcadenas que no son entradas de diccionario separadas, y las que sí lo son. Nuestro campo de conteo puede servir para ese propósito. Count = 0 significa que la subcadena que termina aquí no está en el diccionario. contar> = 0 significa que es.

Un Trie más compacto es el Árbol Radix, o Árbol PATRICIA , que almacena múltiples caracteres por nodo.

Otra extensión de esta idea es el autómata de estado finito acíclico determinista (DAFSA) , a veces llamado un gráfico de palabras acíclica dirigido (DAWG), pero tenga en cuenta que el artículo de la wikipedia DAWG es sobre una cosa diferente con el mismo nombre. No estoy seguro de que un DAWG pueda atravesarse en orden para obtener todas las claves al final, y como señala wikipedia, el almacenamiento de datos asociados (como un conteo duplicado) requiere una modificación. Tampoco estoy seguro de que se puedan construir de forma incremental, pero creo que puede hacer búsquedas sin compactarse. Las entradas recién agregadas se almacenarán como un Trie, hasta que un paso de compactación cada 128 nuevas claves las fusione en el DAWG. (O ejecute la compactación con menos frecuencia para los DAWG más grandes, por lo que no lo está haciendo demasiado, como duplicar el tamaño de una tabla hash cuando tiene que crecer, en lugar de crecer linealmente, para amortizar la costosa operación).

Puede hacer que un DAWG sea más compacto al almacenar múltiples caracteres en un solo nodo cuando no hay ninguna bifurcación / convergencia. Esta página también menciona un enfoque de encoding Huffman para compactos DAWG, y tiene algunos otros enlaces y citas de artículos.

La implementación DAWG de JohnPaul Adamovsky (en C) se ve bien y describe algunas optimizaciones que utiliza. No he examinado atentamente para ver si puede asignar cadenas a los recuentos. Está optimizado para almacenar todos los nodos en una matriz.

Esta respuesta a las palabras de recuento doble en 1TB de texto sugiere DAWGs, y tiene un par de enlaces, pero no estoy seguro de lo útil que es.


Escritura de lotes: Radix en el primer personaje

Puede activar su RadixSort, y mantener diccionarios separados para cada carácter inicial (o para az, no alfabético que ordena antes de, no alfabético, que ordena después de z). Cada diccionario escribe en un archivo temporal diferente. Si tiene varios nodos de cálculo disponibles para un enfoque de MapReduce, esta sería la forma de distribuir trabajo de fusión a los nodos de cálculo.

Esto permite una modificación interesante: en lugar de escribir todos los cubos de radix a la vez, solo escriba el diccionario más grande como un lote . Esto evita que pequeños lotes entren en algunos cubos cada vez que usted. Esto reducirá el ancho de la fusión dentro de cada cubo, acelerando la fase2.

Con un árbol binario, esto reduce la profundidad de cada árbol en aproximadamente log2 (num_buckets), acelerando las búsquedas. Con un Trie, esto es redundante ( cada nodo usa el siguiente carácter como raíz para ordenar los árboles secundarios). Con un DAWG, esto realmente perjudica la eficiencia de espacio porque se pierde al encontrar la redundancia entre cadenas con diferentes inicios pero partes compartidas posteriormente.

Esto tiene el potencial de comportarse mal si hay unos pocos segmentos poco conocidos que siguen creciendo, pero que generalmente no terminan siendo los más grandes. Podrían consumir una gran parte de la memoria total, lo que generaría lotes pequeños de los depósitos comúnmente utilizados. Podría implementar un algoritmo de desalojo más inteligente que registre cuando un cubo (diccionario) se vació por última vez. El puntaje de NeedsEmptying para un cubo sería algo así como un producto de tamaño y edad. O tal vez alguna función de la edad, como sqrt (edad). También sería útil una forma de registrar cuántos duplicados ha encontrado cada contenedor desde la última vez que se vació. Si se encuentra en un punto en su flujo de entrada donde hay muchas repeticiones para uno de los intervalos, lo último que desea hacer es vaciarlo con frecuencia. Quizás cada vez que encuentre un duplicado en un cubo, incremente un contador. Mire la proporción de edad contra dups-found. Los cubos de bajo uso que se encuentran allí y que retiran la RAM de otros cubos serán fáciles de encontrar de esa manera, cuando su tamaño comienza a boost. Se pueden mantener los cubos realmente valiosos incluso cuando son los más grandes, si encuentran muchos duplicados.

Si sus estructuras de datos para rastrear la edad y los dúplex encontrados son una estructura de matrices, la (last_emptied[bucket] - current_pos) / (float)dups_found[bucket] se puede hacer de manera eficiente con el punto flotante vectorial. Una división entera es más lenta que una división FP. Una división de FP tiene la misma velocidad que las divisiones de 4 FP, y los comstackdores pueden auto-vectorizar si les facilitas la tarea de esta manera.

Hay mucho trabajo por hacer entre llenar los cubos, por lo que la división sería un pequeño inconveniente a menos que uses muchos cubos.

elegir cómo hacer un cubo

Con un buen algoritmo de desalojo, una opción ideal de agrupamiento colocará llaves que rara vez tienen duplicados juntas en algunas cubetas, y cubos que tienen muchos duplicados juntos en otras cubetas. Si conoce algún patrón en sus datos, esta sería una forma de explotarlo. Tener algunas cubetas que son en su mayoría de bajo-dup significa que todas esas claves únicas no eliminan las claves valiosas en un lote de salida. Un algoritmo de desalojo que analiza qué tan valiosa ha sido una cubeta en términos de dúplex encontrados por clave única determinará automáticamente qué cubetas son valiosas y vale la pena conservar, aunque su tamaño se está incrementando.

Hay muchas maneras de rastrear sus cadenas en cubos. Algunos se asegurarán de que cada elemento en un cubo se compare con menos de cada elemento en cada cubo posterior, por lo que producir resultados totalmente ordenados es fácil. Algunos no lo harán, pero tienen otras ventajas. Habrá compensaciones entre las opciones de clasificación, todas las cuales dependen de los datos:

  • bueno para encontrar muchos duplicados en el primer pase (por ejemplo, separando los patrones de alto-dup de los patrones de bajo-dup)
  • distribuye el número de lotes de manera uniforme entre las cubetas (por lo que ningún cubo tiene una gran cantidad de lotes que requieren una fusión de múltiples etapas en la fase 2), y tal vez otros factores.
  • produce un mal comportamiento cuando se combina con su algoritmo de desalojo en su conjunto de datos.
  • cantidad de fusión entre cubetas necesaria para producir salida clasificada globalmente. La importancia de esta escala con el número total de cadenas exclusivas, no el número de cadenas de entrada.

Estoy seguro de que las personas inteligentes han pensado en las buenas formas de hacer frente a las cadenas antes que yo, por lo que probablemente valga la pena investigar si el enfoque obvio de primero-personaje no es ideal. Este caso de uso especial (de clasificación al eliminar / contar duplicados) no es típico. Creo que la mayoría de los trabajos sobre clasificación solo consideran los géneros que conservan los duplicados. Por lo tanto, es posible que no encuentre mucho que le ayude a elegir un buen algoritmo de ordenamiento para una clasificación externa de recuento doble. En cualquier caso, dependerá de los datos.

Algunas opciones concretas para el agrupamiento son: Radix = los primeros dos bytes juntos (aún combinando mayúsculas / minúsculas, y combinando caracteres no alfabéticos). O Radix = el primer byte del código hash. (Requiere una combinación global para producir salida clasificada.) O Radix = (str[0]>>2) << 6 + str[1]>>2 . es decir, ignorar los 2 bits bajos de los primeros 2 caracteres, poner [abcd][abcd].* juntos, [abcd][efgh].* juntos, etc. Esto también requeriría cierta fusión de los resultados ordenados entre algunos conjuntos de cubos. por ejemplo, daxxx estaría en el primer cubo, pero aexxx estaría en el segundo. Pero solo los cubos con los mismos bits altos de primer char deben fusionarse para producir el resultado final ordenado.

Una idea para manejar una opción de agrupamiento que ofrece un gran hallazgo de duplicación pero necesita una clasificación por fusión entre cubos: al escribir la salida de fase2, bucket con el primer carácter como base para producir el orden de clasificación que desee. Cada depósito de fase 1 dispersa la salida en segmentos de fase2 como parte del género global. Una vez que se hayan procesado todos los lotes de fase 1 que pueden incluir cadenas que comienzan con a , realice la fusión de a cubo de fase2 en el resultado final y elimine esos archivos temporales.

Radix = los primeros 2 bytes (combinando no alfabético) representarían 28 2 = 784 segmentos. Con 200MiB de RAM, ese es el tamaño promedio del archivo de salida de solo ~ 256k. Vaciar solo un cubo a la vez haría que ese sea el mínimo, y normalmente obtendría lotes más grandes, por lo que podría funcionar. (Su algoritmo de desalojo podría golpear un caso patológico que lo hizo mantener una gran cantidad de cubos grandes, y escribir una serie de pequeños lotes para cubos nuevos. Hay peligros para la heurística inteligente si no se prueba cuidadosamente).

Múltiples lotes empaquetados en el mismo archivo de salida es probablemente más útil con muchos cubos pequeños. Tendrás, por ejemplo, 784 archivos de salida, cada uno con una serie de lotes. Esperemos que su sistema de archivos tenga suficiente espacio libre contiguo y sea lo suficientemente inteligente como para hacer un buen trabajo al no fragmentarse demasiado al dispersar escrituras pequeñas en muchos archivos.


Fusionar

En las etapas de fusión, con lotes clasificados no necesitamos un diccionario. Simplemente tome la siguiente línea del lote que tenga el valor más bajo, combinando duplicados a medida que los encuentre.

MergeSort generalmente combina pares, pero cuando se hace una clasificación externa (es decir, disco -> disco) , es común una entrada mucho más amplia para evitar leer y volver a escribir la salida muchas veces. Tener 25 archivos de entrada abiertos para fusionarse en un archivo de salida debería estar bien. Use la implementación de la biblioteca de PriorityQueue (típicamente implementada como un Heap) para elegir el siguiente elemento de entrada de muchas listas ordenadas. Tal vez agregue líneas de entrada con la cadena como prioridad, y el recuento y número de archivo de entrada como carga útil.

Si usó radix distribute-by-first-character en la primera pasada, entonces combine todos los lotes a en el archivo de salida final (incluso si este proceso toma múltiples etapas de fusión), luego todos los lotes b , etc. Usted no Necesito verificar cualquiera de los lotes desde el inicio-con- a cubo contra lotes de cualquier otro cubo , por lo que ahorra una gran cantidad de trabajo de fusión, especialmente. si tus llaves están bien distribuidas por el primer personaje.


Minimizando el impacto en el servidor de producción:

Acelere la E / S del disco durante la fusión, para evitar poner de rodillas al servidor si la captación previa del disco genera una enorme profundidad de lectura de la cola de E / S. Limitar su E / S, en lugar de una fusión más estrecha, es probablemente una mejor opción. Si el servidor está ocupado con su trabajo normal, es probable. no hará muchas lecturas secuenciales grandes, incluso si solo está leyendo un par de archivos.

Compruebe la carga del sistema de vez en cuando mientras se ejecuta. Si es alto, duerma durante 1 segundo antes de hacer más trabajo y verificar nuevamente. Si es realmente alto, no haga más trabajo hasta que el promedio de carga disminuya (durmiendo 30 segundos entre revisiones).

También compruebe el uso de la memoria del sistema y reduzca el umbral de lote si la memoria es escasa en el servidor de producción. (O si realmente apretado, enjuague su lote parcial y duerma hasta que la presión de memoria se reduzca).

Si el tamaño del archivo temporal es un problema, puede hacer la compresión de prefijo común como frcode de updatedb / locate para reducir significativamente el tamaño del archivo para listas ordenadas de cadenas. Probablemente use la clasificación sensible a mayúsculas y minúsculas dentro de un lote, pero no se distingue entre mayúsculas y minúsculas. Entonces cada lote en el cubo tendrá todas las A s, luego todas las a s. O incluso LZ4 los comprime / descomprime sobre la marcha. Usa hexadecimal para los recuentos, no decimal. Es más corto y más rápido de codificar / decodificar.

Use un separador que no sea un caracter de nombre de archivo legal, como / , entre la clave y el recuento. El análisis de cadenas bien podría tomar mucho tiempo de CPU en la etapa de fusión, por lo que vale la pena considerarlo. Si puede dejar las cadenas en los búferes de entrada por archivo, y simplemente apuntar su PQueue hacia ellos, eso podría ser bueno. (Y le dirá de qué archivo de entrada proviene una cadena, sin almacenarla por separado).


la optimización del rendimiento:

Si las cadenas no ordenadas iniciales estaban disponibles extremadamente rápido, una tabla hash con lotes pequeños que se ajustan al diccionario en la memoria caché de la CPU L3 podría ser una ganancia, a menos que una ventana más grande pueda incluir una fracción mucho mayor de claves y encuentre más dups. Depende de cuántas repeticiones son típicas en, digamos, 100k archivos. Cree lotes ordenados pequeños en la memoria RAM mientras lee, luego combínelos en un lote de discos. Esto puede ser más eficiente que hacer una gran oferta en la memoria, ya que no tiene acceso aleatorio a la entrada hasta que la haya leído inicialmente.

Dado que I / O probablemente será el límite, los lotes grandes que no encajan en la memoria caché de datos de la CPU son probablemente una ganancia, para encontrar más duplicados y (¿en gran medida?) Reducir la cantidad de trabajo de fusión que se debe realizar.

Puede ser conveniente verificar el tamaño de la tabla hash / consumo de memoria después de cada porción de nombres de archivo que se obtiene del sistema operativo, o después de cada subdirectorio o lo que sea. As long as you choose a conservative size bound, and you make sure you can’t go for too long without checking, you don’t need to go nuts checking every iteration.


This paper from 1983 examines external merge-sorting eliminating duplicates as they’re encountered, and also suggests duplicate elimination with a hash function and a bitmap. With long input strings, storing MD5 or SHA1 hashes for duplicate-elimination saves a lot of space.

I’m not sure what they had in mind with their bitmap idea. Being collision-resistant enough to be usable without going back to check the original string would require a hash code of too many bits to index a reasonable-size bitmap. (eg MD5 is a 128bit hash).

How do you “merge the group files” in your approach? In worst case every line had a different name template so each group file had 5,000 lines in it and each merge doubles the number of lines until you overflow memory.

Your friend is closer to the answer, those intermediate files need to be sorted so you can read them line by line and merge them to create new files without having to hold them all in memory. This is a well-known problem, it’s an external sort . Once sorted you can count the results.

A jolly good problem.

Considering that you intend to process the results in batches of 5000 , I don’t believe memory optimisations will be of particular importance so we could probably ignore that aspect like a bad Adam Sandler film and move onto the more exciting stuff. Besides, just because some computation uses more RAM does not necessarily imply it’s a bad algorithm. No one ever complained about look-up tables.

However, I do agree computationally the dictionary approach is better because it’s faster . With respect to the alternative, why perform an unnecessary sort even if its quick? The latter, with its “O(m log m)” is ultimately slower than “O(m)”.

The Real Problem?

With RAM out of the equation, the problem is essentially that of computation . Any “performance problem” in the algorithm will arguably be insignificant to the time it takes to traverse the file system in the first place .

That’s arguably where the real challenge will be. A problem for another time perhaps?

EDIT : displayName makes a good point about using Hadoop – quite ideal for concurrent jobs and compute

¡Buena suerte!

Your problem is a very good candidate for Map-Reduce . Great news: You don’t need to move from C# to Java (Hadoop) as Map-Reduce is possible in .NET framework!

Through LINQs you have the basic elements of execution in place already for performing Map Reduce in C#. This might be one advantage over going for External Sort though there is no question about the observation behind External Sort. This link has the ‘Hello World!’ of Map-Reduce already implemented in C# using LINQs and should get you started.


If you do move to Java, one of the most comprehensive tutorial about it is here . Google about Hadoop and Map-Reduce and you will get plenty of information and numerous good online video tutorials.

Further, if you wish to move to Java, your requirements of:

  • Sorted results
  • critical RAM usage

will surely be met as they are inbuilt fulfillments you get from a Map-Reduce job in Hadoop.