2007年 05月 12日

Lua 末尾再帰最適化

subtech

Lua は末尾再帰最適化を行う。ってマニュアルに書いてあるんだけど、ホントカヨーって思って調べてみた。

function pow(x, n)
	if n == 1 then return x end

	return x * pow(x, n-1)
end

function pow_tail(x, n)
	local function pow_f (c, r)
		if c == 0 then
			return r
		else
			return pow_f(c - 1, x * r)
		end
	end

	return pow_f(n, 1)
end

-- print(     pow(2, 1000000000))
-- print(pow_tail(2, 1000000000))

pow は普通の再帰で pow_tail が末尾再帰ばーじょん
pow のほうを実行すると

lua: math1.lua:7: stack overflow
stack traceback:
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        ...
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:22: in main chunk
        [C]: ?

でエラー

pow_tail を実行中に途中で C-c で止めると

^Clua: interrupted!
stack traceback:
        math1.lua:15: in function <math1.lua:11>
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        ...
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        math1.lua:23: in main chunk
        [C]: ?

と tail call でスタック情報が消えて ? になってることがわかる。

❤️ 投げ銭する

Lua math ライブラリが遅い?

subtech

math ライブラリが遅いって聞いたけど

#!lua
# math1.lua
for i = -5000000, 5000000 do
	math.abs(i)
end
#!lua
# mathrep.lua
function abs(i)
	if i < 0 then return -i else return i end
end

for i = -5000000, 5000000 do
	abs(i)
end
#!lua
# math2.lua
abs = math.abs
for i = -5000000, 5000000 do
	abs(i)
end
$ repeat 5 time lua -v math1.lua
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.02s system 99% cpu 2.719 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.710 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.712 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.711 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.711 total
$ repeat 5 time lua -v mathrep.lua
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.51s user 0.02s system 98% cpu 2.562 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.52s user 0.02s system 99% cpu 2.548 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.51s user 0.01s system 99% cpu 2.545 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.52s user 0.01s system 99% cpu 2.547 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.51s user 0.01s system 99% cpu 2.547 total
$ repeat 5 time lua -v math2.lua
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.195 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.192 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.198 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.191 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.193 total

結論：(少なくとも Mac 上の 5.1.1 の math.abs については) テーブルのキーをひくのがおそいだけで、関数自体は math のほうが高速

❤️ 投げ銭する
2007年 05月 11日

学校

半期の生物特殊講義が面白い。なんかこう、知識を吸収してるって感じがある。テストができるかは謎だけどw
セントラルドグマの DNA -> RNA -> タンパク質のあたりがおもしろい (DNA と入力しようとすると DNS とうってしまうのをどうにかしたい)
というか今までタンパク質が何なのかさえ知らなかった。アミノ酸がなんなのかとか。DNA の中の遺伝子が保持されている場所はどうやって記録されているかとか

❤️ 投げ銭する

関連エントリー

404

取り戻す青春が見つかりません。

器用貧乏な女の子

だいたいのことを平均より少しできる（できるようになることがすぐにできる）女の子について

ヘッドフォン娘の良さは無機質なものとのギャップがメインではない

と思う。そんなんだったら別にヘッドフォンじゃなくていい。

2007年 05月 10日

✖

やっぱ他人のブログ読むのは重要だな。
ブログ書いてるので読んでると、ちょっとその人への考えかたが変わる気がする。

なんか

なんか今日は腹の底のほうにもにょもにょした感じのがたまっていて、気分が悪い。憂鬱だなぁ。いろんなことが不安すぎる。

mac socks

subtech

Mac で svn/svk を socks 化する方法がない…… tsocks うごかないしなぁ

MacPorts インストールしなおしたらうごいた。
けど、DNS をやっぱりローカル解決しててだめだ。hosts かけばいいかなぁ

hosts に SSH サーバ先から見たレポジトリの IP 書いて sudo lookupd -flushcache したらいけた
❤️ 投げ銭する
2007年 05月 09日

Lua イテレータをコルーチンで実装する。

subtech

これはなんか Ruby と似た感じで実装できる。

local itr = coroutine.wrap(function ()
    local i = 1
    while true do
        coroutine.yield(i)
        i = i + 1
    end
end)


for i in itr do
    print(i)
    if i > 10 then break end
end

for in にはイテレータ関数を与える。coroutine.wrap はファンクションを与えるとコルーチン (thread) を生成してそれを resume する関数を返す。

yield の引数が呼び出し元に返って、in の前の変数に代入される。（多値かえして多重代入もできる）

❤️ 投げ銭する