2つのkshまたはbashアレイ間で共通の要素を探す

Question

私はKornシェルスクリプトを書いています。私は2つの配列（例えば、arr1とarr2）を持っていて、両方とも文字列を含んでいるので、arr1からどの要素が（全体の文字列または部分文字列として）arr2に存在するかチェックする必要があります。最も直感的な解決策は、forループネスト、およびarr1からの各要素は次のように（grepを通して）arr2に見出すことができるかどうかをチェックしたれる：そうネストされた実行、

for arr1Element in ${arr1[*]}; do 
    for arr2Element in ${arr2[*]}; do 
     # using grep to check if arr1Element is present in arr2Element 
     echo $arr2Element | grep $arr1Element 
    done 
done 

問題がarr2が約3000の要素を有することですループには長い時間がかかります。私はBashでこれを行うより良い方法があるのだろうかと思います。

もし私がJavaでこれをやっていたのであれば、配列の要素のハッシュを計算してから、別の配列のハッシュを探すことができましたが、Bashにはこれは（私がBashでハッシュ計算関数を書こうとしていない限り）。

提案がありますか？

Answer 1

バージョン4.0バッシュは、連想配列を持っているので：

$ declare -A elements 
$ elements[hello]=world 
$ echo ${elements[hello]} 
world 

あなたが希望するJava地図と同じ方法で、これを使用することができます。部分文字列の扱い

declare -A map 
for el in "${arr1[@]}"; do 
    map[$el]="x" 
done 

for el in "${arr2[@]}"; do 
    if [ -n "${map[$el]}" ] ; then 
     echo "${el}" 
    fi 
done 

は完全に、より重い問題であり、すでに使用しているブルートフォースアルゴリズムの短い任意の言語で挑戦、だろう。文字シーケンスのバイナリツリーインデックスを構築することはできますが、私は試していませんそのはBashで！

printf '%s\n' "${arr2[@]}" \ 
    | grep -o -F "$(printf '%s\n' "${arr1[@]}") 

、それが適当と考えるようgrep最適化をしてみましょう：あなたはgrepを使用してOKだ、とあなたは部分文字列だけでなく、完全な文字列を一致させたいために、一つのアプローチは、書くことですので

Answer 2

。

Answer 3

BashFAQ #36は、commでbashの集合算術（和集合、非結合集合など）を行うことを説明しています。以下はARR1とARR2の両方の項目ごとにラインを放出する、あなたの値はリテラル改行を含めることはできませんと仮定

：

comm -12 <(printf '%s\n' "${arr1[@]}" | sort -u) \ 
     <(printf '%s\n' "${arr2[@]}" | sort -u) 

あなたの配列があらかじめソートされている場合、あなたはsort Sを削除することができます（これは、grepベースのアプローチよりも、大規模なアレイでは非常にメモリと時間効率が非常に高くなります）。

Answer 4

ここbash/awk考えです：

# some sample arrays 

$ arr1=(my first string "hello wolrd") 
$ arr2=(my last stringbean strings "well, hello world!) 

# break array elements into separate lines 

$ printf '%s\n' "${arr1[@]}" 
my 
first 
string 
hello world 

$ printf '%s\n' "${arr2[@]}" 
my 
last 
stringbean 
strings 
well, hello world! 

# use the 'printf' command output as input to our awk command 

$ awk ' 
NR==FNR { a[NR]=$0 ; next } 
{ for (i in a) 
     if ($0 ~ a[i]) print "array1 string {"a[i]"} is a substring of array2 string {"$0"}" } 
' <(printf '%s\n' "${arr1[@]}") \ 
    <(printf '%s\n' "${arr2[@]}") 

array1 string {my} is a substring of array2 string {my} 
array1 string {string} is a substring of array2 string {stringbean} 
array1 string {string} is a substring of array2 string {strings} 
array1 string {hello world} is a substring of array2 string {well, hello world!} 

• NR==FNR：のみファイル＃1のために： ''
• nextという名前awkの配列に格納する要素：プロセスの次の行は、ファイル＃1に。この時点で、awkスクリプトの残りはファイル＃1では無視されます。ファイル＃2の各行について...
• for (i in a)：配列 'a'の各インデックスについて...
• if ($0 ~ a[i])：[i]は、ファイル＃2から現在の行（$ 0）のサブであるかどうかを確認し、もしそうなら...
• print "array1...：試合

---

についての出力情報以下のデータを使用して、テストの実行：

arr1 == 3300 elements 
arr2 == 500 elements 

全てarr2要素がarr1（すなわち、500試合）にサブ/パターンマッチを有する、合計ティム実行するeは〜27秒です...そのため、配列を繰り返しループすることは有料です。

明らかに（？）、正確な文字列一致のために

• ...の繰り返しアクションの量を減らす必要があるチャールズ・ダフィーによってcommソリューションが理にかなっている（それがに設定された同じ500分の3300テストに対して実行されますサブ/ PATTのため、私は約5秒で実行するegrepソリューションを得ることができた部分文字列/パターンマッチのために約0.5秒）
• （私の他の答え/ポストを参照してください）

Answer 5

egrepソリューションERNマッチング...

egrep -f <(printf '.*%s.*\n' "${arr1[@]}") \ 
     <(printf '%s\n'  "${arr2[@]}") 

• egrep -f：この場合...
• <(printf '.*%s.*\n' "${arr1[@]}")ある、-fで指定されたファイルから検索するパターンを取る：行あたり1つのパターンにarr1要素を変換し、接頭辞と接尾辞
• <(printf '%s\n' "${arr2[@]}")のための正規表現ワイルドカード文字（*）を追加：行ごとに1列にarr2要素を変換

以下のように設定されたサンプルデータに対して実行すると

：

arr1 == 3300 elements 
arr2 == 500 elements 

... 500試合で、総実行時間は約5秒です。 egrepで行われている繰り返し処理のビットはまだありますが、私の他の回答（bash/awk）に見られるように悪くはありません。もちろん、反復処理を排除した速いcommソリューションではありません。