Bashでピボットテーブルを作る話と再帰的な xargs

Bashでピボットテーブルを作る話

諸般の事情ででっかいテーブルからピボットテーブルを作りたい。
でっかいテーブルなのでメモリに全部は乗らない。
単純にピボットテーブルを作ろうとすると vector<vector<value>> みたいな構造が欲しくなるのでメモリに乗らないのはツラい。

ということで、一時ファイルを使いつつ、シェルスクリプトでピボットテーブルを作ることにした。
なお、それ、シェルスクリプトでやる必要あるの？という質問は締め切られております。

ソース: https://github.com/takei-yuya/pivot_table
(英語がおかしいのは仕様。PR歓迎)

ピボットテーブルって？

すんごく単純に説明すると

row	col	value
1	a	value_1a
1	b	value_2b
2	a	value_1a
2	b	value_2b

みたいな列指向(?)なテーブルから

row\col	a	b
1	value1a	value1b
2	value2a	value2b

みたいな行列テーブルを作ることらしい(伝聞)。

雑な説明なので、ピボットテーブルについて詳しく知りたいよ！という方は詳細はググってくだしあ。
実際には、数値を加算してみたり、平均取ってみたり、とかもあるようですが、今回は割愛。
(というかシェルスクリプトでやろうとすると複雑になりすぎる予感)

シェルスクリプトでやる方針

メモリに乗らないでっかいテーブル、という前提で、どうやってピボットテーブルを作るか、という方針。

ポイントとなるコマンドは paste(1) 。
これはGNU Coreutilsに入っているコマンドで、複数のファイルを横方向に連結するコマンド。
使い方はこんな

$ (echo 1; echo 2; echo 3) > file1
$ (echo a; echo b; echo c) > file2
$ cat file1
1
2
3
$ cat file2
a
b
c
$ paste file1 file2
1(タブ)a
2(タブ)b
3(タブ)c

ファイルは2つだけでなくて、複数とれる。

今回はこの paste(1) を使い、列ごとに分割したファイルをつくって、横方向にくっつけることを考えます。
つまり、

row	col	value
1	a	value_1a
1	b	value_2b
2	a	value_2a
2	b	value_2b

このテーブルから、列aだけを抜き出した

row	value of a
1	value_1a
2	value_2a

というテーブルと、列bだけを抜き出した

row	value of b
1	value_1b
2	value_2b

というテーブルを作って、これを横方向にがっちゃんこすると

row\col	a	b
1	value1a	value1b
2	value2a	value2b

これができる。

早速書いて見る。

まずは、列ごとにテーブルを分割したので、 sort(1) を使い、列でソートする。
ついでに、ヘッダを作る様に全列も取得しておく。

temp_dir="$(mktemp -d)"  # 作業用テンポラリディレクトリ
row_filed=1  # 行の値が入っているカラムのインデックス
col_field=2  # 列の値が入っているカラムのインデックス
val_field=3  # 値が入っているカラムのインデックス
delim=","  # とりあえず区切り文字はカンマで

cat "$@" \  # 入力は引数のファイルか標準入力
  | grep -v '^$' \  # 空行は無視
  | sort -t "${delim}" -k "${col_field}" -k "${row_field}" \  # 列でソート(ついでに第二ソートキーとして行でもソート)
  | tee "${temp_dir}/sorted" \  # ソート済みファイルを保存
  | cut -d "${delim}" -f "${col_field}" \  # cut(1) を使って列だけ取得
  | uniq > "${temp_dir}/cols"  # uniq(1) して重複のない列の値一覧を保存(列でソートしてあるので uniq(1) だけでok

これで列ごとに順番に並んだファイルができあがる。

row	col	value
1	a	value_1a
2	a	value_2a
:	a	:
N	a	value_Na
1	b	value_1b
2	b	value_2b
:	b	:
N	b	value_Nb
1	c	value_1c
2	c	value_2c
:	c	:
N	c	value_Nc

これを行の種類数( N )分の行数に分割すると各列用のテーブルができあがる。
行の種類数がほしいので、wc(1) でカウントして、 split(1) で分割

