Como subtrair duas listas (rápido)? [duplicado]

Question

O que é uma maneira rápida de subtrair duas listas ¹ . As listas podem ser pequenas, talvez uma maneira direta em trabalhos de shell. Ou as listas podem ser longas, talvez ferramentas externas sejam as mais rápidas.

Suponha que você tenha duas listas:

list1=( 1 2 3 4 5 6 7 8 9 10 11 12 )
list2=( 1 2 3   5   7 8 9    11 12 )

Como remover todos os elementos da lista2 da lista1 para obter uma lista resultante ( listr ) equivalente a:

listr=( 4 6 10 )

As listas podem estar dentro dos arquivos também, como deveria se a lista for grande (pode usar muita memória).

Para tornar esta questão breve, estou colocando todos os algoritmos em uma resposta da comunidade.

Por favor, leia os vários testes feitos lá.

Multisets

A pergunta original foi criada para encontrar os elementos que faltam em uma lista completa (list1) na lista2, sem repetições.

No entanto, se as listas forem:

list1=( a a b b b c     d d   )
list2=(     b b   c c c d d e )

E a definição de subtração multiset é como nesta página , o resultado esperado é:

listr= ( a a b )

Apenas os algoritmos 1 e 3 funcionam corretamente.
Nenhum algoritmo 2 ou 4 pode fazer isso.
Algoritmo 5 (comm) poderia corresponder a essa definição fazendo comm -23 .
Algoritmo 6 (zsh) falha. Eu não sei como fazer isso funcionar.
Algoritmo 7 (comm). Como dito acima, usando -23 funciona.

Eu não analisei todos os algoritmos para a definição Definir diferença simétrica que deve render:

listr=( a a b c c e )

Mas comm -3 list1.txt list2.txt | tr -d ' \t' funciona.

¹ Sim, sei que é uma má idéia processar um arquivo de texto (lista de linhas ) em um shell, é lento pelo design.
Mas há casos em que parece que não pode ser evitado .
Eu (nós) estamos (estamos) abertos a sugestões.

    

Answer 1

Você pode usar comm para remover qualquer coisa que seja comum a ambas as listas:

listr=($(comm -3 <(printf "%s\n" "${list1[@]}" | sort) <(printf "%s\n" "${list2[@]}" | sort) | sort -n))

Isso classifica as duas listas na ordem comm expects, compara-as, produz apenas itens que são exclusivos para qualquer uma das listas e os classifica novamente em ordem numérica.

Se as duas listas forem ordenadas lexicograficamente ( conforme LC_COLLATE ) , você pode evitar a classificação novamente:

listr=($(comm --nocheck-order -3 <(printf "%s\n" "${list1[@]}") <(printf "%s\n" "${list2[@]}")))

Isso também funciona muito bem se os valores que você precisa comparar estiverem armazenados em arquivos.

    

Answer 2

#!/bin/zsh
list1=( 1 2 3 4 5 6 7 8 9 10 11 12 )
list2=( 1 2 3   5   7 8 9    11 12 )
listr=("${(@)list1:|list2}")
typeset -p listr

    

Answer 3

Resumo:

• Para listas longas, se as listas já estiverem ordenadas, comm (alg7) é o mais rápido.

• A solução zsh é (de longe) a mais rápida se nenhum arquivo é lido, isto é, as listas recebem "na memória". No entanto, isso não é uma comparação justa com todas as outras soluções que precisam ler valores de arquivos. Eu mudei o código original (que evitou o tempo para ler arquivos de testes) para um código que também inclui o tempo para ler arquivos.

Esta é uma resposta da comunidade, destina-se apenas a relatar o tempo de cada resposta.

Por favor DO edite e adicione a sua solução / opção para comparar tudo.

Lista de algoritmos

• alg1: solução ingênua em loop.
• alg2: usando sort e uniq -u externos
• alg3: processando uma string no bash.
• alg4: junte-se às listas ordenadas (Obrigado @Kusalananda )
• alg5: comm (Obrigado @Stephen Kitt )
• alg6: zsh (Agradecimentos @Llua )
• alg7: comm mas em arquivos já classificados (obrigado @Stephen Kitt )

Nota do manual do zsh:

${name:|arrayname}
If arrayname is the name (N.B., not contents) of an array variable, then any elements contained in arrayname are removed from the substitution of name.

Teste

Como existem várias maneiras de resolver isso, precisamos de uma estrutura geral para testar (com justiça) as respostas.

Algumas diretrizes (altere-as se você achar que elas são injustas):

• Meça repetições suficientes para ter uma precisão razoável.
• Medida dentro do shell usado (evite carregar / descarregar o shell).
• Evite a sobrecarga de saída, não imprimindo ou redirecionando para / dev / null.

