TI-Nspire & Lua / スクリプティングのヒント / メタテーブルを使う 9 of 9 / メモ化する

参考:

• Programming in Lua プログラミング言語Lua公式解説書, p.194-200
• http://adriweb.free.fr/t3/2013/Powerpoint_Advanced_TI-Nspire_Lua_Programming.pptx, p.15
• お気楽 Lua プログラミング超入門

-- 竹内函数を定義する。これをメモ化してみる。
function tarai(x, y, z)
   if x <= y then
      return y
   else
      return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
   end
end 

-- メモ化函数を定義する。
function memorize(func)
   local mem = {} -- 計算結果を記憶しておくためのテーブルを用意する。
   setmetatable(mem, {__mode = "v"}) -- そのテーブルを「(値の) 弱いテーブル」にする。弱いテーブルにする意味は今回はあまりない。
   return function(...)
              -- 引数をキーとして過去の計算結果を参照し、
              -- 計算結果が見つかればそれを返す。
              -- 見つからなければ新たに計算して返すとともに記憶しておく。
             local key = table.concat({...}, ",") 
             local result = mem[key]
             if result == nil then
                result = func(...)
                mem[key] = result
             end
             return result
          end
end

------------------
-- 確かめてみる --
------------------
-- メモ化しない場合:
do
local startTime = timer.getMilliSecCounter()
local a = tarai(12,6,0)
local stopTime = timer.getMilliSecCounter()
local elapsedTime = stopTime - startTime
print("case 1. output: "..a..", elapsed time: "..elapsedTime.." msec")
end

-- メモ化した場合:
tarai = memorize(tarai)
do
local startTime = timer.getMilliSecCounter()
local a = tarai(12,6,0)
local stopTime = timer.getMilliSecCounter()
local elapsedTime = stopTime - startTime
print("case 2. output: "..a..", elapsed time: "..elapsedTime.." msec")
end

-- メモ化した竹内函数をもう一度同じ初期値で計算した場合:
do
local startTime = timer.getMilliSecCounter()
local a = tarai(12,6,0)
local stopTime = timer.getMilliSecCounter()
local elapsedTime = stopTime - startTime
print("case 3. output: "..a..", elapsed time: "..elapsedTime.." msec")
end