▷¿Cómo restar dos listas (rápido)? ✔️ Foro Ayuda 【 2024 】

Solución:

Puedes usar comm para eliminar todo lo que sea común a ambas listas:

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

Esto ordena ambas listas en el orden comm espera, compara, genera solo elementos que son exclusivos de cualquiera de las listas y los vuelve a clasificar en orden numérico.

Si ambas listas están ordenadas lexicográficamente (según LC_COLLATE), puede evitar volver a ordenar:

listr=($(comm --nocheck-order -3 <(printf "%sn" "$list1[@]") <(printf "%sn" "$list2[@]")))

Esto también funciona muy bien si los valores que necesita comparar están almacenados en archivos.

#!/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:")
typeset -p listr

Abstracto:

Para listas largas, si las listas ya están ordenadas, comm (alg7) es el más rápido.
La solución zsh es (de lejos) la más rápida si no se lee ningún archivo, es decir, las listas se dan "en memoria". Sin embargo, esa no es una comparación justa con todas las demás soluciones que tienen que leer valores de archivos. Cambié el código original (que evitó el tiempo para leer archivos de la prueba) a un código que también incluye el tiempo para leer archivos.

Esta es una respuesta de la comunidad, está destinada a informar solo el tiempo de cada respuesta.

Por favor HACER edite y agregue su solución / opción para comparar todo.

Lista de algoritmos

alg1: solución en bucle ingenua.
alg2: usando externo sort y uniq -u
alg3: procesando un string en bash.
alg4: únase -v en listas ordenadas (Gracias @Kusalananda)
alg5: comm (Gracias @Stephen Kitt)
alg6: zsh (Gracias @Llua)
alg7: comm pero en archivos ya ordenados (gracias @Stephen Kitt)

Nota del manual de zsh:

$ nombre de matriz
Si arrayname es el nombre (NB, no contenido) de un array variable, todos los elementos contenidos en arrayname se eliminan de la sustitución de name.

Pruebas

Como hay varias formas de resolver esto, necesitamos un marco general para probar (con justicia) las respuestas.

Algunas pautas (cámbielas si las considera injustas):

Mide suficientes repeticiones para tener una precisión razonable.
Mida dentro del caparazón utilizado (evite cargar / descargar el caparazón).
Evite la sobrecarga de salida al no imprimir o redirigir a / dev /null.

Código de prueba:

#!/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() 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 '%sn' "$a"


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

alg5()  #listr=$(
                    comm -3 <(printf "%sn" "$list1[@]" 

alg6() zsh -c '  alg6()
                           list1=( $(cat list1.txt) )
                           list2=( $(cat list2.txt) )
                           listr=("$(@)list1:")
                           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 '%sn' "$list1[@]" | sort >list1.txt
printf '%sn' "$list2[@]" | sort >list2.txt

repeats=$1:-10; shift
out=$1:-no    ; shift
(($#==0)) && set -- alg1..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 corta (como se presenta en el 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

Los tiempos para alg6 son los informados por zsh y después los informados por bash.
Además, el tiempo de ejecución de zsh es realmente menor (0.050) si la lectura de archivos se elimina de la función al exterior.

Lista más larga

La prueba de una lista de solo 500 valores (10 repeticiones) revela que alg1 es muy ineficiente. Eliminándolo de más pruebas:

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

La prueba de valores de 5k (10 repeticiones) revela que alg3 también es 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

Prueba de valores de 50k (10 repeticiones):

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 repeticiones)

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

Por 1 M (10 repeticiones)

alg4 11.127 10.804 0.251
alg7 5.772 5.525 0.230

¡Haz clic para puntuar esta entrada!

(Votos: 0 Promedio: 0)

¿Cómo restar dos listas (rápido)?