Loading article…
コンピュータサイエンスにおいて、Tak関数は竹内郁夫氏にちなんで名付けられた再帰関数である。その定義は以下のとおりである。
def tak ( x : int , y : int , z : int ) -> int : y < x の場合: return tak ( tak ( x - 1 , y , z ), tak ( y - 1 , z , x ), tak ( z - 1 , x , y ) ) else : return z竹内氏による元の定義は以下のとおりです。
def 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 # not z!「たらい」は日本語の「たらい回し」の略です。
ジョン・マッカーシーはこの関数を竹内氏にちなんでtak()と名付けた。[ 5 ]
しかし、後のいくつかの参照箇所では、なぜかyがzに変わってしまっています。これは小さな違いですが、重要な違いです。なぜなら、元のバージョンは遅延評価の恩恵を大きく受けているからです。
他のコードと全く同じ方法で書かれているにもかかわらず、以下のHaskellコードははるかに高速に動作します。
たらい:: Int -> Int -> Int -> Intたらいx y z | x <= y = y |それ以外の場合= tarai ( tarai ( x - 1 ) y z ) ( tarai ( y - 1 ) z x ) ( tarai ( z - 1 ) x y )メモ化によってこの関数を簡単に高速化できるが、それでも遅延評価の方が優れている。
taraiを最適化する最もよく知られた方法は、次のような相互再帰的なヘルパー関数を使用することです。
def laziest_tarai ( x : int , y : int , zx : int , zy : int , zz : int ) -> int : y < x : return y else : return laziest_tarai ( tarai ( x - 1 , y , z ) , tarai ( y - 1 , z , x ) ,たらい( zx , zy , zz ) - 1 , x , y )def tarai ( x : int , y : int , z : int ) -> int : y < x : yを返すelse :返すlaziest_tarai ( tarai ( x - 1 , y , z ), tarai ( y - 1 , z , x ) , z - 1 , x , y )以下は、C言語でtarai()を効率的に実装した例です。
int tarai ( int x , int y , int z ) { while ( x > y ) { int oldx = x , oldy = y ; x =タライ( x - 1 , y , z ); y =タライ( y - 1 , z , oldx ); if ( x <= y )ブレーク; z =タライ( z - 1 , oldx , oldy ); yを返します。}x <= yz（3番目の引数）が評価される前に（）の追加チェックが行われることに注意してください。これにより、不要な再帰評価が回避されます。