2017/09/19

サンプルコード:フィボナッチ数を対数時間で求める

今回はフィボナッチ数を対数時間で求めるプログラムについてです。



Wikipedia より)


フィボナッチ数とは、次の漸化式で表せる数列です。

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

実際に各値を求めると次のような数値になります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Wikipedia には次のような一文があります。

フィボナッチ数(フィボナッチすう、英: Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)にちなんで名付けられた数である。

フィボナッチ数 - Wikipedia
Fibonacci - Wikipedia

なんでも、 12 世紀頃の数学者であり「フィボナッチ」(ボナッチの息子)と(後に)呼ばれた、イタリアのレオナルドさん発案だそうです。

余談ですが、「レオナルド」はイタリアあたりの歴史にやたらに登場しますね。日本でいう「ごんべえ」的な感じでしょうか。

それはさておき。

フィボナッチ数の値は解析的に求めることもできますが、プログラミングの課題としては、再帰アルゴリズムあるいは動的計画法を使って解くことが求められることが多いようです。

まずはロジックが最もシンプルな線形時間でのアプローチを先に見てみましょう。


線形時間での求解


単純なループを使った動的計画法アプローチでは、線形時間 O(n) で解くことができます。



これは直感的な求め方ですね。続いて対数時間で求めるアプローチです。


対数時間での求解


フィボナッチ数は直感に反し、対数時間 O(log(n)) で求めることができます。

