c# algorithm sorting dictionary large-data

c# - Clasificación externa de cadenas con restricción de memoria, con duplicados combinados y contados, en un servidor crítico(miles de millones de nombres de archivo)



algorithm sorting (4)

¿Cómo "fusiona los archivos de grupo" en su enfoque? En el peor de los casos, cada línea tenía una plantilla de nombre diferente, por lo que cada archivo de grupo tenía 5.000 líneas y cada combinación duplicaba el número de líneas hasta que se desbordaba la memoria.

Su amigo está más cerca de la respuesta, esos archivos intermedios deben ordenarse para que pueda leerlos línea por línea y combinarlos para crear nuevos archivos sin tener que guardarlos en la memoria. Este es un problema bien conocido, es un tipo externo . Una vez ordenado, puede contar los resultados.

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 la 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 debería ser

sign.xml,2 hero.xml,1

Se desconoce el tipo total de plantillas de nombre posibles, posiblemente exceda int.MaxValue .

Se desconoce el número total de archivos en el servidor, posiblemente exceda int.MaxValue .

Requisitos :

El resultado final se debe ordenar por plantilla de nombre.

El servidor en el que se ejecutará la herramienta es súper crítico. Deberíamos poder decir 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 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 montón de archivos grupales.

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 los sucesos.

Sugiero usar el diccionario. La plantilla de nombre de archivo es clave. Sea m el tamaño de la partición. (En este ejemplo es 5000). Entonces, 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 pasada ya que las plantillas de mismo nombre están todas juntas ahora. complejidad temporal O (m log m), complejidad espacial O (m).

No podemos persuadirnos mutuamente. ¿Ustedes ven algún problema de los dos métodos?

Su problema es un muy buen candidato para Map-Reduce . Buenas noticias: no es necesario pasar de C # a Java (Hadoop), ya que Map-Reduce es posible en .NET framework.

A través de LINQ, ya tiene los elementos básicos de ejecución para realizar Map Reduce en C #. Esta podría ser una ventaja sobre optar por la clasificación externa, aunque no hay dudas sobre la observación detrás de la clasificación externa. Este enlace tiene el ''Hola Mundo!'' de Map-Reduce ya implementado en C # usando LINQs y debería ayudarlo a comenzar.

Si se muda a Java, uno de los tutoriales más completos al respecto está here . Google sobre Hadoop y Map-Reduce y obtendrá mucha información y numerosos buenos videos tutoriales en línea.

Además, si desea pasar a Java, sus requisitos de:

  • Resultados ordenados
  • uso crítico de RAM

seguramente se cumplirán, ya que son cumplimientos incorporados que obtienes de un trabajo de Map-Reduce en Hadoop.

Un muy buen problema.

Teniendo en cuenta que tiene la intención de procesar los resultados en lotes de 5000 , no creo que las optimizaciones de memoria sean de particular importancia, por lo que probablemente podríamos ignorar ese aspecto como una mala película de Adam Sandler y pasar a cosas más emocionantes. Además, el hecho de que algunos cálculos usen más RAM no implica necesariamente que sea un algoritmo malo. Nadie se quejó de las tablas de consulta.

Sin embargo, estoy de acuerdo computacionalmente que el enfoque del diccionario es mejor porque es más rápido . Con respecto a la alternativa, ¿por qué realizar una clasificación innecesaria incluso si es rápida? El último, con su "O (m log m)" es en última instancia más lento que "O (m)".

¿El verdadero problema?

Con RAM fuera de la ecuación, el problema es esencialmente el de la computación . Podría decirse que cualquier "problema de rendimiento" en el algoritmo será insignificante para el tiempo que lleva atravesar el sistema de archivos en primer lugar .

Ahí es donde podría estar el verdadero desafío. ¿Un problema para otro momento quizás?

EDITAR : displayName hace un buen punto sobre el uso de Hadoop, bastante ideal para trabajos concurrentes y computación

¡Buena suerte!

IDK si se ha estudiado la ordenación externa con la combinación de conteo de duplicados. Encontré un artículo de 1983 (ver más abajo). Por lo general, los algoritmos de ordenación se diseñan y estudian con el supuesto de ordenar 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 considera una aplicación de diccionarios compactos combinados con una clasificación de fusión externa.

