sqlplot で実験から tex まで

# 概要

実装の品質を実際に測るため、実験を走らせているものです。
しかし、その実験から出た指標データを上手く集めて、理解できやすい図・テーブルで表せることは手動的に面倒です。
指標をスプレッドシートに挿入する研究者はまだ多いと思われています。
[matplotlib](https://matplotlib.org/)・[plotly](https://plotly.com/) といった色々なデータから図を作るソフトがありますが、
そのソフトを早速に使うことができないし、研究者に大切に扱われる tex フォマットになかなか対応できません。
簡単なコマンドで自動的に実験のデータから `tex` までの方法は [sqlplot](https://github.com/koeppl/sqlplot) です。
`sqlplot` は `tex` ファイルの中に特徴な `sql` コマンドに基づいて自動的に図・テーブルを作ることができます。
この記事で、`sqlplot` を提案したいと思います。

## sqlplot というのは

`sqlplot` は python 言語で作られた道具です。
実験のデータに基づいて内部メモリー `sqlite` のデータベースを組み合わせて、`tex` ファイルの中に書いてある特徴なコマンドで図・テーブルを作ります。
いろいろなコマンドがありますが、 python で作られたお掛けで、自分で新しいコマンドを追加しやすいです。

## データのフォマット

実験しながら、ただのテキストファイルで測ったデータを置いて、
`sqlplot` をそのファイルを読ませることができます。
読みながら、`RESULT` というキーワードから初める行のみ気になります。
`RESULT`はキーと値から組み合わせるペア列が従います。
その行のシンタックスはこれです。

```
RESULT key1=value1 key2=value2 ...
```

つまり、キーと値のペアーは`=`で繋いで、各のペアーは空文字で区切ってあります。


# 例えば： ソートアルゴリズム

簡単な例で `sqlplot` の使い方を説明したいと思います。
そのために、`python` で実装されたバブルソートと挿入ソートといった素朴のスートアルゴリズムの速さを測りましょう。
バブルソートと挿入ソートと、どちらも $O(n^2)$ 最悪計算時間で動作しますが、
実際的に、どんなデータサイズでどのアルゴリズムの方が速いという質問の解を以下に解析しましょう。

## python コード

まず、バブルソートの実装を作りましょう：

```python
def bubble(arr):
    for i in range(len(arr)-1):
        for j in range(0, len(arr)-i-1): 
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
```

ただし `arr` はソートしたい数字配列です。
次は挿入ソートです：

```python
def selection(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
```

実験からデータを作るために、以下の関数を定義しましょう。
その関数は上で定義されたソート関数の中に一つかつその関数のネームを入力に対して取ります。

```python
import time

def measure(fn, fnlabel):
    start = time.process_time()
    sortedliste = fn(liste)
    end = time.process_time()
    print("RESULT time={} algo={} size={}".format(end - start, fnlabel, len(liste)))
    return sortedliste
```

この `print` コマンドは `sqlplot` が読めるフォマットで時間と入力のサイズを出力します。
残ったコードは `main` 関数です。
ここで、各のサイズ `problemsize` に対して、1 から `problemsize` までの数字を `liste` というリストに保存して、 `liste`　を混ぜて、 `measure` を各のソートアルゴリズムに対して呼びます。

```python
import random

for problemsize in [10, 100, 1000, 5000]:
	liste = list(range(problemsize))
	random.seed(a=0)
	random.shuffle(liste)
	measure(selection, "selection")
	measure(bubble, "bubble")
```

そのプログラムを作動したら、以下のような入力が出るはずです。

```
RESULT time=9.489000000001413e-06 algo=selection size=10
RESULT time=7.481999999996158e-06 algo=bubble size=10
RESULT time=0.0002442059999999968 algo=selection size=100
RESULT time=0.0002923949999999939 algo=bubble size=100
RESULT time=0.023890221999999996 algo=selection size=1000
RESULT time=0.028448002999999993 algo=bubble size=1000
RESULT time=0.5738962959999999 algo=selection size=5000
RESULT time=0.7924896020000001 algo=bubble size=5000
```

# 基本的な tex コード

ここから、集めたデータに基づいて `tex` の図を作りましょう。
まずは、データを `sort.txt` というファイルに保存します。
つぎは、この tex ファイルを置きましょう。

```tex
%% IMPORT-DATA sort sort.txt

\documentclass{article}
\usepackage{tikz}
\usepackage{pgfplots}
\begin{document}

\begin{tikzpicture}
\begin{axis}
%% MULTIPLOT(algo) SELECT size AS x, time as y, MULTIPLOT FROM sort
%% GROUP BY algo,x

\end{axis}
\end{tikzpicture}
\end{document}
```

`sqlplot` のコマンドは `%%` から初める行で書くべきです。
最小のコマンドは `%% IMPORT-DATA sort sort.txt` です。
そのコマンドは、 `sort.txt` の `RESULT` 行の基づいて、データベーステーブル `sort` を作ります。
（以上に述べりましたが、詳しくことに、`sqlplot` は`tex` ファイルを読みながら、そのデータベースを内部メモリーで組み合わせますが、`tex` ファイルを読破した後で、その組み合わせたデータベースを消しします。）
次のコマンドは `MULTIPLOT` です。
`MULTIPLOT` は複数の測りたいものをプロットします。
ここで、その複数のものは `algo` というキーがあるデータです。
各の `algo`のタプルを集めて、タプルのサイズを $x$ 軸とタプルの時間を $y$ 軸に映します。
`sqlplot.py` を今作った `tex` ファイルに応用すると、この出力が出て来ます：

```tex
%% IMPORT-DATA sort sort.txt

\documentclass{article}
\usepackage{tikz}
\usepackage{pgfplots}
\begin{document}

\begin{tikzpicture}
\begin{axis}
%% MULTIPLOT(algo) SELECT size AS x, time as y, MULTIPLOT FROM sort
%% GROUP BY algo,x
\pgfplotsset{cycle list shift=1} % 1
\addplot coordinates{(10, 7.236000000000742e-06) (100, 0.0002994150000000008) (1000, 0.028540775999999997) (5000, 0.8158583169999999)};                                      
\addlegendentry{bubble};
\pgfplotsset{cycle list shift=1} % 2
\addplot coordinates{(10, 9.677999999999076e-06) (100, 0.0002550619999999969) (1000, 0.025769473999999997) (5000, 0.5913769769999999)};                                      
\addlegendentry{selection};

\end{axis}
\end{tikzpicture}
\end{document}
```

この`tex`ファイルをコンパイルすると、以下の図を求めることができます。


![始めのプロット](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315858/2b49c058-866d-d528-2894-346f5e7a7f02.png)

## 工夫した tex

以上のプロットを見えて、不足なものが見た目に現れます：
 
 - 測った $x$ 値は 10べき乗のスケールで飛ばしましたから、最初の測りは見にくいです。 $x$ 値を対数的なスケールでに変化したいです。
   解法を二つ提案します。 
  - tex の解法は `\begin{axis}[xmode=log]` に変化することです。
  - sql の解法は `SELECT size AS x` を `SELECT LOG(2,size) AS x` に変換することです。
 - 自動的な作ったプロットコマンドを他のファイルに保存できます。
   例えば、 `easysort.tex` にそのコマンドを保存しましょう：

```tex
%% MULTIPLOT(algo) SELECT LOG(2,size) AS x, AVG(time) as y, MULTIPLOT FROM sort
%% GROUP BY algo,x
%% CONFIG file=easysort.tex

\input{easysort.tex}
```

次の不服なものは、今の実験は時間をただ一回のみ測ったことです。
複数時間の平均数値を `sqlplot` で計算させることができます。
そのために、 ただ `time as y` を `AVG(time) as y` に変化する必要です。

最後に、高々 1000 のサイズに興味があれば、
もっと大きいなサイズについてデータを `sort.txt` で消さずに、
`WHERE size <= 1000` を SQL コマンドに追加しても大丈夫です。
結局、全部の `tex` ファイルはこの形になりました：

```tex
%% IMPORT-DATA sort sort.txt

\documentclass{article}
\usepackage{tikz}
\usepackage{pgfplots}
\begin{document}

\begin{tikzpicture}
\begin{axis}
%% MULTIPLOT(algo) SELECT LOG(2,size) AS x, AVG(LOG(2,time)) as y, MULTIPLOT FROM sort
%% WHERE size <= 1000
%% GROUP BY algo,x
%% CONFIG file=easysort.tex

\input{easysort.tex}
\end{axis}
\end{tikzpicture}
\end{document}
```

ただし、時間も対数的にプロットされました。
これで、小さいサイズの結果が読みやすくなりました：

![工夫したプロット](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/315858/02aa7c0e-48d4-3ad4-a4d4-b6ee2cdf7feb.png)


作った図によると、
小さいデータなら、バッブルソートは一番速いけど、データが大きくなるとどんどん遅くなります。
これで何かを習うべきなら、
たくさん小さい配列をソートしたいとき、工夫されたソートアルゴリズムより、素朴のバッブルソートのほうが速い可能性があるということです。

## 故障・debug

`sqlplot` はおかしく動作するとき、`-l DEBUG` のパラメタでどの sql コマンドを使ったのを表わすことができます。

# リンク

- [sqlplot-tools](https://github.com/bingmann/sqlplot-tools) は C++ で書いてある sqlplot の先祖です。
- [sqlplot](https://github.com/koeppl/sqlplot)