cut -d "${delim}" -f "${row_field}" "${temp_dir}/sorted" \  # 先ほどのファイルからcut(1)で行だけ取得して
  | sort -u > "${temp_dir}/rows"  # sort(1) で重複除去して保存

cut -d "${delim}" -f "${val_filed}" \  # あとでpasteするときに邪魔な値を入れないように値だけ抜き出して
  | split -l "$(wc -l < "${temp_dir}/rows")" - "${temp_dir}/col_"  # colごとにファイルを `split(1)` で分割

split(1) は指定された行数/ファイルサイズなどごとに、ファイルを分割して、指定されたプレフィックスを使い、 ${prefix}aa ${prefix}ab ${prefix}ac ... というファイルを作ってくれる。
ファイルグロブ(*)の展開順でファイルを作ってくれるので便利。

これで、各列ごとに、行でソートされた値のテーブル群、つまり

value of a
value_1a
value_2a
:
value_Na

value of b
value_1b
value_2b
:
value_Nb

value of c
value_1c
value_2c
:
value_Nc

こんなファイル群ができあがったので、あとは paste(1) するだけ。

paste -d "${delim}" "${temp_dir}/col_"*  # がっちゃんこ

こうなる

value of a	value of b	value of c
value_1a	value_1b	value_1c
value_2a	value_2b	value_2c
:	:	:
value_Na	value_Nb	value_Nc

すごく楽ちん。

欠損値どうする問題

さて、先ほどのソースだと split(1) で行数等分してたけど、欠損値、値抜けがあると列ごとのテーブルのサイズがズレてしまう。
つまりそのまま split(1) が使えない。

困った。

本当に困った。

どうにもこうにも綺麗な方法が思い浮かばなかったので泥臭く行くことにした。
方針としては、先に欠損値をなにかしらの値で埋めてしまって、等行数で区切れるようにする。

ここでのポイントとなるコマンドは join(1) 。
paste(1) 同様に横方向に連結するコマンド。ただし、連結するさいに、共通の値を持つカラムを使って行の対応を取ってくれる。
こんな

$ (echo -e "1\ta"; echo -e "2\tb"; echo -e "3\tc") > file1
$ (echo -e "1\tA"; echo -e "3\tC"; echo -e "5\tE") > file2
$ cat file1
1(タブ)a
2(タブ)b
3(タブ)c
$ cat file2
1(タブ)A
3(タブ)C
5(タブ)E
$ join file1 file2
1 a A
3 c C

デフォルトだと一番左のカラムに共通の値が入っていると見なして、二つのファイルで共通の値を持つ行ごとに横方向に連結する。
-a NUM(1 or 2) オプションをつけると、 共通行だけでなく、どちらか片方(1つめのファイルか2つめのファイル)の値を常に出力するようになる。

$ join -a1 file1 file2  # 1つめのファイルの中身は常に表示
1 a A
2 b
3 c C
$ # 二行目は1つめのファイルの値だけ出ている

さらに -o FORMAT オプションを付けると表示する内容を制御できる。 FORMAT はカンマかスペース区切りで、 NUM(1 or 2).COLUMN でどっちのファイルのどのカラムを表示するか、を指定する

$ join -a1 -o "2.2" file1 file2  # 2つめのファイルの第二カラムだけを表示する
A

C
$ # 二行目は2つめのファイルにない値(欠損値)なので空行が表示される

$ join -a1 -o "2.2" -e X file1 file2 # -e オプションを使うと欠損値を別の値で埋められる
A
X
C

この join(1) を使って、テーブル上で欠損している値を補ってみる。
つまり、

row	col	value
1	a	value_1a
2	a	value_2a
5	a	value_5a
1	b	value_1b
4	b	value_4b
1	c	value_1c
3	c	value_3c
5	c	value_5c

の様なrowとcolの全ての組み合わせがないテーブルと、

row	col	dummy
1	a	-
2	a	-
3	a	-
4	a	-
5	a	-
1	b	-
2	b	-
3	b	-
4	b	-
5	b	-
1	c	-
2	c	-
3	c	-
4	c	-
5	c	-

の様な全部のrow/colの組み合わせがそろったテーブルを join(1) して