Los 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 doble).

TL: resumen de DR de ideas útiles, ya que divagué con 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 hubo muchos duplicados en un grupo de 5000 cadenas, todavía no usará mucha memoria. Puede encontrar muchos más duplicados en el primer paso de esta manera.

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

  • Para evitar una explosión de uso de memoria al ordenar las claves en una tabla hash, use un diccionario que pueda hacer un recorrido en orden de las claves. (es decir, ordenar sobre la marcha). Hay SortedDictionary<TKey, TValue> (basado en árbol binario). Esto también intercala el uso de la CPU de ordenar con la E / S esperando obtener las cadenas de entrada.

  • Clasifique por radix cada lote en salidas por primer carácter (az, no alfabético que se ordena antes de A y no alfabético que se ordena después de z ). O alguna otra opción de distribución que distribuya bien sus llaves. Use diccionarios separados para cada cubo de radix y vacíe solo el más grande en un lote cuando alcance el límite de su memoria. (La heurística de desalojo más elegante que la "mayor" puede valer la pena).

  • acelere la E / S (especialmente al fusionar) y verifique 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 codificación de prefijo común, o tal vez lz4.

  • Un diccionario de espacio eficiente 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 de memoria superior. Un Trie (o mejor, Radix Trie ) podría ser ideal, porque almacena los caracteres dentro de los nodos del árbol, con prefijos comunes solo almacenados una vez. Los gráficos de palabras acíclicas dirigidas son aún más compactos (encuentran redundancia entre subcadenas comunes que no son prefijos). Usar uno como Diccionario es complicado pero probablemente posible (ver más abajo).

  • Aproveche el hecho de que no necesita eliminar ningún nodo o cadena de árbol hasta que vacie todo el diccionario. Utilice una matriz de nodos que se pueda cultivar y otra matriz de caracteres que se pueda crecer y que agrupe las cadenas cabeza a cola. (Útil para un Radix Trie (nodos multi-char), pero no un Trie normal donde cada nodo es un único char).

  • Dependiendo de cómo se distribuyan los duplicados, es posible que pueda o no encontrar muchos en el primer paso. 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 directorio, que puede suministrar eficientemente su código con una secuencia de cadenas para que no se clasifiquen y se cuenten. Así que solo diré "cadenas" o "teclas", 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 programa simple en el servidor que envía nombres de archivo a través de una conexión TCP a un programa que se ejecuta en otra máquina, donde es seguro usar mucha más memoria. El programa 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 reunió todas las piezas, aquí está mi respuesta real:

Un límite superior en el uso de la memoria es fácil. Escriba su programa para usar un límite de memoria constante, independientemente del tamaño de entrada. Las entradas más grandes conducirán a más fases de fusión, no 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 alguna 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 hacer una mejor suposición.

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 encabezados de longitud al comienzo de cada uno para permitir saltar por lotes, o escriba compensaciones de bytes en una secuencia de datos separada. Si el tamaño también es importante, vea mi párrafo sobre el uso de la compresión de prefijo común de estilo frcode.

Como Ian Mercer señala en su respuesta, ordenar sus lotes hará que fusionarlos sea mucho más eficiente. Si no lo hace, corre el riesgo de chocar contra un muro 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 las entradas coincidentes potencialmente pocas eliminadas.

No ordenar los lotes hace que la complejidad del tiempo del primer pase O (N) sea complicada, pero hay que ordenar en algún momento más tarde o las etapas posteriores tienen un límite en el peor de los casos que es dramáticamente peor. Desea que su salida se ordene globalmente, por lo que, aparte de los enfoques RadixSort, no se puede evitar una O (N log N) en alguna parte.

Con un tamaño de lote limitado, se esperan 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 que se escriben los lotes de la fase 1.

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

Si de todos modos no puede hacer mucha eliminación de duplicados dentro de cada lote, entonces necesita optimizar para juntar claves posiblemente coincidentes para la siguiente etapa. Su primera etapa podría agrupar cadenas de entrada por primer byte, en hasta 252 archivos de salida (no todos los 256 valores son caracteres legales de nombre de archivo), o en 27 o más archivos de salida (alfabeto + misceláneo), 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 la primera etapa deben tener una densidad duplicada mucho más alta. En realidad, esta distribución Radix de entradas en cubos de salida es útil en cualquier caso, ver más abajo.

