「竹内関数」の版間の差分
語の定義と概要を分離、概要に特徴を追加 |
m編集の要約なし |
||
1行目: | 1行目: | ||
'''竹内関数(たけうちかんすう) |
'''竹内関数'''(たけうちかんすう)は、[[プログラミング言語]][[実装|処理系]]の[[ベンチマーク]]などに使われる、[[再帰的定義|再帰的に定義]]された[[関数 (数学)|関数]]である。 |
||
== 概要 == |
== 概要 == |
||
三つの[[整数]] ''x, y, z'' に対して、次のように再帰的に[[定義]]される。 |
三つの[[整数]] ''x'', ''y'', ''z'' に対して、次のように[[再帰]]的に[[定義]]される。 |
||
<math>{\rm Tarai}(x, y, z) = \begin{cases} |
<math>{\rm Tarai}(x, y, z) = \begin{cases} |
||
9行目: | 9行目: | ||
\end{cases}</math> |
\end{cases}</math> |
||
定義からわかるように処理を次々にたらい |
定義からわかるように処理を次々に[[たらい回し]]にしていくことから、'''たらいまわし関数'''、'''たらい関数''' (''Tarai function'') とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。[[日本電信電話公社|電電公社]]研究員(当時)の[[竹内郁雄]]が[[1976年]]に考案した。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。 |
||
他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム(dumb)フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない(ワード長の整数演算さえ実装していれば十分)、再帰がたいして深くならない(たいした量のスタックを使えなくても十分)、といった特性があり、関数呼び出し(と戻り)の[[オーバーヘッド]]がものをいう、というベンチマークである。 |
他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム(dumb)フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない(ワード長の整数演算さえ実装していれば十分)、再帰がたいして深くならない(たいした量のスタックを使えなくても十分)、といった特性があり、関数呼び出し(と戻り)の[[オーバーヘッド]]がものをいう、というベンチマークである。 |
||
37行目: | 37行目: | ||
竹内関数を高速化するには、関数呼び出しのコストを小さくする、というまっとうな手法と、計算を必要になるまでやらない(引数のx, y, zの値が実際に必要なのは、関数の呼び出し時でなくifの評価時で、しかも常に全部は必要としない)か、一度やった計算の結果を再利用するかして、計算量自体を削減する(当然非常に速い。ベンチマークとしては一種のチートと言えなくもない)手法とがあり、後者には次のような手法がある。 |
竹内関数を高速化するには、関数呼び出しのコストを小さくする、というまっとうな手法と、計算を必要になるまでやらない(引数のx, y, zの値が実際に必要なのは、関数の呼び出し時でなくifの評価時で、しかも常に全部は必要としない)か、一度やった計算の結果を再利用するかして、計算量自体を削減する(当然非常に速い。ベンチマークとしては一種のチートと言えなくもない)手法とがあり、後者には次のような手法がある。 |
||
; [[メモ化]] |
|||
一度計算した値を覚えておき、次の呼び出しではその値を使う。 |
: 一度計算した値を覚えておき、次の呼び出しではその値を使う。 |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
マッカーシー版は、メモ化では同様に速い。しかし、マッカーシー版をHaskellなどでそのままの定義で遅延評価した場合は、高速にならない(遅延評価では計算量が減らない)、という違いがある。 |
マッカーシー版は、メモ化では同様に速い。しかし、マッカーシー版をHaskellなどでそのままの定義で遅延評価した場合は、高速にならない(遅延評価では計算量が減らない)、という違いがある。 |
||
54行目: | 53行目: | ||
* [http://www.nue.org/nue/#tak-function TAK Function] |
* [http://www.nue.org/nue/#tak-function TAK Function] |
||
* [http://mathworld.wolfram.com/TAKFunction.html Wolfram MathWorld] |
* [http://mathworld.wolfram.com/TAKFunction.html Wolfram MathWorld] |
||
* [http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.htm どう転んでもLisp] - スライド10 |
* [http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.htm どう転んでもLisp] - スライド10 - 13に作者自身の解説がある |
||
* [http://www.nue.ci.i.u-tokyo.ac.jp 東京大学 竹内郁雄研究室] |
* [http://www.nue.ci.i.u-tokyo.ac.jp 東京大学 竹内郁雄研究室] |
||
2011年11月12日 (土) 03:37時点における版
竹内関数(たけうちかんすう)は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。
概要
三つの整数 x, y, z に対して、次のように再帰的に定義される。
定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数、たらい関数 (Tarai function) とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。電電公社研究員(当時)の竹内郁雄が1976年に考案した。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。
他のよくベンチマークに使われる関数と比較して、たとえばフィボナッチ数を何の工夫もなく計算するいわゆるダム(dumb)フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない(ワード長の整数演算さえ実装していれば十分)、再帰がたいして深くならない(たいした量のスタックを使えなくても十分)、といった特性があり、関数呼び出し(と戻り)のオーバーヘッドがものをいう、というベンチマークである。
マッカーシー版
ジョン・マッカーシーは竹内関数を記憶違いで[1] z を返すように変更し、これがTak関数として広まった。以下がその定義である。
計算量はずっと少ない。
本質
竹内関数の出力は以下のものと同等である。
ドナルド・クヌースによる研究が、Textbook Examples of Recursion(1990)にある。
高速化
竹内関数を高速化するには、関数呼び出しのコストを小さくする、というまっとうな手法と、計算を必要になるまでやらない(引数のx, y, zの値が実際に必要なのは、関数の呼び出し時でなくifの評価時で、しかも常に全部は必要としない)か、一度やった計算の結果を再利用するかして、計算量自体を削減する(当然非常に速い。ベンチマークとしては一種のチートと言えなくもない)手法とがあり、後者には次のような手法がある。
- メモ化
- 一度計算した値を覚えておき、次の呼び出しではその値を使う。
- 遅延評価
- クロージャなどを利用して、関数呼び出しの計算より前に引数を計算すること(先行評価)をしない(ただし、クロージャ生成のコストがかかる)。原則として遅延評価する言語であるHaskellでは定義そのままで非常に速い。他にもScalaなど遅延評価に対応した言語においては、簡単に、非常に高速に評価が終わるコードを作成できる。
マッカーシー版は、メモ化では同様に速い。しかし、マッカーシー版をHaskellなどでそのままの定義で遅延評価した場合は、高速にならない(遅延評価では計算量が減らない)、という違いがある。
参照
関連項目
外部リンク
- TAK Function
- Wolfram MathWorld
- どう転んでもLisp - スライド10 - 13に作者自身の解説がある
- 東京大学 竹内郁雄研究室