La herramienta `uniq` más rápida en Linux

8

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 htopcomando 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é?

MLSC
fuente
¿Has intentado ejecutarlos, posiblemente con time?
choroba
el tiempo es importante y también el uso y la fiabilidad de la memoria (quiero decir, cuál hace su trabajo con precisión)
MLSC
Todavía no ... Pero hice algunas pruebas antes ... y pregunté en alguna parte, algunos muchachos me dijeron que awk es lo mejor ... pero en htop ... veo que el uso de memoria está aumentando
MLSC
3
@MortezaLSC: es una compensación. Cuanto más rápido es el programa, más memoria se usa.
Cuonglm

Respuestas:

16

Consideremos cómo funciona cada solución.

  • uniqEsto requiere que el archivo ya esté ordenado. De lo contrario, sortprimero debe canalizarlo , lo que significa que sortdebe leer todo el archivo en la memoria, reordenarlo ( O(n log n)) y luego escribirlo en la tubería. El trabajo de uniqes muy barato, ya que solo tiene que comparar líneas adyacentes de su entrada.

  • sort -uEsto combina el trabajo de sort | uniq. Esto tiene que recopilar todas las entradas únicas en la memoria como lo hace el awkscript, pero también desperdicia tiempo clasificándolas antes de producir la salida. Esto es O(n log n), aunque en este caso nes el número de elementos únicos, no todas las entradas. Entonces es mejor que la tubería.

  • sedNo estoy seguro de por qué enumeró esto, ya que no puedo pensar en una buena manera de hacerlo sed. Tal vez si primero lo ordena y canaliza a un sedscript, hay una manera de comparar líneas adyacentes. Entonces sed, solo estaría haciendo lo que uniqhace, y uniqprobablemente lo haga de la manera más eficiente posible.

  • awkEste 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 usa O(n)tiempo y O(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.

Barmar
fuente
1
+1 La explicación awktambié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.
Ricitos
@Barmar perdón, pero cuando tengo un archivo grande (16 G) con capacidad de memoria 8G, ¿qué va a pasar con mi memoria?
MLSC
8
@goldilocks, sortrecurre 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).
Stéphane Chazelas
Es verdad. Entonces, si se encuentra con un caso en el que se awkqueda sin memoria, sortpuede 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.
Barmar
@Barmar ¿Cómo dedujo que el tiempo de reordenamiento aumenta O(n log n)? ¿O simplemente lo sabes desde otro lado?
jimmij
0

Solo quería señalar que el ñu uniqparece 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:

$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes

36.7GiB 0:07:41 [81.4MiB/s]

$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2

36.7GiB 0:03:14 [ 193MiB/s]

$ pv all_files  | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3                                        
36.7GiB 0:02:18 [ 270MiB/s] 

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)

$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps

$ time awk '!x[$0]++' test > /dev/null                                                                                                                             
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                  
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps

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

$ export LC_ALL=c
$ time sort -u test > /dev/null                                                                                                                                             1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k

$ time awk '!x[$0]++' test > /dev/null                                                                                                                                1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                               
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps

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.

Jens Timmerman
fuente
¿Qué implementación de sorty uniq? ¿Qué locale?
Stéphane Chazelas