Aún así, debe ordenar sus salidas de la primera etapa en fragmentos, para dar al siguiente paso una ventana mucho más amplia de doble búsqueda para la misma RAM.

Voy a pasar más tiempo en el dominio donde puede encontrar una cantidad útil de duplicados en la secuencia 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 se 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 detección de duplicados sobre la marcha.

Para minimizar el trabajo de la fase 2, la fase 1 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 fase 2. Los lotes más grandes ayudan con ambos factores , por lo que es muy útil acercarse lo más posible a su límite 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 el consumo de memoria se acerque al límite elegido. Los duplicados se cuentan y se tiran, 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 hace por la implementación de la biblioteca). Acumular la longitud de las cadenas agregadas también puede brindarle una buena estimación de la memoria utilizada para almacenar las cadenas. O simplemente haga una suposición sobre la distribución de longitud de cadena. Inicialmente, haga que su tabla hash tenga el tamaño correcto para que no tenga que crecer mientras agrega elementos, para que se detenga cuando esté llena al 60% (factor de carga) o algo así.

Una estructura de datos de espacio eficiente para el diccionario aumenta nuestra ventana de búsqueda doble para un límite de memoria dado. Las tablas hash se vuelven muy ineficientes cuando su factor de carga es demasiado alto, pero la tabla hash solo tiene que almacenar punteros en las cadenas. Es el diccionario más familiar y tiene implementaciones 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 usar un diccionario que se pueda recorrer en orden ordenado. Ordenar sobre la marcha tiene sentido porque las claves entrarán lentamente , limitadas por el disco IO ya que estamos leyendo metadatos del sistema de archivos. Una desventaja es que si la mayoría de las claves que vemos son duplicados, entonces estamos haciendo muchas búsquedas de O (tamaño de lote de registro), en lugar de muchas búsquedas de 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 (tamaño de lote de registro) tendrán un tamaño de lote cercano al máximo, no distribuido uniformemente entre 0 y máximo. Un árbol paga la sobrecarga O (log n) de la clasificación para cada búsqueda, ya sea que la clave sea única o no. Una tabla hash solo paga el costo de clasificación al final después de eliminar 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 un factor de carga máximo establecido en 0.75 o algo puede ser bastante denso, pero tener que ordenar los KeyValuePair s 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 (referencias) para rascar el espacio para una ordenación no en el lugar, 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 regresar y buscar cada cadena en la tabla hash). Si los picos cortos de gran consumo de memoria son tolerables y no hacen que intercambie / pague 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 los contenedores de biblioteca estándar.

Un goteo constante del uso de la CPU para mantener el diccionario ordenado en las teclas de velocidad disponibles es probablemente mejor que las explosiones poco frecuentes del uso de la CPU para ordenar todas las teclas de un lote, además de la explosión del consumo de memoria.

La biblioteca estándar .NET tiene SortedDictionary<TKey, TValue> , que según los documentos se implementa con un árbol binario. No verifiqué si tiene una función de reequilibrio, o si utiliza un árbol rojo-negro, para garantizar el rendimiento de O (log n) en el peor de los casos. No estoy seguro de la cantidad de memoria que tendría. Si esta es una tarea única, entonces recomendaría absolutamente usarla para implementarla 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 Tries en la biblioteca.

Estructuras de datos para diccionarios ordenados eficientes en memoria

