読者です 読者をやめる 読者になる 読者になる

futoase

よろしくお願いします。

Nimrod AdventCalendar 8日目 兼 俺 AdventCalendar 8日目

全国の Nimrod ファンのみなさんこんにちは。
Nimrod Advent Calendar の 8日目を担当している、@syanbi a.k.a. @xgaです。7日目の記事は @takano32 さんの Nimrodへようこそ - Prologue です。ぜひ、こちらもご覧ください。

竹内関数

どうも皆さん。竹内関数はご存知でしょうか?
たらい回し関数と言われていて、言語処理系のベンチマークに使われている関数です。

検証環境

検証環境は以下のとおりです。

  • OS: MacOS X Lion (10.7)
  • MacBook Air 2011 11inch CPU: Core i7 (1.8GHz) RAM: 4GB(DDR3 1333Mhz)

Nimrodで竹内関数

さっそく書いてみましょう。

proc tarai(x: int, y: int, z: int): int =
  if y < x:
    return tarai(
      tarai(x-1, y, z),
      tarai(y-1, z, x),
      tarai(z-1, x, y)
    )
  else:
    return y

when isMainModule:
  discard tarai(12, 6, 0)
  echo("owari...")
  • discard という宣言は、関数の戻り値を無視するという宣言です。Nimrodでは関数(proc)の返り値は無視されません。 ここを参考のこと
  • isMainModule で判断すると、ファイル単体で実行された時のエントリポイントとしてブロックを利用することができます。

実行結果


x=12, y=6, z=0 だとものすごい速さですね。ちょっと与える数を変更させてみましょうか…

x=15, y=5, z=0 で実行してみます。

これでも約33.3秒と充分に早いです。

pythonでやってみたらどうなるのだろう

  • 処理系は CPython version 2.7.2 で実行しました。
  • メモ化とかせず単純に書いて実行してみると…
#!/usr/bin/env python
# -*- coding:utf-8 -*-

def tarai(x,y,z):
  if y < x:
    return tarai(
      tarai(x-1, y, z),
      tarai(y-1, z, x),
      tarai(z-1, x, y)
    )
  else:
    return y

if __name__ == '__main__':
  tarai(12, 6, 0)
  print("owari...")

実行結果


x=12, y=6, z=0 で約3.2秒かかりました。
怖いですが、x=15, y=5, z=0で確認してみましょう。

12分以上かかりました。メモ化を行うとか、pypyを使うなどの工夫を行えばもっと速くなると思いますが、
そもそもNimrodはCにトランスレートを行った上でコンパイル処理を行うため、Pythonでは歯がたたないでしょう…

お次は

9日目の記事は似非原 a.k.a. @esehara さんの記事になります。お楽しみに!

俺AdventCalendar 7日分について

  • 今日中に書きます。

Copyright (c) 2013-2015 Keiji Matsuzaki