Tengo un archivo de texto grande (1.5 G),
Quiero saber cuál es la herramienta más rápida y confiable en Linux.
Usualmente uso:
awk '!x[$0]++' file.txt
Pero cuando uso el htop
comando veo que mi uso de memoria está aumentando.
Quiero saber cuál es el más rápido y confiable para archivos de gran tamaño.
uniq?
sort?
sed?
awk?
¿Por qué?
time
?Respuestas:
Consideremos cómo funciona cada solución.
uniq
Esto requiere que el archivo ya esté ordenado. De lo contrario,sort
primero debe canalizarlo , lo que significa quesort
debe leer todo el archivo en la memoria, reordenarlo (O(n log n)
) y luego escribirlo en la tubería. El trabajo deuniq
es muy barato, ya que solo tiene que comparar líneas adyacentes de su entrada.sort -u
Esto combina el trabajo desort | uniq
. Esto tiene que recopilar todas las entradas únicas en la memoria como lo hace elawk
script, pero también desperdicia tiempo clasificándolas antes de producir la salida. Esto esO(n log n)
, aunque en este cason
es el número de elementos únicos, no todas las entradas. Entonces es mejor que la tubería.sed
No estoy seguro de por qué enumeró esto, ya que no puedo pensar en una buena manera de hacerlosed
. Tal vez si primero lo ordena y canaliza a unsed
script, hay una manera de comparar líneas adyacentes. Entoncessed
, solo estaría haciendo lo queuniq
hace, yuniq
probablemente lo haga de la manera más eficiente posible.awk
Este es probablemente el mejor porque solo realiza la mínima cantidad de trabajo necesario. A medida que lee cada línea, realiza una búsqueda eficiente de hash para ver si la línea ya está en su memoria, y solo almacena las líneas únicas como claves hash y un contador como valor. (Si la línea no estaba presente anteriormente, la condición será verdadera, por lo que la línea se imprimirá. De lo contrario, no lo hará). Esto usaO(n)
tiempo yO(uniq n)
memoria.Cada método utilizará una cantidad considerable de memoria, ya sea para ordenar la entrada o para hacer un seguimiento de las entradas que han visto para que puedan eliminar duplicados.
fuente
awk
también explica por qué usa cantidades crecientes de memoria. Cualquier cosa que haga un tipo terminará haciendo esto también, solo 1) probablemente lo usará todo de una vez, 2) puede usar un poco más, dependiendo del número de claves únicas frente a duplicadas.sort
recurre a archivos temporales (de manera inteligente) para evitar llenar la memoria. Su uso de memoria está obligado. El límite es personalizable con algunas implementaciones de tipo. Es más eficiente que permitir que el sistema intercambie memoria aleatoriamente en el disco (lo que también afecta también a las aplicaciones en el sistema).awk
queda sin memoria,sort
puede ser la única solución porque ha sido diseñado para lidiar con esto. Por otro lado, toda esa lectura y escritura del disco lo ralentizará, por lo que probablemente tomará mucho tiempo completarlo. Si se trata de cantidades tan grandes de datos, probablemente debería usar un DBMS en lugar de archivos de texto.O(n log n)
? ¿O simplemente lo sabes desde otro lado?He encontrado que ese tipo parece ser la herramienta uniq más rápida como se muestra aquí -> ¿ La forma más rápida de eliminar duplicados en una gran lista de palabras?
fuente
Solo quería señalar que el ñu
uniq
parece terriblemente lento, incluso en una lista ordenada.Acabo de intentar obtener una lista de prefijos de directorio de una lista de nombres de archivos ordenados:
sort -u parece el doble de rápido que uniq, y esto es con la lectura ordenada de stdin y la escritura en stdout, por lo que todavía no veo ninguna paralelización. No tengo idea de por qué uniq debería ser mucho más lento que ordenar, ya que no tiene que ordenar la lista ...
La salida de este comando es muy pequeña (hay muchos duplicados), solo 264kb y la ordenación termina instantáneamente después de que se realiza el pv.
Las mismas velocidades permanecen si cambia el orden de los comandos, mi flujo está limitado por el tiempo de CPU aquí, no por el acceso al disco y los cachés (solo tengo 8 GB de RAM y mi intercambio no se usa)
Estoy ejecutando esto en una máquina fedora 31 con gnu coreutils sort y uniq y gnu awk; locale se establece en en_US.UTF-8
ACTUALIZACIÓN , ya que esto me intrigó bastante, hice algunas pruebas más, vamos a quitar la parte cortada y asegurarnos de que el archivo esté bien ordenado
cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test
Esto lleva 8.4 minutos. la prueba ahora es de 7.9GB grande
ejecutemos estas herramientas en el archivo en lugar de en una tubería, esto permitirá que estas herramientas realicen una mayor optimización, como ordenar en subprocesos múltiples. y también desde un ssd más rápido.
Es posible que no note que la ordenación también está tomando mucha memoria, ya que hace trucos inteligentes con archivos temporales en / tmp que pueden ser tmpfs y estarán en su ram (Intente ordenar un archivo más grande que / tmp, se ejecutará en el espacio problemas, es por eso que necesito el indicador -T. en el comando anterior)
Parece que su solución awk es la más rápida de estas 3 , y en realidad usa menos memoria
update2 y ahora con una configuración regional más simple
Esta vez, uniq gana la carrera ... como lo sugiere Stéphane Chazelas en los comentarios, establecer su ubicación en C hace que ordenar y uniq sea mucho más rápido.
fuente
sort
yuniq
? ¿Qué locale?