ポイントは次のとおりです。

  1. 行列で考えた場合、フィボナッチ数の漸化式は F(n) = P * F(n - 1)(ただし P((1, 1), (1, 0) という行列)で表せる。
  2. 結果、 F(n)F(n) = P^n * (1, 0)^T で求めることができる。
  3. ミソは P^n の計算で、これは単純に Pn 回積を繰り返して求めることもできるが、例えば n = 2^m となる場合(例えば n = 64 なら m = 6 )にかぎると、 P^64 = (P^32)^2 = ((P^16)^2)^2 = (((P^8)^2)^2)^2 = ((((P^4)^2)^2)^2)^2 = (((((P^2)^2)^2)^2)^2)^2 ということで、 2 乗を 6 回繰り返す形でも求めることができる(つまり指数時間で求められる)。これは 63 回積を繰り返すより断然早い。
  4. n = 2^m とならない n については、 n = 2^m1 + 2^m2 + 2^m3 + ... という形に分解することで(要は 2 進数表現にすることによって)各部を 2^m の形に表すことができる。この事実を利用すると、 P^n = P^(2^m1 + 2^m2 + 2^m3 + ...) = P^(2^m1) * P^(2^m2) * P^(2^m3) * ... で求められる。

詳細のロジックに興味のある方は、次のページの解説がとても丁寧でわかりやすいのでそちらをご覧になってみてください。

The Nth Fibonacci Number in O(log N)

実際のサンプルコードは次のとおりです。



コード上のポイントは次のとおりです。

  • フィボナッチ数を求める関数は get_fibonacci() で、それ以外の関数はすべてヘルパー関数です。
  • if __name__ == '__main__': 以下の部分はすべてテストコードです。
  • 上の 4. の 2 の乗数への分解を行う関数は get_2exponent_series() です。
  • 上の 3. の部分を担う関数は pow_matrix() です。
  • 行列の積の計算は multiply_matrix() で行っています。単純な 2 x 2 行列の計算なので、ライブラリは使わずそのまま計算しています。間違いやすいのでケアレスミスに注意が必要です。
  • やや本筋から外れる、キャッシングと畳み込みの計算には標準ライブラリ functoolslru_cache()reduce() を使っています。

以前の「ハノイの塔」のサンプルと同じく、ホワイトボードコーディングの本の中に出てきたので個人的なエクササイズを兼ねて書いてみました。

この話題(「フィボナッチ数を対数時間で求める方法」)については学生時代にちらっと学んだことがある気がするのですが、その詳細は完全に忘れてしまっていたので、今回改めて調べて「おぉ、これはすごい!」ととても感動しました(笑)。

再帰や動的計画法は「問題の本質をいかにシンプルな形で捉え抽出することができるか」がポイントで、このあたりは汎用の問題解決能力とも直結する気がします。私はこのあたりは特段苦手というわけではありませんが、「ものすごく得意」「閃きまくって仕方がない!」というわけでもないので、こういう問題解決が得意な人を見るとうらやましくなります。

2017/09/06

Python ライブラリ: watchdog

Python のライブラリである watchdog をご紹介してみます。

watchdog : Python Package Index

今回は次の組み合わせで動作確認をしています。

python 3.6.1
watchmedo 0.8.3

watchdog とは


watchdog とはファイルの変更を監視して、ファイルが変更されたら何らかの処理を行う自動化ツール作成のためのライブラリです。

watchdog を import してスクリプトを書く方法と、 watchmedo というコマンドを利用する方法の 2 つの利用方法が用意されています。

私はライトな使い方しかしておらず「コマンドを使用する方法」だけで事足りてしまっているので、今回は後者のみの紹介とさせていただきます。スクリプトを書く方法に興味のある方は公式のドキュメントをご覧になってみてください。

Watchdog — watchdog documentation

インストール


pip でそのままインストールしましょう。


$ pip install watchdog


基本的な使い方


上述のとおり、今回は watchdog が提供するコマンド watchmedo を使った方法をご紹介します。

といっても使い方はシンプルで、 watchmedo コマンドに監視対象と実行したいコマンドをオプションでただ渡すだけで OK です。

以下は私が PHP のプロジェクトで PHPUnit のテストを書いている最中に使ったコマンドです。 PHPUnit のテストファイルが更新されたら(私がファイルを保存したら)自動で対象のテストファイルに対してテストを実行するというものです。


watchmedo shell-command \
--patterns="*Test.php" \
--ignore-directories \
--recursive \
--command='./vendor/bin/phpunit ${watch_src_path} && echo ""'


watchmedo にサブコマンド shell-command を指定して実行しています。使用しているオプションについて以下にかんたんに説明します。

  • --patterns 対象のファイル名のパターン。
  • --ingore-directories ディレクトリを無視する場合につける。
  • --recursive 再帰的に子孫ディレクトリをウォッチする場合につける。
  • --command ファイルの変更が検出されたときに実行したいコマンド。

私がいま確認したところ、公式のドキュメントには詳しい記述がありませんが、 --command オプションで指定するコマンドの中では以下のパラメータを利用することができます。


${watch_src_path} 変更されたファイルのパス
${watch_dest_path} ファイル移動が発生するイベントにおいて移動先のファイルのパス
${watch_event_type} イベントのタイプ
${watch_object} ファイルかディレクトリか


以上です。

このあたりについては Node.js まわりでの開発が最近活発ですが Node.js は流行り廃りのサイクルが他の言語に比べて短いような気もするので、この Python の watchdog など短期間では廃りにくい方法をひとつ知っておくと便利だと思います。

参考

Watchdog — watchdog documentation
GitHub - gorakhargosh/watchdog: Python library and shell utilities to monitor filesystem events.

2017/08/28

サンプルコード:ハノイの塔

再帰( recursion )を使うと解法のロジックをわかりやすく表現できる問題のひとつに「ハノイの塔」というものがあります。



ハノイの塔(ハノイのとう、Tower of Hanoi)はパズルの一種。 バラモンの塔または ルーカスタワー(Lucas' Tower)とも呼ばれる。

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

  • 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
  • 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
  • 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤すべてを移動させるには最低 2n − 1 [2]回の手数がかかる。

解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。

ハノイの塔 - Wikipedia

画像、テキストともに出典はいずれも Wikipedia です。

私事ですが、最近ホワイトボードプログラミングの本を読んでおりその中にハノイの塔が出てきたので、今回は個人的なエクササイズも兼ねてハノイの塔のプログラムを Python で書いておきたいと思います。

ここに載せるには少し長くなったので Gist に貼り付けました。



このプログラムを実行すると次のような内容が出力されます。「 move ... 」から始まる行はディスクの移動を表します。 s d e は各塔を表します。蛇足かもしれませんが、 s は source 、 d は destination 、 e は extra の略です。

started.
s: 3 2 1 
d: 
e: 
move disk-1 from s to d (1).
s: 3 2 
d: 1 
e: 
move disk-2 from s to e (2).
s: 3 
d: 1 
e: 2 
move disk-1 from d to e (3).
s: 3 
d: 
e: 2 1 
move disk-3 from s to d (4).
s: 
d: 3 
e: 2 1 
move disk-1 from e to s (5).
s: 1 
d: 3 
e: 2 
move disk-2 from e to d (6).
s: 1 
d: 3 2 
e: 
move disk-1 from s to d (7).
s: 
d: 3 2 1 
e: 
finished.

解法のコアとなる部分は TowerOfHanoi クラスの move_disk() メソッドのみです。その他の部分は、途中経過や移動の回数を表示するための周辺的コードです。

ハノイの塔の解法がなぜ move_disk() のような再帰を含むメソッド(関数)で書けるのかについてここでの説明は割愛します。興味のある方は Wikipedia の「解き方」の節をご覧になってみてください。

私事ですが、ふだんはウェブ開発をやっていて、このような難しいアルゴリズム問題を考えたりするようなことはあまりないので、書いていてとても新鮮な気持ちになりました。おもしろいです。


参考

ハノイの塔 - Wikipedia