Intersección de dos matrices en BASH

12

Tengo dos matrices como esta:

A=(vol-175a3b54 vol-382c477b vol-8c027acf vol-93d6fed0 vol-71600106 vol-79f7970e vol-e3d6a894 vol-d9d6a8ae vol-8dbbc2fa vol-98c2bbef vol-ae7ed9e3 vol-5540e618 vol-9e3bbed3 vol-993bbed4 vol-a83bbee5 vol-ff52deb2)
B=(vol-175a3b54 vol-e38d0c94 vol-2a19386a vol-b846c5cf vol-98c2bbef vol-7320102b vol-8f6226cc vol-27991850 vol-71600106 vol-615e1222)

Las matrices no están ordenadas y posiblemente podrían contener elementos duplicados.

  1. Me gustaría hacer la intersección de estas dos matrices y almacenar los elementos en otra matriz. ¿Como podría hacerlo?

  2. Además, ¿cómo obtendría la lista de elementos que aparecen en B y no están disponibles en A?

Bogdan
fuente
2
Use un lenguaje de programación real, no un shell para este tipo de tarea.
Stéphane Chazelas 12/12/2013
1
¿Necesita retener el orden de los elementos? Si hay elementos duplicados (por ejemplo, A y B contienen foodos veces), ¿los necesita duplicados en el resultado?
Gilles 'SO- deja de ser malvado'

Respuestas:

13

comm(1)es una herramienta que compara dos listas y puede darle la intersección o diferencia entre dos listas. Las listas deben ordenarse, pero eso es fácil de lograr.

Para obtener sus matrices en una lista ordenada adecuada para comm:

$ printf '%s\n' "${A[@]}" | LC_ALL=C sort

Eso convertirá la matriz A en una lista ordenada. Haz lo mismo para B.

Para usar commpara devolver la intersección:

$ comm -1 -2 file1 file2

-1 -2 dice que elimine las entradas exclusivas del archivo1 (A) y exclusivas del archivo2 (B): la intersección de las dos.

Para que devuelva lo que está en el archivo 2 (B) pero no en el archivo 1 (A):

$ comm -1 -3 file1 file2

-1 -3 dice que elimine las entradas exclusivas de file1 y comunes a ambas, dejando solo aquellas exclusivas de file2.

Para alimentar dos tuberías comm, utilice la función "Sustitución de proceso" de bash:

$ comm -1 -2 <(pipeline1) <(pipeline2)

Para capturar esto en una matriz:

$ C=($(command))

Poniendolo todo junto:

# 1. Intersection
$ C=($(comm -12 <(printf '%s\n' "${A[@]}" | LC_ALL=C sort) <(printf '%s\n' "${B[@]}" | LC_ALL=C sort)))

