Encontre o menor conjunto de valores em que pelo menos um valor está presente em cada linha de um arquivo

Question

Eu tenho um arquivo df como:

1   4
1   6
1   7
1   10
2   3
2   9
2   10
3   4
4   7
9   10

Eu preciso identificar o menor conjunto de valores para que cada linha em df contenha pelo menos um desses valores.

Do df acima, o out desejado é:

1
2
4
9

Eu tenho um processo que funciona, mas é terrivelmente lento. Existe uma maneira de executar isso mais rapidamente ou paralelizar o processo?

x=1  
while [ $x -gt 0 ]  
do  
    i=$(paste df | tr '\t' '\n' | sort | uniq -c | 
        sort -r -k1,1 -k2,2n | awk 'NR==1{print $2}')  
    echo $i >> out  
    grep -vw $i df > tmpdf  
    cat tmpdf > df  
    x=$(paste df | wc -l)  
done

    

Answer 1

Aqui está um perl "barulhento":

perl -lane '
        for $f (@F) {push @{$x{$f}}, $.}                          # 1.
    } END {
        use List::Util qw/any first/;
        sub sort_by_count_desc {
            map  { $_->[0] } 
            sort { $b->[1] <=> $a->[1] || $a->[0] <=> $b->[0] } 
            map  { [$_, scalar(@{$x{$_}})] } 
            @_ 
        }
        @ordered = sort_by_count_desc(keys %x);                   # 2.
        %result = ();
        for ($i=1; $i<=$.; $i++) {                                # 3.
            $node = first { any {$_ == $i} @{$x{$_}} } @ordered;  # 4.
            $result{$node} = 1;
        }
        print join "\n", sort_by_count_desc(keys %result);
' df

Onde

1. faz um loop sobre as linhas do arquivo e mapeia cada valor para a lista de linhas que aparece em
2. cria uma linha ordenada dos valores classificados pelo tamanho da lista de aparências, decrescente
3. faz um loop no intervalo de números de linha e para cada número de linha
4. localiza o primeiro valor para o qual o número da linha aparece

Isso gera

1
2
4
10

    

Answer 2

Esta é uma otimização "muda" do Linux usando bash , mas não é especialmente portátil e não melhora o algoritmo:

f=$(mktemp) ; cp df $f
while [ -s $f ]  ; do   
    tr '\t' '\n' < $f | sort | uniq -c | sort -r -k1,1 -k2,2n | 
    grep -om1 '\S$' | tee >(grep -vwf - $f | sponge $f)
done
rm $f

Notas:

• Usar o arquivo de entrada df como um rascunho é uma prática ruim, use mktemp em seu lugar.

• A saída vai para STDOUT . Altere done para done > out , se desejado.

• O sponge util remove a necessidade de nomear um arquivo tmpdf .

• Usa tee e grep -f - em vez de uma variável de sequência de caracteres de pesquisa $i .

• Verificar se wc -l é 0 não é necessário; test -s é suficiente.