Ferramenta `uniq` mais rápida no Linux

Question 1

Vamos considerar como cada solução funciona.

uniqIsso requer que o arquivo já esteja classificado. Caso contrário, você terá que canalizá-lo sortprimeiro, o que significa que sortserá necessário ler o arquivo inteiro na memória, reordená-lo ( O(n log n)) e depois gravá-lo no canal. O trabalho do uniqé muito barato, já que basta comparar linhas adjacentes de sua entrada.
sort -uIsso combina o trabalho de sort | uniq. Isso precisa coletar todas as entradas exclusivas na memória, como o awkscript faz, mas também perde tempo classificando-as antes de produzir a saída. Isto é O(n log n), embora neste caso nseja o número de itens únicos, não todas as entradas. Então é melhor que o cachimbo.
sedNão sei por que você listou isso, pois não consigo pensar em uma boa maneira de fazer isso sed. Talvez se você primeiro classificar e direcionar para um sedscript, haja uma maneira de comparar linhas adjacentes. Então, sedestaria apenas fazendo o que uniqfaz, e uniqprovavelmente o fará da maneira mais eficiente possível.
awkEste é provavelmente o melhor porque realiza apenas a quantidade mínima de trabalho necessária. À medida que lê cada linha, ele faz uma pesquisa de hash eficiente para ver se a linha já está em sua memória e armazena apenas as linhas exclusivas como chaves de hash e um contador como valor. (Se a linha não estava presente anteriormente, a condição será verdadeira, então a linha será impressa. Caso contrário, não será.) Isso consome O(n)tempo e O(uniq n)memória.

Cada método usará uma quantidade considerável de memória, seja para classificar a entrada ou para controlar quais entradas foram vistas, para que possam remover duplicatas.

Answer

Vamos considerar como cada solução funciona.

uniqIsso requer que o arquivo já esteja classificado. Caso contrário, você terá que canalizá-lo sortprimeiro, o que significa que sortserá necessário ler o arquivo inteiro na memória, reordená-lo ( O(n log n)) e depois gravá-lo no canal. O trabalho do uniqé muito barato, já que basta comparar linhas adjacentes de sua entrada.
sort -uIsso combina o trabalho de sort | uniq. Isso precisa coletar todas as entradas exclusivas na memória, como o awkscript faz, mas também perde tempo classificando-as antes de produzir a saída. Isto é O(n log n), embora neste caso nseja o número de itens únicos, não todas as entradas. Então é melhor que o cachimbo.
sedNão sei por que você listou isso, pois não consigo pensar em uma boa maneira de fazer isso sed. Talvez se você primeiro classificar e direcionar para um sedscript, haja uma maneira de comparar linhas adjacentes. Então, sedestaria apenas fazendo o que uniqfaz, e uniqprovavelmente o fará da maneira mais eficiente possível.
awkEste é provavelmente o melhor porque realiza apenas a quantidade mínima de trabalho necessária. À medida que lê cada linha, ele faz uma pesquisa de hash eficiente para ver se a linha já está em sua memória e armazena apenas as linhas exclusivas como chaves de hash e um contador como valor. (Se a linha não estava presente anteriormente, a condição será verdadeira, então a linha será impressa. Caso contrário, não será.) Isso consome O(n)tempo e O(uniq n)memória.

Cada método usará uma quantidade considerável de memória, seja para classificar a entrada ou para controlar quais entradas foram vistas, para que possam remover duplicatas.

Question 2

Eu só queria salientar que o gnu uniqparece terrivelmente lento, mesmo em uma lista ordenada.

Apenas tentei obter uma lista de prefixos de diretório de uma lista de nomes de arquivos classificados:

$ 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 duas vezes mais rápido que uniq, e isso ocorre com sort lendo de stdin e gravando em stdout, então não vejo nenhuma paralelização ainda. Não tenho ideia de por que o uniq deveria ser muito mais lento do que classificar, já que não precisa classificar a lista ...

A saída deste comando é muito pequena (há muitas duplicatas), apenas 264kb e a classificação termina instantaneamente após a conclusão do pv.

As mesmas velocidades permanecem se você inverter a ordem dos comandos, meu fluxo é limitado pelo tempo de CPU aqui, não pelo acesso ao disco e aos caches (só tenho 8 GB de RAM e meu swap não é usado)

Estou executando isso em uma máquina fedora 31 com gnu coreutils sort e uniq e gnu awk; localidade está definida como en_US.UTF-8

ATUALIZAR, como isso me intrigou bastante, fiz mais alguns testes, vamos tirar a parte cortada do caminho e ter certeza de que o arquivo está bem classificado

cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test

Isso leva 8,4 minutos. o teste agora tem 7,9 GB

vamos executar essas ferramentas no arquivo em vez de em um canal, isso permitirá que essas ferramentas façam mais otimização, como a classificação em vários threads. e também de um SSD mais rápido.

Você pode não perceber que o sort também está consumindo muita memória, já que ele faz truques inteligentes com arquivos temporários em /tmp que podem ser tmpfs e estarão em sua memória RAM (tente classificar um arquivo maior que /tmp, você irá para o espaço problemas, é por isso que preciso do sinalizador -T no comando acima)

$ 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

Assim parecesua solução awk é a mais rápida dessas 3, e na verdade usa menos memória

atualização2 e agora com uma localidade mais simples

$ 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

Desta vezuniq vence a corrida... como Stéphane Chazelas sugere nos comentários, definir sua localidade como C torna a classificação e a uniq muito mais rápidas!

Answer