Classifique otimamente um conjunto de dados de N chaves quando a primeira chave já estiver ordenada

Question

Frequentemente me deparo com situações em que dados ordenados parcialmente precisam ser classificados. A primeira coluna já está classificada, as posteriores não são. Como este exemplo de duas colunas:

1 5
1 3
2 10
2 -1
2 3
3 11
3 -200
3 20

A saída desejada é aquela produzida por

sort -k 1,1g -k 2,2g

que funciona, mas tem o problema de que nada sairá do tipo até que toda a entrada tenha sido lida. Quando a entrada é de vários gigabytes de texto, isso pode demorar um pouco, durante o qual nada a jusante do tipo em um pipeline pode ser executado. Ele também não é muito eficiente em termos de uso de memória, já que o conjunto de dados inteiro deve residir lá de uma só vez, mesmo que para alcançar o tipo desejado, apenas uma pequena fração realmente precise estar lá.

Com um script, não seria difícil dividir isso em partes e depois classificar cada parte. O comando sort tem uma opção em algum lugar para notificá-lo de que os dados nessa coluna já estão ordenados? Eu não vejo isso no tipo 8.4, mas talvez eu tenha perdido isso?

Se a classificação encontrar um valor fora de ordem na coluna que foi informada já está ordenada, deve sair. Isso indica um erro no processamento upstream.

    

Answer 1

Eu não posso fazer isso com o único sort . Pode não ser possível.

Na minha solução awk manipula a primeira coluna e executa sort quantas vezes forem necessárias. O script recebe entrada de stdin, imprime para stdout).

#!/usr/bin/awk -f

BEGIN { command = "sort -k 2,2g" }

{
if ( NR==1 ) {
   val=$1
   buf=$0
}
else
if ( $1 < val ) {
   print "Unsorted 1st column detected. Processing last valid chunk and aborting." > "/dev/stderr"
   exit 1
   }
else {
if ( $1 == val )
   buf=buf"\n"$0
else
   {
   print buf | command
   close(command)
   buf=$0
   val=$1
   }
   }
}

END { print buf | command }

Notas:

• close(command) é crucial. Sem ele, todos os canais para command iriam para um single sort .
• Na minha opinião, os operadores de comparação awk lidam com números muito bem. Para ter certeza de que a solução funciona da mesma forma que o sort funcionaria, você precisa recuperar o status de saída de sort -c -k 1,1g para val"\n"$1 e separadamente para $1"\n"val e, em seguida, criar a lógica de script nessa . Isso executaria dois sort processos por linha de entrada, espero um grande desempenho.

Answer 2

Perl para o resgate!

Faz exatamente o que você pediu, ele canaliza pedaços da entrada começando com o mesmo número para ordenar que opera somente na segunda coluna.

#!/usr/bin/perl
use warnings;
use strict;

my $sort;

my $first = -1;
while (<>) {
    my ($x, $y) = split;
    if ($first != $x) {
        die "Unsorted line $." if $first > $x;
        $first = $x;
        open $sort, '|-', 'sort -k2,2n' or die $!;
    }
    print {$sort} $_;
}

O único problema pode ser o valor inicial de $first : se sua entrada começar com um número negativo na primeira coluna, você precisará especificar um valor menor.

Eu usei o n sort em vez de g , já que parece um pouco mais rápido na minha máquina.

    

Answer 3

Kamil Cuk postou esta resposta no outro tópico. Eu vou tentar apagar esse tópico agora, já que aparentemente ter isso em dois lugares é um não não, e gostaria de preservar essa resposta aqui.

O script a seguir imprime linhas com a mesma primeira coluna em um arquivo temporário e as classifica.

file=$1
# create temporary file
temp=$(mktemp)
trap 'rm "$temp"' EXIT
i_last=""
while read -r i j; do
    if [ "$i" != "$i_last" ]; then
        # output sorted temporary file
        sort -n $temp
        # and truncate temporary file
        > $temp
        # increment first column pointer
        i_last=$i
    fi
    # print all lines into temporary file
    echo "$i" "$j" >>$temp
done <"$file"
# dont forget leftovers
sort -n "$temp"