フィボナッチ数列を使って jq コマンドの末尾再帰最適化を検証してみる

jq コマンドは立派なプログラミング言語で、末尾再帰の最適化をサポートしています。今回はフィボナッチ数列を算出する関数を定義して、検証してみます。

この記事では

  • スクリプトファイルの使い方
  • 関数の定義方法
  • フィボナッチ数列算出関数の定義
  • 末尾再帰の最適化

を順に解説していきます。

環境

  • macOS 10.14.4
  • jq 1.5
  • fish shell 3.0.0

フィボナッチ数列算出プログラムの仕様

今回作りたいプログラムは

インプット

  • 出力したいフィボナッチ数列の要素数(2以上)
  • 第2要素までのフィボナッチ数列

アウトプット

・インプットで指定した要素数までのフィボナッチ数列

とします。

第1要素、第2要素をインプットで渡すことにより、アルゴリズムを簡略化します。

最初に作りたいことのイメージを共有するため、実行結果を載せておきます。

# 要素数10のフィボナッチ数列を出力する
❯ echo '[10, [0, 1]]' | jq -f fib_seq.jq
[
0,
1,
1,
2,
3,
5,
8,
13,
21,
34
]

jq コマンドの標準入力に渡している配列([10, [0, 1]])の最初の要素(10)が、出力したいフィボナッチ数列の要素数、次の要素([0,1])が、フィボナッチ数列の1番目と2番目の要素です。

jq コマンドの引数に渡しているファイル fib.jq にフィボナッチ数列を計算する関数が定義されています。


それでは、

  • スクリプトファイルの使い方
  • 関数の定義方法
  • フィボナッチ数列算出関数の定義
  • 末尾再帰の最適化

を順に解説していきます。

スクリプトファイルの使い方

通常 jq コマンドの引数には、フィルターを記載します。

# 標準入力で渡された配列の最初の要素を取り出す
❯ echo '[10, [0, 1]]' | jq '.[0]'
10

通常これで十分なのですが、フィルターが複雑になれば、この書き方では視認性が悪くなります。

ある程度複雑なフィルターを用いたいときには、フィルターをファイルに記載して、それを jq コマンドに渡します。その際は jq コマンドの -f オプションを使います。

jq -f <フィルターが記載されたファイル>

関数の定義方法

フィボナッチ数列といえば、再帰的アルゴリズムの代表的なものです。再起的アルゴリズムを実装する場合、関数を定義するのが一般的です。

jq コマンドで関数を定義するには def シンタックスを使います。文法は以下の通りです。

def <関数名>(<仮引数>) : <本体>

例えば引数に渡された値に 1 を追加する関数は

def f(x) : x + 1

になります。

# 引数に1を渡して、1を加算して出力
❯ echo '1' | jq 'def f(x) : x + 1; f(.)'
2

f(x) : x + 1 までが関数定義部、 f(.) が関数呼び出し部です。

ちなみに仮引数は1つしか宣言できません。

jq コマンドの関数の特徴として、 unix コマンドを実装する時のように、仮引数で値を渡す以外に、標準入力(のような形)でも値を渡せます

# 標準入力(のような形)で1を渡して、1を加算して出力
❯ echo '1' | jq 'def f : . + 1; f'
2

関数定義部(def f : . + 1)で仮引数を使っていません。代わりに . を使うことにより、標準入力(のような形)で値を受け取ります。

最初の例のほうがプログラミング言語の関数としては、しっくりきますが、 jq コマンドは後者の使い方が推奨されているようです。

フィボナッチ数列算出関数の定義

それでは def シンタックスを使ってフィボナッチ数列を計算する関数を作ってみましょう。

# フィボナッチ数列算出関数
❯ cat -n fib_seq.jq
1 def fib:
2
3 if (.[0] <= (.[1] | length) )
4 then
5 .[1]
6 else
7 [
8 .[0],
9 .[1] + [.[1][-2] + .[1][-1]]
10 ]
11 | fib
12 end;
13
14 fib

行数が出力されているのは、 cat コマンドの -n オプションの効果です。

くどいかもしれませんが、各行を追ってみましょう。

    1 def fib:

フィボナッチ数列の関数を定義します。再帰的なプログラムを書きますが、仮引数を使わず、標準入力(のような形)での値渡しを利用します。従って関数名のみです。

     3     if (.[0] <= (.[1] | length) )
