Como o comando de sorting do UNIX pode classificar um arquivo muito grande?

O comando de sort UNIX pode classificar um arquivo muito grande como este:

 sort large_file 

Como o algoritmo de sorting é implementado?

Por que isso não causa consumo excessivo de memory?

   

Os detalhes algorítmicos do comando Ordenação do UNIX informam que o Unix Sort usa um algoritmo de sorting de mesclagem R-Way externo. O link entra em mais detalhes, mas em essência ele divide a input em partes menores (que se encheckboxm na memory) e, em seguida, mescla cada parte no final.

O comando sort armazena dados de trabalho em arquivos de disco temporários (geralmente em /tmp ).

AVISO: Esse script inicia um shell por pedaço, para arquivos realmente grandes, isso pode ser centenas.


Aqui está um script que escrevi para esse propósito. Em uma máquina de 4 processadores, ela melhorou o desempenho de sorting em 100%!

 #! /bin/ksh MAX_LINES_PER_CHUNK=1000000 ORIGINAL_FILE=$1 SORTED_FILE=$2 CHUNK_FILE_PREFIX=$ORIGINAL_FILE.split. SORTED_CHUNK_FILES=$CHUNK_FILE_PREFIX*.sorted usage () { echo Parallel sort echo usage: psort file1 file2 echo Sorts text file file1 and stores the output in file2 echo Note: file1 will be split in chunks up to $MAX_LINES_PER_CHUNK lines echo and each chunk will be sorted in parallel } # test if we have two arguments on the command line if [ $# != 2 ] then usage exit fi #Cleanup any lefover files rm -f $SORTED_CHUNK_FILES > /dev/null rm -f $CHUNK_FILE_PREFIX* > /dev/null rm -f $SORTED_FILE #Splitting $ORIGINAL_FILE into chunks ... split -l $MAX_LINES_PER_CHUNK $ORIGINAL_FILE $CHUNK_FILE_PREFIX for file in $CHUNK_FILE_PREFIX* do sort $file > $file.sorted & done wait #Merging chunks to $SORTED_FILE ... sort -m $SORTED_CHUNK_FILES > $SORTED_FILE #Cleanup any lefover files rm -f $SORTED_CHUNK_FILES > /dev/null rm -f $CHUNK_FILE_PREFIX* > /dev/null 

Consulte também: ” Classificando arquivos grandes mais rápido com um script de shell ”

Eu não estou familiarizado com o programa, mas acho que isso é feito por meio de sorting externa (a maior parte do problema é mantida em arquivos temporários, enquanto uma parte relativamente pequena do problema é mantida na memory por vez). Veja The Art of Computer Programming, de Donald Knuth , vol. 3 Classificando e pesquisando, Seção 5.4 para uma discussão muito aprofundada do assunto.

 #!/bin/bash usage () { echo Parallel sort echo usage: psort file1 file2 echo Sorts text file file1 and stores the output in file2 } # test if we have two arguments on the command line if [ $# != 2 ] then usage exit fi pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {} ';' rm {} > $2 

Observe atentamente as opções de sorting para acelerar o desempenho e entender o impacto na máquina e no problema. Os principais parâmetros no Ubuntu são

  • Localização de arquivos temporários -T directory_name
  • Quantidade de memory para usar -SN% (N% de toda a memory a ser usada, quanto mais, melhor, mas evite a assinatura que causa a troca para o disco. Você pode usá-la como “-S 80%” para usar 80% da RAM disponível, ou “-S 2G” para 2 GB de RAM.

O questionador pergunta “Por que não há alto uso de memory?” A resposta para isso vem da história, máquinas unix antigas eram pequenas e o tamanho da memory padrão era pequeno. Ajuste isso o máximo possível para que sua carga de trabalho melhore amplamente o desempenho de sorting. Defina o diretório de trabalho para um local no dispositivo mais rápido que tenha espaço suficiente para armazenar pelo menos 1,25 * do tamanho do arquivo que está sendo classificado.

A memory não deve ser um problema – o tipo já cuida disso. Se você quiser otimizar o uso do seu processador multi-core, eu implementei isso em um pequeno script (semelhante a alguns que você pode encontrar na rede, mas mais simples / mais limpo que a maioria deles;)).

 #!/bin/bash # Usage: psort filename   # In this example a the file largefile is split into chunks of 20 MB. # The part are sorted in 4 simultaneous threads before getting merged. # # psort largefile.txt 20m 4 # # by hp split -b $2 $1 $1.part suffix=sorttemp.`date +%s` nthreads=$3 i=0 for fname in `ls *$1.part*` do let i++ sort $fname > $fname.$suffix & mres=$(($i % $nthreads)) test "$mres" -eq 0 && wait done wait sort -m *.$suffix rm $1.part*