row	col	value
1	a	value_1a
2	a	value_2a
3	a	-
4	a	-
5	a	value_5a
1	b	value_1b
2	b	-
3	b	-
4	b	value_4b
5	b	-
1	c	value_1c
2	c	-
3	c	value_3c
4	c	-
5	c	value_5c

こんなテーブルを作る。
そうすればあとは行数で等分することができる。
(paste(1) 的には別に dummy カラムはいらなかったりする)

ただ、 paste(1) は共通カラムを一つしか指定できない。
一方で今は、 row と col の両方を共通カラムとして使いたい。
仕方が無いので、 row と col を連結して、そのカラムを join(1) の共通カラムとして指定する。
こんな感じ

delim2=$'\v'  # そのままrowとcolをくっつけるのもナンなので垂直タブあたりを区切り文字に使ってみる

# row/colが全部そろったダミーテーブルをつくる
while read -d $'\n' col; do
  while read -d $'\n' row; do
    printf "%s%s%s\n" "${col}" "${delim2}" "${row}"  # delim2でくっつけて一つのカラムにする
  done < "${temp_dir}/rows"
done < "${temp_dir}/cols" > "${temp_dir}/indexes"

# rowとcolをdelim2でくっつけて一つのカラムにしつつ、第二カラムに値をいれる
paste -d "${delim2}${delim}" \  # paste(1) の -d は複数の区切り文字を順番に指定できる。地味に便利
  <(cut -d "${delim}" -f "${col_field}" "${temp_dir}/sorted") \
  <(cut -d "${delim}" -f "${row_field}" "${temp_dir}/sorted") \
  <(cut -d "${delim}" -f "${val_field}" "${temp_dir}/sorted") > "${temp_dir}/values"

# ダミーテーブルと値のテーブルをくっつけて、値のカラムだけ表示する
join -t "${delim}" "${temp_dir}/indexes" "${temp_dir}/values" -a1 -o "2.2" \
  | split -l "$(wc -l < "${temp_dir}/rows")" - "${temp_dir}/col_"  # 等分する(前章と同じ)

paste -d "${delim}" "${temp_dir}/col_"*  # がっちゃんこ

うーん。泥臭い。
素敵な方法あったら教えてください。

モーレツな量の列があったら？

先ほどのコードの最後、 paste -d "${delim}" "${temp_dir}/col_"* この部分。
列数が膨大な量あると実は困る。
シェルは引数の最大長が決まっていて、システム構成変数 ARG_MAX を越える長さの引数を渡せない。
いわゆる「引数リストが長すぎます(Argument list too long)」というエラーメッセージのアレ。
手元のMacだと262144という値になっている。

$ getconf ARG_MAX
262144

26万もあれば十分じゃないか、と思うかもしれないけど、これは引数の個数、ではなくて引数の総byte数(引数の区切り文字分を含む)。

今回の場合、 ${temp_dir}/col_"* を渡している。
Macの場合引数なしの mktemp(1) は /var/folders/fs/xxxxxxxxxxxxxxxxxxxxxxxxxxxxx/T/tmp.XXXXXXXXXXX みたいなパスを返すので、引数区切り文字や split(1) の生成するパスを含めると、1ファイルあたりだいたい72bytes。262144 を 72 で割って 3640 。
列数3640。ちょっと心許ない……。

この辺を良きに計らってくれるのが xargs(1) コマンド。
ARG_MAXに引っかからないように引数の個数を抑えて、代わりに複数回コマンドを実行してくれる。
とても頼もしい存在なのだけど、今回はそのままでは使えない……。
というのも xargs(1) は複数のコマンドの結果を「縦に」並べてしまうのだ。
つまり

$ (echo 1; echo a; echo A) > file1
$ (echo 2; echo b; echo B) > file2
$ (echo 3; echo c; echo C) > file3
$ (echo 4; echo d; echo D) > file4
$ paste file1 file2 file3 file4  # 横に連結したい
1(タブ)2(タブ)3(タブ)4
a(タブ)b(タブ)c(タブ)d
A(タブ)B(タブ)C(タブ)D
$ echo file{1,2,3,4} | xargs -n2 paste  # 引数を2個ずつ実行する
1(タブ)2
a(タブ)b
A(タブ)B
3(タブ)4
c(タブ)d
C(タブ)D
$ echo file{1,2,3,4} | xargs -t -n2 paste  # 実行されたコマンドを表示してみる
paste file1 file2
1(タブ)2
a(タブ)b
A(タブ)B
paste file3 file4
3(タブ)4
c(タブ)d
C(タブ)D