Cuanto más eficiente sea la memoria del diccionario, más duplicados podemos encontrar antes de tener que escribir un lote y eliminar el diccionario. Además, si se trata de un diccionario ordenado, más grandes pueden ser nuestros lotes incluso cuando no pueden 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 O (log n) tiempo de búsqueda (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 hacer esto tendría un mayor impacto en el rendimiento del servidor que el uso del 100% de la CPU al buscar un árbol binario. No sabe desde dónde cargar el siguiente nodo hasta que se carga el nodo actual, por lo que no puede canalizar las solicitudes de memoria. Las predicciones erróneas de la rama 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. (Así es, ¡algunos programas de uso de CPU 100% son peores que otros!)

Es bueno si vaciar nuestro diccionario no deja la memoria fragmentada cuando lo vaciamos. Sin embargo, los nodos de árbol tendrán un tamaño constante, por lo que se podrán utilizar un montón de agujeros dispersos para futuras asignaciones de nodos de árbol. Sin embargo, si tenemos diccionarios separados para múltiples cubos de radix (ver más abajo), las cadenas de teclas asociadas con otros diccionarios podrían mezclarse con nodos de árbol. Esto podría hacer que Malloc tenga dificultades para reutilizar toda la memoria liberada, lo que podría aumentar el uso real de la memoria visible del sistema operativo por un pequeño factor. (A menos que la recolección de basura en tiempo de ejecución de C # haga compactación, en cuyo caso se resuelve la fragmentación).

Como nunca necesita eliminar nodos hasta que desee vaciar el diccionario y eliminarlos todos, puede almacenar sus nodos Tree en una matriz ampliable. Por lo tanto, la administración de memoria solo tiene que realizar un seguimiento de una gran asignación, lo que reduce 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 usar eficientemente como 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, una vez más, nunca es necesario eliminar, aumentar o incluso modificar uno hasta que esté listo para eliminarlos todos, puede empaquetarlos cabeza a cola en una matriz de caracteres, con un byte cero al final de cada uno. De nuevo, esto ahorra una gran cantidad de libros y también facilita el seguimiento de la cantidad de memoria que se utiliza para las cadenas de teclas, lo que le permite acercarse con seguridad al límite 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.

Un Trie almacena las cadenas en la estructura de árbol, dándole compresión de prefijo común. Se puede atravesar en orden, 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. La implementación parcial de AC # Trie (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 Trie necesitan almacenar potencialmente muchos punteros secundarios, por lo que cada nodo puede ser grande. O cada nodo podría ser de tamaño variable, manteniendo 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 una lista enlazada o un árbol de búsqueda binario, para evitar perder espacio en nodos con pocos hijos. (Los niveles inferiores de un árbol tendrán mucho de eso). Se necesitan marcadores / nodos de fin de palabra para distinguir entre las 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 lo es.

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

Otra extensión de esta idea es el autómata determinista acíclico de estado finito (DAFSA) , a veces llamado Gráfico de palabras acíclicas dirigido (DAWG), pero tenga en cuenta que el artículo de la wikipedia de DAWG trata sobre algo diferente con el mismo nombre. No estoy seguro de que un DAWG se pueda atravesar en orden para sacar todas las claves al final, y como señala Wikipedia, almacenar datos asociados (como un conteo duplicado) requiere una modificación. Tampoco estoy seguro de que se puedan construir de forma incremental, pero creo que puedes hacer búsquedas sin haberlas compactado. Las entradas recién agregadas se almacenarán como un Trie, hasta que un paso de compactación cada 128 nuevas claves las combine en el DAWG. (O ejecute la compactación con menos frecuencia para 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 operación costosa).

Puede hacer que un DAWG sea más compacto almacenando varios caracteres en un solo nodo cuando no hay ninguna ramificación / convergencia. Esta página también menciona un enfoque de codificación de Huffman para DAWG compactos, 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 mirado cuidadosamente para ver si puede asignar cadenas a recuentos. Está optimizado para almacenar todos los nodos en una matriz.

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

Escribir 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 se ordena antes que a, no alfabético que se ordena después de z). Cada diccionario escribe en un archivo temporal diferente. Si tiene varios nodos de proceso disponibles para un enfoque de MapReduce, esta sería la forma de distribuir el trabajo de fusión a los nodos de proceso.

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 fase 2.

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 utiliza el siguiente carácter como una raíz para ordenar los árboles secundarios). Con un DAWG, esto realmente perjudica su eficiencia de espacio porque pierde al encontrar la redundancia entre cadenas con diferentes inicios, pero luego partes compartidas.

