Portanto, eu tenho um arquivo muito grande (cerca de 10 GB) e preciso classificá-lo, assim como ao usar o utilitário 'sort', mas com mais eficiência.
O problema é que não tenho memória, poder de CPU, tempo nem espaço de troca livre para alimentar todo o tipo.
O bom é que o arquivo já está parcialmente ordenado (posso dizer que a distância de cada linha de sua posição final é menor que algum valor N). Esse tipo me lembra o clássico exemplo de classe de computador de usar heapsort com heap de tamanho N para esse propósito.
Pergunta: Existe alguma ferramenta unix que já faz isso efetivamente, ou eu preciso codificar um eu mesmo?
Obrigado -mk
Seria mais fácil dividir o arquivo em seções menores e classificá-las. Para dividir: -
split --lines=100000 large_file file_part.
Em seguida, classifique cada um deles usando a classificação normal
for suffix in 'ls file_part.* | cut -f2 -d.'
do
sort file_part.${suffix} > file_sorted.${suffix}
done
você pode então combinar por mesclar a classificação
sort -m file_sorted.*
Isso deve ser muito mais fácil em sua máquina.
Classificar, está usando o algoritmo de classificação de mesclagem R-way. A maneira mais rápida de fazer o seu trabalho seria:
sort myfile
isso implica complexidade de tempo O (n logn) e tempo O (n).
Se você particionar os dados, provavelmente pagará em termos de tempo.
O código acima tem um problema. Com a ordenação -m, os arquivos não têm garantia de serem mutuamente ordenados.
do manual do unix:
-m, --merge
merge already sorted files; do not sort
por exemplo,
arquivo1: a b c k l q arquivo2: d e m
sort -m file1 file2
a b c k l q e m
que não está em ordem.
Além disso, o fato de os elementos estarem em lugares menores que N não garante uma saída ordenada com o código acima:
arquivo: a e b c h f g
no arquivo N = 3 e todos os elementos são menos de 3 lugares do que seu lugar correto
arquivo1: h f g, arquivo2: b c d, arquivo3: a e
sort file1
produz:
arquivo1: fgh, arquivo2: bcd, arquivo3: ae
e
sorm -m file3 file2 file1
saídas:
a e b c d f g h
que está errado.