sublime - Manera eficiente de memoria para eliminar líneas duplicadas en un archivo de texto usando C++
eliminar lineas repetidas notepad++ (5)
¿Cuál es la forma más eficiente de eliminar las líneas duplicadas en un archivo de texto grande usando C ++?
Déjenme aclarar, no estoy pidiendo código, solo el mejor método. No se garantiza que las líneas duplicadas sean adyacentes. Me doy cuenta de que un enfoque optimizado para un uso mínimo de la memoria daría como resultado velocidades más lentas, pero esta es mi restricción ya que los archivos son demasiado grandes.
Para minimizar el uso de la memoria:
Si tiene una E / S de disco ilimitada (o muy rápida), puede escribir cada línea en su propio archivo con el nombre de archivo como el hash + algún identificador que indique el orden (o no orden, si el orden es irrelevante). De esta manera, utiliza el sistema de archivos como memoria extendida. Esto debería ser mucho más rápido que volver a escanear el archivo completo para cada línea.
Como una adición de lo que han dicho a continuación, si espera una alta tasa de duplicados, puede mantener un cierto umbral de hash en la memoria y en el archivo. Esto daría resultados mucho mejores para altas tasas duplicadas. Como el archivo es tan grande, dudo que n^2 sea aceptable en el tiempo de procesamiento. Mi solución es O(n) en la velocidad de procesamiento y O(1) en la memoria. Sin embargo, es O(n) en el espacio de disco requerido durante el tiempo de ejecución, que otras soluciones no tienen.
Parece que podría estar ejecutando hardware limitado de varias especificaciones, por lo que querrá probar una cantidad de algoritmos y perfiles de eliminación duplicados antes de decidir cuál es el mejor para la implementación a largo plazo.
¿Por qué no simplemente consultar a Knuth, ordenar y buscar? Eso te dará una gran formación para tomar una decisión equilibrada.
Haría hash cada línea y luego volveré a las líneas que tienen hashes no únicos y los compararé individualmente (o de forma amortiguada). esto funcionaría bien en archivos con una incidencia relativamente baja de duplicados.
Cuando utiliza un hash, puede configurar la memoria utilizada en una cantidad constante (es decir, podría tener una pequeña tabla hash con solo 256 ranuras o algo más grande. En cualquier caso, la cantidad de mem puede restringirse a cualquier cantidad constante. ) los valores en la tabla son el desplazamiento de las líneas con ese hash. por lo que solo necesita line_count * sizeof (int) más una constante para mantener la tabla hash.
incluso más simple (pero mucho más lento) sería escanear el archivo completo para cada línea. pero prefiero la primera opción. esta es la opción más eficiente de memoria posible. solo necesitaría almacenar 2 desplazamientos y 2 bytes para hacer la comparación.
Puede usar una ordenación eficiente de E / S (como el comando de ordenamiento unix) y luego leer el archivo en línea por línea comparando cada línea con la lectura previa. Si los dos son iguales, no genere ningún resultado si no salen de la línea.
De esta forma, la cantidad de memoria utilizada por el algoritmo es constante.
Solución simple de fuerza bruta (muy poco consumo de memoria): Haga un n ^ 2 para pasar el archivo y eliminar las líneas duplicadas. Velocidad: O (n ^ 2), Memoria: constante
Rápido (pero pobre, consumo de memoria): la solución de Stefan Kendall: hash cada línea, almacenarlas en un mapa de algún tipo y eliminar una línea que ya existe. Velocidad: O (n), memoria: O (n)
Si está dispuesto a sacrificar orden de archivos (supongo que no, pero lo agregaré): puede ordenar las líneas, luego pasar eliminando duplicados. velocidad: O (n * log (n)), Memoria: constante
editar: si no le gusta la idea de ordenar el contenido del archivo o tratar de mantener hashes únicos pero puede manejar el uso de memoria O (n): Puede identificar cada línea con su marcador de posición de 32 o 64 bits (dependiendo del tamaño del archivo) y clasifique las posiciones de los archivos en lugar del contenido del archivo.
edición n. ° 2: advertencia: las líneas de clasificación en memoria de diferentes longitudes son más difíciles que hacerlo para decir, una matriz de enteros ... en realidad, pensando en cómo la memoria tendría que cambiar y moverse en un paso de fusión, estoy segundo adivinar mi capacidad para ordenar un archivo como ese en n * log (n)