Bashの配列で集合演算

まずは結論

Bashの配列で、SQLのUNION、INTERSECT、MINUS (PostgreSQLなどではEXCEPT) にあたる集合演算をしたい。つまり、和集合、積集合、差集合を取りたい。

自分的最適解は今のところこれ。ただし、配列の要素に空白類を含まない場合に限る。

union() { printf '%s\n' $@ | sort -u; }
intersect() { printf '%s\n' $@ | sort | uniq -d; }
minus() { (printf '%s\n' $@ | sort -u; printf '%s\n' $2) | sort | uniq -u; }

使い方はこう。

array1=(aa bb)
array2=(bb cc)
echo $(union "${array1[*]}" "${array2[*]}")      # => aa bb cc
echo $(intersect "${array1[*]}" "${array2[*]}")  # => bb
echo $(minus "${array1[*]}" "${array2[*]}")      # => aa

説明

関数の定義

関数の書き方は3種類あるが、function をつけない#1の書き方が最もシンプルで互換性が高い。

union() { ... }           #1 functionをつけない
function union { ... }    #2 functionをつけて、()をつけない
function union() { ... }  #3 functionをつけて、()もつける

関数を1行で書くときは、定義内容の最終行にもセミコロンをつける。でないと、syntax error になる。

printfコマンド

printf は、要は変数のフォーマットができる echo。

echo も printf も、内部コマンド (Bashのビルトインコマンド) と外部コマンドがある。外部コマンドのパス (/bin/printf とか) を指定しない限り、内部コマンドが使われるはず。余分なプロセスを生成しない分、内部コマンドの方が速い。

printf の第1引数はフォーマット指定文字列で、%s が後ろの変数を文字列として嵌め込むプレースホルダ。 \n は改行文字 (LF)。 Macのデフォルトでは、確かキーボードの ￥ を押すと円記号 (U+00A5) が入力される。バックスラッシュ (U+005C) を入力するには Option+￥。 Ubuntu Desktop では、JISキーボードの ￥ を押すと 0xC2A5 が入力された (なんで?)。バックスラッシュ (U+005C) を入力するには ＼ を押す。 WindowsのJISキーボードでは、￥ でも ＼ でも同じ。

コマンドとしての printf は、第2引数以降の数がプレースホルダより多ければ、引数の数分プレースホルダを繰り返してくれる。例えば、こう書くと、

printf '%s %s\n' aa bb cc dd ee

こうなる。

aa bb
cc dd
ee 

$@

関数の中の $@ は、その関数に渡された引数全部に展開される。類似の変数に $* もあって、こちらは引数全部が1個の文字列として展開される。今回は配列要素が空白類を含まない前提で、$@ をダブルクォートで囲んでもいないので、$* と書いても結果は同じになる (結局、全引数が空白で再分割されるので)。

union関数 (和集合)

union() { printf '%s\n' $@ | sort -u; }
array1=(aa bb)
array2=(bb cc)
echo $(union "${array1[*]}" "${array2[*]}")  # => aa bb cc

union 関数内の $@ は、引数で渡された2個の配列の全要素 (aa bb bb cc) に展開される。これが printf '%s\n' により、1要素1行の

aa
bb
bb
cc

に変換される。

sort -u は sort | uniq と同じ意味で、重複行が1行にまとめられる。最終的に、第1配列の要素と第2配列の要素の「少なくともどちらか片方にある要素」(aa bb cc)の集合になる。和集合である。

以下は union を呼び出す側の話。

array1 のような配列の宣言では、= の前後に空白を入れてはいけない。 ( ... ) の中に、要素を空白類で区切って書く。

${array1[*]} は、全要素を、空白区切りの1つの文字列 ("aa bb") に展開する。ちなみに、{ ... }をつけずに $array1[*] とすると、$array1 の部分だけが最初の要素 (aa) に展開されて、aa[*] になってしまう。類似のものに ${array1[@]} もあって、こちらは配列の各要素が独立した文字列として展開される ("aa" "bb")。今回は配列要素が空白類を含まない前提で、かつ、(後述するように) 要素が「1行か2行か」で重複の有無を判定しているため、union と intersect は、"${array1[*]}" "${array2[*]}" で呼び出しても "${array1[@]}" "${array2[@]}" で呼び出しても結果は同じ (各要素がどっちの配列に由来するは関係ないので)。一方、後述する minus では $2 を使っているために、必ず "${array1[*]}" "${array2[*]}" で呼び出さなければならない。

$( ... ) は、... をコマンドとして実行した結果の文字列に置き換わる (コマンド置換)。 $( ... ) の代わりに、コマンドをバッククォートで囲んでも意味は同じだが、$( ... ) の方が互換性は高い。

echo の引数を " ... " で囲んでいないため、関数が出力した空白類は、改行文字も含めて空白1個に置き換わっている。そのため、結果が1行で表示されている。

intersect関数 (積集合)

intersect() { printf '%s\n' $@ | sort | uniq -d; }
array1=(aa bb)
array2=(bb cc)
echo $(intersect "${array1[*]}" "${array2[*]}")  # => bb

union との違いは、sort -u が sort | uniq -d になっているだけ。 uniq の -d (--repeated) は、重複がある行のみを出力するオプション。 2回登場する要素というのは、第1配列と第2配列の両方に存在する要素なので、最終的に「両方ともにある要素」(bb) の集合になる。積集合である。

minus関数 (差集合)

minus() { (printf '%s\n' $@ | sort -u; printf '%s\n' $2) | sort | uniq -u; }
array1=(aa bb)
array2=(bb cc)
echo $(minus "${array1[*]}" "${array2[*]}") # => aa

差集合 (第1配列にしかない要素の集合) は、まず第1配列の要素と第2配列の要素の和集合を作り、そこから第2配列の要素を除去する (排他的論理和を取る) ことで得られる。したがって、前半部分の printf '%s\n' $@ | sort -u は union と同じ。

その末尾に、printf '%s\n' $2 で、第2配列の要素をもういちど追加する。これで、第2配列の要素だけが2行登場する状態になる。ここまでを ( ... ) で囲んでいるのは、前半と後半の出力を、サブシェルによりひとつの標準出力にまとめるため。

sort | uniq -u の -u (--unique) は、ユニークな行、つまり1回しか登場しない行だけを残すオプション (sort の -u と混同しないように。uniq のオプションですから)。1回だけ登場する要素というのは、「第1配列だけにある要素」(aa) の集合になる。差集合である。

minus 内では $2 を使っているので、minus を呼び出す側が渡す引数は、必ず "${array1[*]}" "${array2[*]}" でなければならない。ここをもし "${array1[@]}" "${array2[@]}" にしてしまったり、あるいはダブルクォートを外してしまったりすると、呼ばれた minus 関数側で、どこまでが第1配列の要素で、どこからが第2配列の要素か判別できなくなってしまう。その結果、上記の例では、minus 内の $2 に bb が入ってしまい、期待した結果が得られない。

おわりに

この実装は、ほとんど参考資料そのまんま。最初、こんなシンプルな記述で集合演算が実装できる理屈が分からず、いろいろ調べたり試したりした。その結果を、あとで思い出せるようにメモしてみた。

※参考資料

※バージョンメモ

GNU bash, version 5.2.37(1)-release (x86_64-pc-linux-gnu)