Utilitário de memória eficiente para retornar N primeiros valores classificados

Question

Eu gostaria de implementar um exemplo MapReduce muito popular usando apenas programas existentes operando de maneira UNIX. O problema é encontrar N valores mais frequentes em uma quantidade enorme de dados. A solução genérica em qualquer linguagem de programação de propósito geral é:

1. Mapeie cada valor da lista para uma tupla (valor, 1).
2. Agrupe os mesmos valores resumindo suas contagens.
3. Classifique os valores por contagem, mantendo os itens mais frequentes do N.

Para eficiência, cada etapa deve caber na memória e ser paralelizada, se possível. Assim, posso usar split , paste , xargs e sort de "utilitários principais" e parallel de "mais utils" para as duas primeiras etapas que ainda satisfazem as restrições de problemas. Mas, para implementar o último passo, eu preciso sempre manter não mais do que N valores simultaneamente ou então eu rapidamente ficarei sem memória, então obviamente eu não posso usar sort canalizado para head . Uma abordagem comum é usar a estrutura de dados da "fila de prioridades", mas existe um programa para isso?

    

Answer 1

A classificação GNU se beneficiaria de uma função --range para suportar essa operação comum: link

Então sugiro implementar isso em uma versão local do tipo (1), e vamos mesclar isso upstream também para torná-lo geralmente disponível