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に入っているコマンドで、複数のファイルを横方向に連結するコマンド。
使い方はこんな

```console
$ (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)` を使い、列でソートする。
ついでに、ヘッダを作る様に全列も取得しておく。

```bash
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)` で分割

```bash
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)` するだけ。

```bash
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)` 同様に横方向に連結するコマンド。ただし、連結するさいに、共通の値を持つカラムを使って行の対応を取ってくれる。
こんな

```console
$ (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つめのファイル)の値を常に出力するようになる。

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

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

```console
$ 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)` の共通カラムとして指定する。
こんな感じ

```bash
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という値になっている。

```console
$ 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)` は複数のコマンドの結果を「縦に」並べてしまうのだ。
つまり

```console
$ (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。


実装としてはこんな

```bash
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` の影響を受ける。

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

```console
$ /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`**