# 2. B - A
$ D=($(comm -13 <(printf '%s\n' "${A[@]}" | LC_ALL=C sort) <(printf '%s\n' "${B[@]}" | LC_ALL=C sort)))
camh
fuente
Esto solo funcionará si sus valores no contienen \n.
Chris Down
@ChrisDown: Eso es correcto. Siempre trato de escribir scripts de shell que se citan correctamente y manejan todos los caracteres, pero me he dado por vencido en \ n. NUNCA lo he visto en un nombre de archivo, y un gran grupo de herramientas de Unix funcionan con \ n registros delimitados que pierdes mucho si intentas manejar \ n como un carácter válido.
camh
1
Lo he visto en los nombres de archivo cuando uso administradores de archivos GUI que no desinfectan correctamente los nombres de archivos de entrada que se copian de otro lugar (además, nadie dijo nada sobre los nombres de archivos).
Chris Down
Para proteger \nintente esto:arr1=( one two three "four five\nsix\nseven" ); arr2=( ${arr1[@]:1} "four five\\nsix" ); n1=${#arr1[@]}; n2=${#arr2[@]}; arr=( ${arr1[@]/ /'-_-'} ${arr2[@]/ /'-_-'} ); arr=( $( echo "${arr[@]}"|tr '\t' '-t-'|tr '\n' '-n-'|tr '\r' '-r-' ) ); arr1=( ${arr[@]:0:${n1}} ); arr2=( ${arr[@]:${n1}:${n2}} ); unset arr; printf "%0.s-" {1..10}; printf '\n'; printf '{'; printf " \"%s\" " "${arr1[@]}"; printf '}\n'; printf "%0.s-" {1..10}; printf '\n'; printf '{'; printf " \"%s\" " "${arr2[@]}"; printf '}\n'; printf "%0.s-" {1..10}; printf '\n\n'; unset arr1; unset arr2
Jason R. Mick
Uno no debe establecer LC_ALL=C. En cambio, establezca LC_COLLATE=Cla misma ganancia de rendimiento sin otros efectos secundarios. Para obtener resultados correctos , también deberá establecer la misma clasificación para la commque se utilizó sort, por ejemplo:unset LC_ALL; LC_COLLATE=C ; comm -12 <(printf '%s\n' "${A[@]}" | sort) <(printf '%s\n' "${B[@]}" | sort)
Sorpigal
4

Puede obtener todos los elementos que están en A y B recorriendo ambas matrices y comparando:

A=(vol-175a3b54 vol-382c477b vol-8c027acf vol-93d6fed0 vol-71600106 vol-79f7970e vol-e3d6a894 vol-d9d6a8ae vol-8dbbc2fa vol-98c2bbef vol-ae7ed9e3 vol-5540e618 vol-9e3bbed3 vol-993bbed4 vol-a83bbee5 vol-ff52deb2)
B=(vol-175a3b54 vol-e38d0c94 vol-2a19386a vol-b846c5cf vol-98c2bbef vol-7320102b vol-8f6226cc vol-27991850 vol-71600106 vol-615e1222)

intersections=()

for item1 in "${A[@]}"; do
    for item2 in "${B[@]}"; do
        if [[ $item1 == "$item2" ]]; then
            intersections+=( "$item1" )
            break
        fi
    done
done

printf '%s\n' "${intersections[@]}"

Puede obtener todos los elementos en B pero no en A de manera similar:

A=(vol-175a3b54 vol-382c477b vol-8c027acf vol-93d6fed0 vol-71600106 vol-79f7970e vol-e3d6a894 vol-d9d6a8ae vol-8dbbc2fa vol-98c2bbef vol-ae7ed9e3 vol-5540e618 vol-9e3bbed3 vol-993bbed4 vol-a83bbee5 vol-ff52deb2)
B=(vol-175a3b54 vol-e38d0c94 vol-2a19386a vol-b846c5cf vol-98c2bbef vol-7320102b vol-8f6226cc vol-27991850 vol-71600106 vol-615e1222)

not_in_a=()

for item1 in "${B[@]}"; do
    for item2 in "${A[@]}"; do
        [[ $item1 == "$item2" ]] && continue 2
    done

    # If we reached here, nothing matched.
    not_in_a+=( "$item1" )
done

printf '%s\n' "${not_in_a[@]}"
Chris Down
fuente
Ejercicio: si intercambias Ay B, ¿es intersectionssiempre igual reordenar?
Gilles 'SO- deja de ser malvado'
@Gilles Si las matrices pueden contener elementos duplicados, no.
Chris Down
3

Para hacerlo, hay un enfoque bastante elegante y eficiente, uniqpero tendremos que eliminar duplicados de cada matriz, dejando solo elementos únicos. Si desea guardar duplicados, solo hay una forma "recorriendo ambas matrices y comparando".

Considere que tenemos dos matrices:

A=(vol-175a3b54 vol-382c477b vol-8c027acf vol-93d6fed0 vol-71600106 vol-79f7970e vol-e3d6a894 vol-d9d6a8ae vol-8dbbc2fa vol-98c2bbef vol-ae7ed9e3 vol-5540e618 vol-9e3bbed3 vol-993bbed4 vol-a83bbee5 vol-ff52deb2)
B=(vol-175a3b54 vol-e38d0c94 vol-2a19386a vol-b846c5cf vol-98c2bbef vol-7320102b vol-8f6226cc vol-27991850 vol-71600106 vol-615e1222)

En primer lugar, transformemos estas matrices en conjuntos. Lo haremos porque no es matemática intersección operación que se conoce como la intersección de conjuntos, y el conjunto es una colección de distintos objetos, diferentes o únicas . Para ser honesto, no sé qué es "intersección" si hablamos de listas o secuencias. Aunque podemos seleccionar una subsecuencia de la secuencia, pero esta operación (selección) tiene un significado ligeramente diferente.

Entonces, ¡vamos a transformar!

$ A=(echo ${A[@]} | sed 's/ /\n/g' | sort | uniq)
$ B=(echo ${B[@]} | sed 's/ /\n/g' | sort | uniq)
  1. Intersección:

    $ echo ${A[@]} ${B[@]} | sed 's/ /\n/g' | sort | uniq -d

    Si desea almacenar los elementos en otra matriz:

    $ intersection_set=$(echo ${A[@]} ${B[@]} | sed 's/ /\n/g' | sort | uniq -d)
    
    $ echo $intersection_set
    vol-175a3b54 vol-71600106 vol-98c2bbef

    uniq -dsignifica mostrar solo duplicados (creo que uniqes bastante rápido debido a su realización: supongo que se hace con la XORoperación).

  2. Obtenga la lista de elementos que aparecen By no están disponibles A, es decirB\A

    $ echo ${A[@]} ${B[@]} | sed 's/ /\n/g' | sort | uniq -d | xargs echo ${B[@]} | sed 's/ /\n/g' | sort | uniq -u

    O, al guardar en una variable:

    $ subtraction_set=$(echo ${A[@]} ${B[@]} | sed 's/ /\n/g' | sort | uniq -d | xargs echo ${B[@]} | sed 's/ /\n/g' | sort | uniq -u)
    
    $ echo $subtraction_set
    vol-27991850 vol-2a19386a vol-615e1222 vol-7320102b vol-8f6226cc vol-b846c5cf vol-e38d0c94

    Por lo tanto, al principio tenemos la intersección de Ay B(que es simplemente el conjunto de duplicados entre ellos), digamos que es A/\B, y luego utilizamos la operación de la intersección invertida de By A/\B(que simplemente son elementos únicos), por lo que obtenemos B\A = ! (B /\ (A/\B)).

PS uniqfue escrito por Richard M. Stallman y David MacKenzie.

kenichi
fuente
1

Ignorando la eficiencia, aquí hay un enfoque:

declare -a intersect
declare -a b_only
for bvol in "${B[@]}"
do
    in_both=""
    for avol in "${A[@]}"
    do
        [ "$bvol" = "$avol" ] && in_both=Yes
    done
    if [ "$in_both" ]
    then
        intersect+=("$bvol")
    else
        b_only+=("$bvol")
    fi
done
echo "intersection=${intersect[*]}"
echo "In B only=${b_only[@]}"
John1024
fuente
0

Mi puro estilo bash

Como estas variables contienen solo vol-XXXdonde XXXhay un número hexadecimal, hay una forma rápida de usar matrices bash

unset A B a b c i                    # Only usefull for re-testing...

A=(vol-175a3b54 vol-382c477b vol-8c027acf vol-93d6fed0 vol-71600106 vol-79f7970e
   vol-e3d6a894 vol-d9d6a8ae vol-8dbbc2fa vol-98c2bbef vol-ae7ed9e3 vol-5540e618
   vol-9e3bbed3 vol-993bbed4 vol-a83bbee5 vol-ff52deb2)
B=(vol-175a3b54 vol-e38d0c94 vol-2a19386a vol-b846c5cf vol-98c2bbef vol-7320102b
   vol-8f6226cc vol-27991850 vol-71600106 vol-615e1222)

for i in ${A[@]#vol-};do
    [ "${a[$((16#$i))]}" ] && echo Duplicate vol-$i in A
    ((a[$((16#$i))]++))
    ((c[$((16#$i))]++))
  done
for i in ${B[@]#vol-};do
    [ "${b[$((16#$i))]}" ] && echo Duplicate vol-$i in B
    ((b[$((16#$i))]++))
    [ "${c[$((16#$i))]}" ] && echo Present in A and B: vol-$i
    ((c[$((16#$i))]++))
  done

Esto debe generar:

Present in A and B vol-175a3b54
Present in A and B vol-98c2bbef
Present in A and B vol-71600106

En este estado, su entorno bash contiene:

set | grep ^c=
c=([391789396]="2" [664344656]="1" [706295914]="1" [942425979]="1" [1430316568]="1"
[1633554978]="1" [1902117126]="2" [1931481131]="1" [2046269198]="1" [2348972751]="1"
[2377892602]="1" [2405574348]="1" [2480340688]="1" [2562898927]="2" [2570829524]="1"
[2654715603]="1" [2822487781]="1" [2927548899]="1" [3091645903]="1" [3654723758]="1"
[3817671828]="1" [3822495892]="1" [4283621042]="1")

Entonces podrías:

for i in ${!b[@]};do
    [ ${c[$i]} -eq 1 ] &&
        printf "Present only in B: vol-%8x\n" $i
  done

Esto rendirá:

Present only in B: vol-27991850
Present only in B: vol-2a19386a
Present only in B: vol-615e1222
Present only in B: vol-7320102b
Present only in B: vol-8f6226cc
Present only in B: vol-b846c5cf
Present only in B: vol-e38d0c94

¡Pero esto está ordenado numéricamente! Si desea un pedido original, podría:

for i in ${B[@]#vol-};do
    [ ${c[((16#$i))]} -eq 1 ] && printf "Present in B only: vol-%s\n" $i
  done

Por lo tanto, muestra los vols en el mismo orden en que los envió:

Present in B only: vol-e38d0c94
Present in B only: vol-2a19386a
Present in B only: vol-b846c5cf
Present in B only: vol-7320102b
Present in B only: vol-8f6226cc
Present in B only: vol-27991850
Present in B only: vol-615e1222

o

for i in ${!a[@]};do
    [ ${c[$i]} -eq 1 ] && printf "Present only in A: vol-%8x\n" $i
  done

para mostrar solo en A :

Present only in A: vol-382c477b
Present only in A: vol-5540e618
Present only in A: vol-79f7970e
Present only in A: vol-8c027acf
Present only in A: vol-8dbbc2fa
Present only in A: vol-93d6fed0
Present only in A: vol-993bbed4
Present only in A: vol-9e3bbed3
Present only in A: vol-a83bbee5
Present only in A: vol-ae7ed9e3
Present only in A: vol-d9d6a8ae
Present only in A: vol-e3d6a894
Present only in A: vol-ff52deb2

o incluso:

for i in ${!b[@]};do
    [ ${c[$i]} -eq 2 ] && printf "Present in both A and B: vol-%8x\n" $i
  done

volverá a imprimir :

Present in both A and B: vol-175a3b54
Present in both A and B: vol-71600106
Present in both A and B: vol-98c2bbef
F. Hauri
fuente
Por supuesto, si las Duplicatelíneas son inútiles, simplemente se pueden descartar.
F. Hauri