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

Question 1

Consideremos cómo funciona cada solución.

uniqEsto requiere que el archivo ya esté ordenado. De lo contrario, primero debe canalizarlo sort, lo que significa que sortdebe leer el archivo completo en la memoria, reordenarlo ( O(n log n)) y luego escribirlo en el canal. El trabajo de uniqes muy barato, ya que sólo 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 awklo hace el script, pero también pierde tiempo clasificándolas antes de producir la salida. Esto es así O(n log n), aunque en este caso nes el número de elementos únicos, no todas las entradas. Entonces es mejor que la pipa.
sedNo estoy seguro de por qué mencionaste esto, ya que no se me ocurre ninguna buena manera de hacerlo sed. Tal vez si primero lo ordena y lo canaliza a un sedscript, haya una manera de comparar líneas adyacentes. Entonces sedsería simplemente hacer lo que uniqhace, y uniqprobablemente lo haga, de la manera más eficiente posible.
awkProbablemente esto sea lo mejor porque solo hace la cantidad mínima de trabajo necesaria. A medida que lee cada línea, realiza una búsqueda hash eficiente 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.) 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 realizar un seguimiento de qué entradas se han visto para poder eliminar duplicados.

Answer

Consideremos cómo funciona cada solución.

uniqEsto requiere que el archivo ya esté ordenado. De lo contrario, primero debe canalizarlo sort, lo que significa que sortdebe leer el archivo completo en la memoria, reordenarlo ( O(n log n)) y luego escribirlo en el canal. El trabajo de uniqes muy barato, ya que sólo 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 awklo hace el script, pero también pierde tiempo clasificándolas antes de producir la salida. Esto es así O(n log n), aunque en este caso nes el número de elementos únicos, no todas las entradas. Entonces es mejor que la pipa.
sedNo estoy seguro de por qué mencionaste esto, ya que no se me ocurre ninguna buena manera de hacerlo sed. Tal vez si primero lo ordena y lo canaliza a un sedscript, haya una manera de comparar líneas adyacentes. Entonces sedsería simplemente hacer lo que uniqhace, y uniqprobablemente lo haga, de la manera más eficiente posible.
awkProbablemente esto sea lo mejor porque solo hace la cantidad mínima de trabajo necesaria. A medida que lee cada línea, realiza una búsqueda hash eficiente 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.) 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 realizar un seguimiento de qué entradas se han visto para poder eliminar duplicados.

Question 2

Sólo quería señalar que gnu uniqparece terriblemente lento, incluso en una lista ordenada.

Intenté obtener una lista de prefijos de directorio a partir 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 dos veces más rápido que uniq, y esto es con lectura de clasificación desde stdin y escritura en stdout, por lo que no veo que haga ninguna paralelización todavía. 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 264 kb y la clasificación finaliza instantáneamente después de que se realiza pv.

Las mismas velocidades se mantienen si inviertes el orden de los comandos, mi flujo está limitado por el tiempo de la CPU aquí, no por el acceso al disco ni por 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; la configuración regional está configurada en en_US.UTF-8

ACTUALIZAR, como esto me intrigó bastante, hice algunas pruebas más, eliminemos la parte cortada y asegurémonos 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 tiene un tamaño de 7,9 GB

Ejecutemos estas herramientas en el archivo en lugar de en una tubería, esto permitirá que estas herramientas realicen una mayor optimización, como la clasificación en múltiples subprocesos. y también desde un ssd más rápido.

Es posible que no notes que ordenar también consume mucha memoria, ya que realiza trucos inteligentes con archivos temporales en /tmp que podrían ser tmpfs y estarán en tu ram (intenta ordenar un archivo más grande que /tmp, te quedarás sin 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

Así parecetu solución awk es la más rápida de estas 3, y en realidad utiliza la menor cantidad de memoria

actualización2 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 vezUniq gana la carrera.... como sugiere Stéphane Chazelas en los comentarios, ¡establecer su configuración regional en C hace que ordenar y unificar sea mucho más rápido!

Answer