Tak (funkce) - Tak (function)

v počítačová věda, Funkce Take je rekurzivní funkce, pojmenoval podle Ikuo Takeuchi (竹 内 郁 雄). Je definován takto:

def tak( X, y, z)  -li y < X    tak(          tak(X-1, y, z),         tak(y-1, z, X),         tak(z-1, X, y)       )  jiný    z  koneckonec

Tato funkce se často používá jako měřítko pro jazyky s optimalizací pro rekurze.[1][2][3][4]

tak () vs. tarai ()

Původní definice Takeuchiho byla následující:

def tarai( X, y, z)  -li y < X    tarai(          tarai(X-1, y, z),         tarai(y-1, z, X),         tarai(z-1, X, y)       )  jiný    y          # ne z!  koneckonec

tarai je zkratka tarai mawashi„v japonštině projít kolem“.

John McCarthy pojmenoval tuto funkci tak () po Takeuchi.[5]

V určitých pozdějších odkazech se však y nějak proměnilo v z. Toto je malý, ale významný rozdíl, protože původní verze významně těží líné hodnocení. Ačkoli je napsáno přesně stejným způsobem jako ostatní, Haskell kód níže běží mnohem rychleji.

tarai :: Int -> Int -> Int -> Inttarai X y z    | X <= y    = y    | v opačném případě = tarai(tarai (X-1) y z)                       (tarai (y-1) z X)                       (tarai (z-1) X y)

Tuto funkci můžete snadno urychlit pomocí memorování přesto líné hodnocení stále vyhrává.

Nejznámějším způsobem optimalizace tarai je použití vzájemně rekurzivní pomocné funkce následujícím způsobem.

def laziest_tarai(X, y, zx, z y, zz)  ledaže y < X    y  jiný    laziest_tarai(tarai(X-1, y, z),                  tarai(y-1, z, X),                  tarai(zx, z y, zz)-1, X, y)  koneckonecdef tarai(X, y, z)  ledaže y < X    y  jiný    laziest_tarai(tarai(X-1, y, z),                  tarai(y-1, z, X),                  z-1, X, y)  koneckonec

Zde je efektivní implementace tarai () v C:

int tarai(int X, int y, int z){    zatímco (X > y) {        int oldx = X, oldy = y;        X = tarai(X - 1, y, z);        y = tarai(y - 1, z, oldx);        -li (X <= y) přestávka;        z = tarai(z - 1, oldx, Oldy);    }    vrátit se y;}

Všimněte si další kontroly pro (x <= y) před vyhodnocením z (třetí argument), abyste se vyhnuli zbytečnému rekurzivnímu vyhodnocení.

Reference

  1. ^ Peter Coffee (1996). "Tak test obstojí ve zkoušce času". PC Week. 13 (39).
  2. ^ "Rekurzivní metody" Elliotte Rusty Harold
  3. ^ Johnson-Davies, David (červen 1986). “Šest z nejlepších proti času”. Uživatel žaludu. 179, 181–182. Citováno 28. října 2020.
  4. ^ Johnson-Davies, David (listopad 1986). "Testování Tak". Uživatel žaludu. 197, 199. Citováno 28. října 2020.
  5. ^ John McCarthy (prosinec 1979). "Zajímavá funkce LISP". Bulletin ACM Lisp (3): 6–8. doi:10.1145/1411829.1411833.

externí odkazy