Código de teste:

#!/bin/bash
alg1(){
         arr=( "${list1[@]}" )
         for i in "${list2[@]}"; do
             for j in "${!arr[@]}"; do
         if [[ "$i" == "${arr[j]}" ]]; then
             unset arr["$j"]
             break
         fi
             done
     done
     printf '%s ' "${arr[@]}"; echo
}

alg2(){
         arr=($({ printf '%s\n' "${list1[@]}" "${list2[@]}"; } | sort | uniq -u))
         printf '%s ' "${arr[@]}"; echo
}

alg3(){
         a=" $(printf '%s ' ${list1[@]})" # Watch the space at the start!!.
         for i in "${list2[@]}"; do
         a=${a/ "$i" / };
     done
     printf '%s\n' "$a"
}

alg4(){  join -v 1 list1.txt list2.txt ; }

alg5(){  #listr=$(
                    comm -3 <(printf "%s\n" "${list1[@]}" | sort) \
                            <(printf "%s\n" "${list2[@]}" | sort) |
                sort -n
     #)
      }

alg6(){ zsh -c '  alg6(){
                           list1=( $(cat list1.txt) )
                           list2=( $(cat list2.txt) )
                           listr=("${(@)list1:|list2}")
                           typeset -p listr
                        }
                  TIMEFMT="%E %U %S"
                  time ( for ((k=0;k<'"$1"';k++)); do alg6; done; )
                '
      }
#: <<-\_comment_
alg7(){ comm -23 list1.txt list2.txt; }

try(){ for ((k=0;k<$1;k++)); do "$2"; done; }

#list1=( 1 2 3 4 5 6 7 8 9 10 11 12 )
#list2=( 1 2 3   5   7 8 9    11 12 )

#list1=( a a b b b c     d d   )
#list2=(     b b   c c c d d e )

size=1000000
list1=( "0" $(seq 1 "$size") )
list2=( "${list1[@]}" ); unset "list2[123]" "list2[234]" "list2[345]"

printf '%s\n' "${list1[@]}" | sort >list1.txt
printf '%s\n' "${list2[@]}" | sort >list2.txt

repeats=${1:-10}; shift
out=${1:-no}    ; shift
(($#==0)) && set -- alg{1..7}

TIMEFORMAT='%R %U %S'
for   i
do    printf '%s ' "$i"
      if [[ $out == no ]]; then
      [[ $i != alg6 ]] &&
          time try "$repeats" "$i" >/dev/null ||
          time alg6 "$repeats" >/dev/null
      else
      [[ $i != alg6 ]] &&
          time try "$repeats" "$i"            ||
          time alg6 "$repeats"
      fi
done

Resultados:

Lista curta (conforme apresentada no código):

$ ./script
alg1 2.056 0.806 1.237
alg2 3.478 3.126 1.756
alg3 0.999 0.728 0.304
alg4 1.186 0.780 0.434
alg5 5.234 1.926 1.722
alg6 2.71s 1.64s 1.26s
     2.758 1.637 1.265
alg7 1.156 0.799 0.422

Os tempos para alg6 são reportados por zsh e depois como relatado por bash.
Além disso, o tempo de execução de zsh é realmente menor (0,050) se a leitura dos arquivos for removida da função para fora.

Lista mais longa

Testar uma lista de apenas 500 valores (10 repetições) revela que alg1 é muito ineficiente. Removendo-o de mais testes:

alg1 4.149 3.471 0.657
alg2 0.145 0.055 0.063
alg3 0.219 0.180 0.009
alg4 0.039 0.015 0.003
alg5 0.149 0.018 0.027
alg6 0.06s 0.02s 0.02s
     0.087 0.030 0.018
alg7 0.033 0.008 0.008

Teste de valores de 5k (10 repetições) revela que alg3 também é ineficiente:

alg2 0.590 0.526 0.187
alg3 12.957 12.888 0.044
alg4 0.098 0.047 0.008
alg5 0.654 0.028 0.036
alg6 0.16s 0.12s 0.04s
     0.211 0.118 0.044
alg7 0.038 0.022 0.014

Teste de 50k valores (10 repetições):

alg2 6.487 5.838 1.611
alg4 0.488 0.469 0.019
alg5 5.073 0.250 0.056
alg6 1.42s 1.20s 0.21s
     1.467 1.206 0.216
alg7 0.271 0.247 0.014

para 500k (10 repetições)

alg4 5.471 5.269 0.156
alg6 15.14s 13.33s 1.91s
     15.215 13.335 1.926
alg7 2.833 2.655 0.138

Para 1 M (10 repetições)

alg4 11.127 10.804 0.251
alg7 5.772 5.525 0.230