ARG_MAX分引数を並べるのはさすがに骨なので -n NUM で引数の数を指定してみました。
で、結果ですが、まぁ、ですよねー、という感じ。

この xargs(1) の各結果をそれぞれまた paste(1) に投げ込みたい。
つまり、再帰的に xargs(1) するようなコマンド/オプションが欲しい。

のだけど、軽く探した結果見つからない。

仕方がないのであきらめて書きましょう

再帰的な xargs

ということで、再帰的な xargs(1) が欲しい。
イメージ的には

COMMAND arg1 arg2 ...(めっちゃ長い)... argN

を

COMMAND \
  <(COMMAND arg1 arg2 ...(そこそこ)... argN_1) \
  <(COMMAND argN_1 ...(そこそこ)... argN_2) \
  ...
  <(COMMAND argN_k ...(そこそこ)... argN)

みたいな感じにするコマンドが欲しい。( <(command) はbash拡張記法)

で、別にそんな難しくなくて、方針としては、 xargs(1) に COMMAND の代わりに、 COMMAND を実行してその結果を格納したファイル名を出力するラッパーコマンド(?)を渡してあげればいい。
その結果のファイルリストをもう一回 xargs に投げて、また結果のファイルリストを受け取って、をファイルが1個になるまで繰り返せばok。

実装としてはこんな

mode=hoge  # -x オプションついていたらCOMMANDのラッパーモード(手抜き)
temp_dir="fuga"  # 作業用テンポラリ 

if [ "${mode}" == "exec" ]; then
  # ラッパーコマンドモード。単に実行して結果をファイルに格納してファイル名を表示するだけ
  temp_file="$(mktemp "${temp_dir}/out.XXXXXXXX")"
  "${@}" > ${temp_file}
  echo "${temp_file}"
else
  # 再帰するxargsモード
  temp_file="$(mktemp "${temp_dir}/list.XXXXXXXX")"  # 結果ファイルリストを保存するファイル
  xargs -- $0 -x -t "${temp_dir}" "${@}" > "${temp_file}"  # xargsにラッパーコマンドを渡す
  nfiles=$(wc -l < "${temp_file}")  # xargsの吐いたファイル数をカウント
  if [ "${nfiles}" -gt 1 ]; then
    # 出力されたファイルがまだ複数ある = まだまだファイルをマージする必要あり→再帰する
    cat "${temp_file}" | $0 -t "${temp_dir}" "${num+-n ${num}}" "${@}"
  else
    # 最後の一個のファイル→出力する
    cat "$(cat "${temp_file}")"
  fi
fi

スクリプト前半は適当。詳細はgithubに上げてあるコードを参照してくだしあ。
あとラッパーと再帰xargs本体を同じスクリプトでやってますが、当然分けてもok。

paste(1) を膨大な引数に対して使う時に便利なのですが、一般的には交換法則が成り立つコマンドならなんでもokです。
つまり、
COMMAND <(COMMAND file1 file2) file3 と
COMMAND file1 <(COMMAND file2 file3) の結果が一致するようなコマンドであればなんでもokというわけです。 ( sort -m とか？ )

まぁ、ARG_MAXに引っかかるようなコトはあまりないとは思いますが……。

そんなわけで何の役に立つのか分からないエントリをぶん投げて :wq

補足 (組み込みコマンドとARG_MAX)

ちなみにbashの組み込みコマンドはARG_MAXの影響を受けない。
ので echo "${temp_dir}/col_"* は問題ない。

ただ、これはあくまで組み込みコマンドだけ。
なので、組み込みでない /bin/echo は当然 ARG_MAX の影響を受ける。

なのでこんなことが起こる。

$ /bin/echo $(yes | head -c `getconf ARG_MAX`) >/dev/null
bash: /bin/echo: Argument list too long
$ echo $(yes | head -c `getconf ARG_MAX`) >/dev/null
$ echo $?
0

echo != /bin/echo