Invertieren eines assoziativen Arrays

7

Angenommen, ich habe ein assoziatives Array in bash,

declare -A hash
hash=(
    ["foo"]=aa
    ["bar"]=bb
    ["baz"]=aa
    ["quux"]=bb
    ["wibble"]=cc
    ["wobble"]=aa
)

wo mir sowohl Schlüssel als auch Werte unbekannt sind (die tatsächlichen Daten werden aus externen Quellen gelesen).

Wie kann ich ein Array der Schlüssel erstellen, die demselben Wert entsprechen, damit ich dies in einer Schleife über alle eindeutigen Werte tun kann?

printf 'Value "%s" is present with the following keys: %s\n' "$value" "${keys[*]}"

und erhalten Sie die Ausgabe (nicht unbedingt in dieser Reihenfolge)

Value "aa" is present with the following keys: foo baz wobble
Value "bb" is present with the following keys: bar quux
Value "cc" is present with the following keys: wibble

Das wichtige Bit ist, dass die Schlüssel als separate Elemente im keysArray gespeichert sind und daher nicht aus einer Textzeichenfolge analysiert werden müssen.

Ich könnte so etwas tun

declare -A seen
seen=()
for value in "${hash[@]}"; do
    if [ -n "${seen[$value]}" ]; then
        continue
    fi

    keys=()
    for key in "${!hash[@]}"; do
        if [ "${hash[$key]}" = "$value" ]; then
            keys+=( "$key" )
        fi
    done

    printf 'Value "%s" is present with the following keys: %s\n' \
        "$value" "${keys[*]}"

    seen[$value]=1
done

Aber es scheint ein bisschen ineffizient mit dieser Doppelschleife.

Gibt es eine Array-Syntax, die ich verpasst habe bash?

Würde zshmir dies beispielsweise Zugriff auf leistungsfähigere Array-Manipulationswerkzeuge geben?

In Perl würde ich tun

my %hash = (
    'foo'    => 'aa',
    'bar'    => 'bb',
    'baz'    => 'aa',
    'quux'   => 'bb',
    'wibble' => 'cc',
    'wobble' => 'aa'
);

my %keys;
while ( my ( $key, $value ) = each(%hash) ) {
    push( @{ $keys{$value} }, $key );
}

foreach my $value ( keys(%keys) ) {
    printf( "Value \"%s\" is present with the following keys: %s\n",
        $value, join( " ", @{ $keys{$value} } ) );
}

Aber bashassoziative Arrays können keine Arrays enthalten ...

Ich würde mich auch für eine Old-School-Lösung interessieren, die möglicherweise eine Form der indirekten Indizierung verwendet (Erstellen einer Reihe von Indexarrays beim Lesen der Werte, die ich hashoben angegeben habe?). Es scheint, dass es einen Weg geben sollte, dies in linearer Zeit zu tun.

Kusalananda
quelle

Antworten:

9

zsh

Schlüsselwerte <=> umkehren

In zsh, wo die primäre Syntax zum Definieren eines Hashs hash=(k1 v1 k2 v2...)wie in ist perl(neuere Versionen unterstützen aus Gründen der Kompatibilität auch die umständliche ksh93 / bash-Syntax, jedoch mit Variationen beim Zitieren der Schlüssel).

keys=("${(@k)hash}")
values=("${(@v)hash}")

typeset -A reversed
reversed=("${(@)values:^keys}") # array zipping operator

oder mit einer Schleife:

for k v ("${(@kv}hash}") reversed[$v]=$k

Das @und doppelte Anführungszeichen dient dazu, leere Schlüssel und Werte beizubehalten (beachten Sie, dass bashassoziative Arrays keine leeren Schlüssel unterstützen). Da die Erweiterung von Elementen in assoziativen Arrays in keiner bestimmten Reihenfolge erfolgt, können Sie nicht sagen, welcher Schlüssel als Wert verwendet wird , wenn mehrere Elemente $hashdenselben Wert haben (was letztendlich ein Schlüssel ist $reversed) $reversed.

für deine Schleife

Sie würden das RHash-Index-Flag verwenden, um Elemente basierend auf dem Wert anstelle des Schlüssels zu erhalten, kombiniert mit efür eine genaue Übereinstimmung (im Gegensatz zum Platzhalter), und dann die Schlüssel für diese Elemente mit dem kParametererweiterungs-Flag abrufen:

for value ("${(@u)hash}")
  print -r "elements with '$value' as value: ${(@k)hash[(Re)$value]}"

Ihr Perl-Ansatz

zsh(im Gegensatz zu ksh93) unterstützt keine Arrays von Arrays, aber ihre Variablen können das NUL-Byte enthalten. Sie können dies also verwenden, um Elemente zu trennen, wenn die Elemente ansonsten keine NUL-Bytes enthalten, oder das ${(q)var}/ ${(Q)${(z)var}}zum Codieren / Decodieren einer Liste verwenden mit Zitieren.