Esto tiene el potencial de comportarse mal si hay algunos cubos tocados con poca frecuencia que siguen creciendo, pero que generalmente no terminan siendo los más grandes. Podrían usar una gran fracción de su memoria total, generando pequeños lotes de los cubos de uso común. Podría implementar un algoritmo de desalojo más inteligente que registre cuándo se vació por última vez un cubo (diccionario). El puntaje de Vaciado de Necesidades 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 (age). También sería útil alguna forma de registrar cuántos duplicados ha encontrado cada depósito desde la última vez que se vació. Si está en un lugar en su flujo de entrada donde hay muchas repeticiones para uno de los depósitos, 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 vs. dups-encontrado. Los cubos de bajo uso sentados allí, quitando la RAM de otros cubos, serán fáciles de encontrar de esa manera, cuando su tamaño comience a aumentar. Los cubos realmente valiosos se pueden mantener incluso cuando son los más grandes actuales, si encuentran muchos duplicados.

Si sus estructuras de datos para rastrear edad y duplicaciones encontradas es una estructura de matrices, la (last_emptied[bucket] - current_pos) / (float)dups_found[bucket] se puede hacer de manera eficiente con el punto flotante de vector. Una división entera es más lenta que una división FP. Una división de FP es la misma velocidad que 4 divisiones de FP, y es de esperar que los compiladores puedan auto-vectorizarse si se les facilita así.

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

elegir cómo baldear

Con un buen algoritmo de desalojo, una opción ideal de agrupamiento colocará claves que rara vez tienen duplicados juntos en algunos cubos, y cubos que tienen muchos duplicados juntos en otros cubos. Si conoce algún patrón en sus datos, esta sería una forma de explotarlo. Tener algunos cubos que son en su mayoría de baja duplicación significa que todas esas claves únicas no eliminan las claves valiosas en un lote de salida. Un algoritmo de desalojo que analiza cuán valioso ha sido un cubo en términos de duplicaciones encontradas por clave única determinará automáticamente qué cubos son valiosos y vale la pena mantener, a pesar de que su tamaño está aumentando.

Hay muchas formas de mezclar sus cadenas en cubos. Algunos se asegurarán de que cada elemento en un depósito se compare menos que cada elemento en cada depósito posterior, por lo que es fácil producir una salida completamente ordenada. Algunos no lo harán, pero tienen otras ventajas. Habrá compensaciones entre las opciones de agrupación, todas las cuales dependen de los datos:

  • bueno para encontrar muchos duplicados en la primera pasada (por ejemplo, separando los patrones high-dup de los patrones low-dup)
  • distribuye el número de lotes de manera uniforme entre los cubos (por lo que ningún cubo tiene una gran cantidad de lotes que requieren una fusión de varias etapas en la fase 2), y quizás otros factores.
  • produce un mal comportamiento cuando se combina con su algoritmo de desalojo en su conjunto de datos.
  • cantidad de fusión entre cubos necesaria para producir una salida clasificada globalmente. La importancia de esto aumenta con el número total de cadenas únicas, no con el número de cadenas de entrada.

Estoy seguro de que las personas inteligentes han pensado en buenas formas de agrupar las cadenas antes que yo, por lo que probablemente valga la pena investigar si el enfoque obvio de por primer personaje no es ideal. Este caso de uso especial (de ordenar al eliminar / contar duplicados) no es típico. Creo que la mayoría del trabajo en la clasificación solo considera los tipos que conservan los duplicados. Por lo tanto, es posible que no encuentre mucho que lo ayude a elegir un buen algoritmo de inversión para un ordenamiento externo de conteo doble. En cualquier caso, dependerá de los datos.

Algunas opciones concretas para el bucketing son: Radix = 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 fusión global para producir una salida ordenada). O Radix = (str[0]>>2) << 6 + str[1]>>2 . es decir, ignore los 2 bits bajos de los primeros 2 caracteres, para poner [abcd][abcd].* juntos, [abcd][efgh].* juntos, etc. Esto también requeriría una fusión de los resultados ordenados entre algunos conjuntos de cubos por ejemplo, daxxx estaría en el primer aexxx , pero aexxx estaría en el segundo. Pero solo los cubos con los mismos bits altos de primer carácter deben fusionarse entre sí para producir la salida final ordenada.

Una idea para manejar una opción de agrupación que proporciona una excelente búsqueda de duplicación pero necesita una clasificación de fusión entre cubetas: al escribir la salida de fase 2, colóquela con el primer carácter como la raíz para producir el orden de clasificación que desee. Cada depósito de fase 1 dispersa la salida en depósitos de fase 2 como parte del ordenamiento global. Una vez que se hayan procesado todos los lotes de fase 1 que pueden incluir cadenas que comienzan con a , combine la fase 2 en el resultado final y elimine esos archivos temporales.