4 then
5 .[1]

標準入力(のような形)で渡された値の1番目の要素(.[0])で指定された、必要な要素数を満たせば再起を終了し、算出したフィボナッチ数列 ( .[1] )を出力します。

(.[1] | length) で .[1] の配列の長さを計算します。 lenghtjq コマンドの組み込み関数です。

     6     else
7 [
8 .[0],
9 .[1] + [.[1][-2] + .[1][-1]]
10 ]
11 | fib
12 end;

必要な数を満たせない時には、引き続き計算を続けます。

8行目は、必要な要素数なので、変更しません。

9行目で、フィボナッチ数列を保管した配列より、要素を大きい方から2つを取り出し、加算したものを、配列の最後に追加します。

11 行目で、再帰的に関数 fib に渡します。

def シンタックスで定義した関数への値の渡し方が理解できれば、全然無難しくないですね。

最後に

    14 fib

です。スクリプトファイルの最後に fib を記載することにより jq コマンドに標準入力で渡された値を fib 関数に渡します。

末尾再帰の最適化

jq コマンドは末尾再帰の最適化をサポートしています

As described above, recurse uses recursion, and any jq function can be recursive. The while builtin is also implemented in terms of recursion.
Tail calls are optimized whenever the expression to the left of the recursive call outputs its last value. In practice this means that the expression to the left of the recursive call should not produce more than one output for each input.

試しに、仮引数で値を渡す関数を作成し、速度を比較してみます。

Currently (jq 1.5rc1 and up) only functions with no arguments are amenable to tail-call optimization (TCO), which makes local functions useful for taking advantage of TCO.

このような記載があるので、仮引数版は末尾再起の最適化は実施されないはずですので、比較対象として意味があるでしょう。

# 仮引数版フィボナッチ数列関数
❯ cat fib_seq_arg.jq
def fib_arg(args):
    if (args[0] <= (args[1] | length))
then
args[1]
else
fib_arg(
[
args[0],
args[1] + [args[1][-2] + args[1][-1]]
]
)
end;
fib_arg(.)

それでは、仮引数版フィボナッチ数列関数を実行してみましょう。計測時間を測定するのに time コマンドを使っています。

❯ time fish -c 'echo '[10, [0, 1]]' | jq  -f  fib_seq_arg.jq > /dev/null'
1.12 real 0.61 user 0.26 sys
❯ time fish -c 'echo '[11, [0, 1]]' | jq  -f  fib_seq_arg.jq > /dev/null'
1.71 real 1.21 user 0.25 sys
❯ time fish -c 'echo '[12, [0, 1]]' | jq  -f  fib_seq_arg.jq > /dev/null'
4.10 real 3.60 user 0.25 sys

❯ time fish -c 'echo '[13, [0, 1]]' | jq -f fib_seq_arg.jq > /dev/null'
13.81 real 13.26 user 0.27 sys

求める要素数を 10 から 13 まで実行してみましたが、実行時間が非線形に増加しています

次に標準入力(みたいな形)版フィボナッチ数列関数を実行してみます。

❯ time fish -c 'echo '[10, [0, 1]]' | jq  -f  fib_seq.jq > /dev/null'
0.90 real 0.40 user 0.25 sys

❯ time fish -c 'echo '[11, [0, 1]]' | jq -f fib_seq.jq > /dev/null'
0.91 real 0.40 user 0.25 sys

❯ time fish -c 'echo '[12, [0, 1]]' | jq -f fib_seq.jq > /dev/null'
0.91 real 0.40 user 0.25 sys

❯ time fish -c 'echo '[13, [0, 1]]' | jq -f fib_seq.jq > /dev/null'
0.90 real 0.40 user 0.25 sys

実行時間は変わりません。要素数を 100 にしても変わりませんでした。

# 要素数を 100 で実行。
❯ time fish -c 'echo '[100, [0, 1]]' | jq -f fib_seq.jq > /dev/null'
0.89 real 0.40 user 0.24 sys

ちゃんと最適化されているようですね。


ますます jq に対する愛が止まらない今日この頃ですが、次回は jq 以外のネタを投稿してみたいと思います。

それでは、皆様、よい CLI ライフを!!