typeset -A seen
for k v ("${(@kv)hash}")
  seen[$v]+=" ${(q)k}"

for k v ("${(@kv)seen}")
  print -r "elements with '$k' as value: ${(Q@)${(z)v}}"

ksh93

ksh93 war die erste Shell, die 1993 assoziative Arrays einführte. Die Syntax für die Zuweisung von Werten als Ganzes bedeutet, dass es sehr schwierig ist, dies programmgesteuert zu tun zsh, aber zumindest ist es in ksh93 etwas gerechtfertigt, da es ksh93komplexe verschachtelte Datenstrukturen unterstützt.

Insbesondere unterstützt ksh93 hier Arrays als Werte für Hash-Elemente, sodass Sie Folgendes tun können:

typeset -A seen
for k in "${!hash[@]}"; do
  seen[${hash[$k]}]+=("$k")
done

for k in "${!seen[@]}"; do
  print -r "elements with '$k' as value ${x[$k][@]}"
done

Bash

bash Jahrzehnte später wurde die Unterstützung für assoziative Arrays hinzugefügt, die ksh93-Syntax kopiert, jedoch nicht die anderen erweiterten Datenstrukturen, und es gibt keinen der erweiterten Parametererweiterungsoperatoren von zsh.

In bashkönnen Sie den im zsh erwähnten Ansatz für zitierte Listen mit printf %qoder mit neueren Versionen verwenden ${var@Q}.

typeset -A seen
for k in "${!hash[@]}"; do
  printf -v quoted_k %q "$k"
  seen[${hash[$k]}]+=" $quoted_k"
done

for k in "${!seen[@]}"; do
  eval "elements=(${seen[$k]})"
  echo -E "elements with '$k' as value: ${elements[@]}"
done

Wie bereits erwähnt, unterstützen bashassoziative Arrays den leeren Wert nicht als Schlüssel, sodass er nicht funktioniert, wenn einige der $hashWerte leer sind. Sie können die leere Zeichenfolge durch einen Platzhalter wie ersetzen <EMPTY>oder dem Schlüssel ein Zeichen voranstellen, das Sie später zur Anzeige entfernen würden.

Stéphane Chazelas
quelle
Nett. Sie haben einen Fehler im Bash-Beispiel: last seen(im Echo) sollte sein elements. Ich nehme jedoch an, dass jedes $ {Seen [$ k]} eine Zeichenfolge mit durch Leerzeichen getrennten Elementen ist, für die daher eine zusätzliche Analyse erforderlich ist, die das OP nicht wollte (?)
Ralph Rönnquist
3

Wie Sie sicher wissen, besteht der Stolperstein darin, den gesamten Wert eines indizierten Arrays abzurufen, wenn sein Name als Wert einer (anderen) Variablen angegeben wird. Ich könnte es nicht mit weniger tun, als ein Zwischenprodukt zu haben, dessen Wert formatiert wird, ${v[@]}und dann eval dafür verwenden. Also, hier ist dieser Ansatz:

declare -A keys
N=0 # counter for the index variables IX1, IX2, IX3, ...
for key in "${!hash[@]}"; do
    value="${hash[$key]}"
    if [ -z "${keys[$value]}" ] ; then N=$((N+1)) ; keys[$value]=IX$N ; fi
    index="${keys[$value]}" # 'index' is now name of index variable
    X="\${$index[@]}"
    eval "$index=( $X $key )" # adding next key to it
done

for value in "${!keys[@]}" ; do
    index=${keys[$value]}
    X="\${$index[@]}"
    printf "Value %s is present with the following keys: %s\n" \
       "$value" "$(eval echo "$X")"
done

Dies ist für Linux bash. Es schafft indizierte Arrays IX1, IX2usw., für die verschiedenen Werte trifft es auf und hält diese Namen in die keysassoziative Array für die Werte. Dies ${keys[$value]}ist also der Name des indizierten Arrays, das die Schlüssel für diesen Wert enthält. Dann Xwird die Variable "Zugriffsphrase" für die Sammlung von Werten eingerichtet, die eval echo "$X"die Übersetzung in diese Werte mit Leerzeichen ermöglicht. Wenn ein Wert beispielsweise ein Array indiziert hat IX2, ist Xdies die Zeichenfolge ${IX2[@]}.

Ich glaube, dass zshes ähnlich ist, Arrays von Arrays nicht zu unterstützen, daher würde es wahrscheinlich eine ähnliche Lösung erfordern. IMHO sind die Zugriffsphrasen in zshjedoch etwas klarer.

Ralph Rönnquist
quelle