Radix = primeros 2 bytes (combinando no alfabético) generaría 28 2 = 784 cubos. Con 200MiB de RAM, ese es un tamaño de archivo de salida promedio de solo ~ 256k. Vaciar solo un cubo a la vez sería lo mínimo, y generalmente obtendría lotes más grandes, por lo que esto podría funcionar. (Su algoritmo de desalojo podría llegar a un caso patológico que lo obligó a mantener muchos cubos grandes, y escribir una serie de pequeños lotes para nuevos cubos. Existen riesgos para la heurística inteligente si no se prueba con cuidado).

Múltiples lotes empaquetados en el mismo archivo de salida probablemente sea más útil con muchos cubos pequeños. Tendrá, 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 de no fragmentar demasiado cuando dispersa las escrituras pequeñas en muchos archivos.

Fusionando:

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

MergeSort generalmente combina pares, pero cuando se realiza una ordenación externa (es decir, disco -> disco) , una entrada mucho más amplia es común para evitar leer y reescribir la salida muchas veces. Tener 25 archivos de entrada abiertos para fusionarse en un archivo de salida debería estar bien. Utilice la implementación de la biblioteca de PriorityQueue (normalmente implementado como un montón) 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 el número de archivo de entrada como carga útil.

Si utilizó la distribución de radix por primer carácter en la primera pasada, luego combine todos los lotes a en el archivo de salida final (incluso si este proceso toma múltiples etapas de fusión), entonces todos los lotes b , etc. es necesario verificar cualquiera de los lotes desde el comienzo con a depósito contra los lotes de cualquier otro depósito , por lo que esto ahorra mucho trabajo de fusión, especialmente. si sus claves están bien distribuidas por primer carácter.

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 gran profundidad de lecturas en la cola de E / S. Acelerar 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 ocasionalmente mientras se ejecuta. Si es alta, duerma durante 1 segundo antes de hacer un poco más de trabajo y verificar nuevamente. Si es realmente alto, no haga más trabajo hasta que el promedio de carga baje (durmiendo 30 segundos entre cheques).

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

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

Use un separador que no sea un carácter de nombre de archivo legal, como / , entre clave y recuento. El análisis de cadenas podría ocupar mucho tiempo de CPU en la etapa de fusión, por lo que vale la pena considerarlo. Si puede dejar cadenas en buffers de entrada por archivo, y solo apuntar su PQueue hacia ellos, eso podría ser bueno. (Y decirte de qué archivo de entrada proviene una cadena, sin almacenarla por separado).

la optimización del rendimiento:

Si las cadenas iniciales sin clasificar estaban disponibles extremadamente rápido, entonces una tabla hash con pequeños lotes que se ajustan al diccionario en el caché de la CPU L3 podría ser una victoria, a menos que una ventana más grande pueda incluir una fracción mucho mayor de claves y encontrar más duplicados. Depende de cuántas repeticiones son típicas en, digamos, 100k archivos. Cree pequeños lotes ordenados en RAM a medida que lee, luego combínelos en un lote de discos. Esto puede ser más eficiente que hacer una gran selección rápida en 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 caben en el caché de datos de la CPU son probablemente una victoria, 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 obtiene del sistema operativo, o después de cada subdirectorio o lo que sea. Siempre que elija un límite de tamaño conservador y se asegure de que no puede pasar demasiado tiempo sin verificar, no necesita volverse loco al verificar cada iteración.

Este artículo de 1983 examina la clasificación de fusión externa eliminando duplicados a medida que se encuentran, y también sugiere la eliminación de duplicados con una función hash y un mapa de bits. Con cadenas de entrada largas, el almacenamiento de hashes MD5 o SHA1 para la eliminación de duplicados ahorra mucho espacio.

No estoy seguro de lo que tenían en mente con su idea de mapa de bits. Ser lo suficientemente resistente a la colisión como para ser utilizable sin volver a verificar la cadena original requeriría un código hash de demasiados bits para indexar un mapa de bits de tamaño razonable. (por ejemplo, MD5 es un hash de 128 bits).