機械学習／テキスト処理 × Lua (LuaJIT)

研究

Python で書いた Passive Aggressive-I が C++ 実装に比べて50倍遅かったので，（スクリプト言語でも）もう少しぐらい速くならないかと思って，スクリプト言語で最速の処理系 (LuaJIT) を持つ Lua で Passive Aggressive-I を実装してみることにした．
Lua はアプリケーションへの組み込みを意図し，高速な動作，ポータビリティ，拡張の容易さなどを重視して設計されたコンパクトな汎用スクリプト言語．今月の TIOBE Programming Community Index では Ruby の一つ下の12位にランキングされている*1．これは，iPhone アプリの開発者による利用が増えているというのが大きい*2と思うが，プログラム言語の設計者たちへのインタビューを纏めた Masterminds of Programming（邦訳: 言語設計者たちが考えること）に Lua の設計者のインタビューが取り上げられたり，その設計者の一人 Roberto Ierusalimschy による Programming in Lua や入門書（入門Luaプログラミング）など日本語の書籍も出版されたりしているので，ここ数年で日本でも認知／普及が進んでいるのは間違いなさそうだ．
Lua の文法を調べつつ，1時間ぐらいで翻訳完了．[追記] Lua は，ビルトイン型／関数が極限まで切り詰められており，複合的で能弁な関数がほとんど存在しないという点で，肥大化したライブラリを備えた Perl/Python/Ruby など他のスクリプト言語とは対照的な言語仕様になっている．
型は nil, boolean, number, string, function, userdata, thread, table の 8種類．数値型は number (double) だけで整数型はない．配列／連想配列は table に二重定義された仕様（http://www.lua.org/gems/sample.pdf の About Tables を参照）になっていて，配列部を連想配列部と区別して走査できる．例えば，下の Passive Aggressive の例では，ex[0] は配列の要素と見なされない（配列の添字は 1 から）．これは興味深い実装だ．table は metatable 経由で柔軟に拡張が可能．下のコードではデフォルト値の動作を定義するのに使っている．
ビルトイン関数については Lua 5.1 Reference Manual - contents を見ると分かるが，文字列操作に使う split/join も無ければ，スクリプト言語で多用する map/filter/reduce もない．基礎的な関数を追加する際には，

にある実装例が参考になる．
Lua は自分色に染められる言語．言語仕様がコンパクトな分，身につけるのは Perl/Python/Ruby 以上に簡単だろう．スクリプト言語における（Perl/Python/Ruby に対する）Lua の位置付けは，コンパイラ言語における（C++ に対する）C のような印象だ（感覚的な意味なので誤解のないよう）．[追記終]
処理系は，

が代表的で，今回は Lua VM の最新版 (lua 5.2.0-alpha) と LuaJIT の最新版 (luajit 2.0.0-beta6; git) を比較した．
処理速度については

に多言語との比較があり，ベンチマークごとのバラつきはやや大きいものの， Javascript V8 より速く，C/C++ 以外のコンパイラ言語に匹敵する実行速度が出ていることが確認できる*3．効率的なコードの書き方は，

が参考になる．特に，local, numeric for を積極的に用いるのが効果的なようで，以下のスクリプトも Lua VM に最適化するよう（コードの可読性が落ちない範囲で）書き直した．ただし，処理系に LuaJIT を使う場合は必ずしも高速化されるとは限らず，例えば 以下のコートでは numeric for より generic for の方が速かったりしたので注意が必要．
結局，Passive Aggressive-I の Lua 実装は以下のようになった．多分以前の Python 実装以上に，以下のスクリプトは Lua として適切な実装になっていない．

#!/usr/bin/env lua

if #arg < 4 then
   print ("Usage: " .. arg[0] .. " train test c iter")
   return
end

train, test, c, iter  = arg[1], arg[2], tonumber (arg[3]), tonumber (arg[4])

examples = {}
for line in io.lines (train) do
   local ex = { [0] = tonumber (string.match (line, "^%S+")) } -- #ex = 0
   for f in string.gmatch (line, " (%d+)") do -- no built-in split
      ex[#ex+1] = tonumber (f)
   end
   examples[#examples+1] = ex
end

local w = {}
setmetatable (w, { __index = function () return 0 end } ) -- default value
for i = 1, iter do
   for j = 1, #examples do
      local ex = examples[j]
      local margin = 0
      for j = 1, #ex do  -- ipairs; LuaJIT (-10%)
         margin = margin + w[ex[j]]
      end
      margin = ex[0] * margin
      if margin <= 1 then
         local t = ex[0] * math.min (c, (1 - margin) / #ex) -- there was a bug here (corrected)
         for j = 1, #ex do w[ex[j]] = w[ex[j]] + t end  -- localize; Lua VM (-5%)
      end
   end
   io.stderr:write (".")
end
io.stderr:write ("done.\n")

pp, pn, np, nn = 0, 0, 0, 0
for line in io.lines (test) do
   local margin = 0
   for f in string.gmatch (line, " (%d+)") do
      margin = margin + w[tonumber (f)]
   end
   if tonumber (string.match (line, "^%S+")) > 0 then
      if margin > 0 then pp = pp + 1 else pn = pn + 1 end
   else
      if margin > 0 then np = np + 1 else nn = nn + 1 end
   end
end

print (string.format ("acc. %2.3f%% (pp %d) (pn %d) (np %d) (nn %d)",
                      (pp + nn) * 100 / (pp + pn + np + nn), pp, pn, np, nn))

実行してみる．

# Lua VM
> run lua pa.lua train test 0.005 20
....................done.
acc. 91.064% (pp 53006) (pn 4776) (np 5386) (nn 50548)
elapsed (real): 29.129s; RSS=242.7M

# LuaJIT
> run luajit pa.lua train test 0.005 20
....................done.
acc. 91.064% (pp 53006) (pn 4776) (np 5386) (nn 50548)
elapsed (real): 9.096s; RSS=151.2M

# Python
> run python2.6 pa.py train test 0.005 20
....................done.
acc. 91.064% (pp 53006) (pn 4776) (np 5386) (nn 50548)
elapsed (real): 63.262s; RSS=276.5M

# C++ (gcc -O2 -march=core2 -m64)
> run pa train test 0.005 20
....................done.
acc. 91.064% (pp 53006) (pn 4776) (np 5386) (nn 50548)
elapsed (real): 1.331s; RSS=51.0M

Lua VM -> LuaJIT でかなり高速化されている．Lua 実装 (LuaJIT) は C++ 実装よりは 7 倍遅いが Lua 実装 (Lua VM) に比べて 3 倍，Python 実装 (python 2.6) の 7 倍高速．C++/Python と結果が少しズレているのが気になる．何故だろう・・・． バグを直したら，結果は一致した．
（Wikipedia 中の）単語の頻度を数えるスクリプトも翻訳してみた．

#!/usr/bin/env lua

local dict = {}
setmetatable (dict, { __index = function () return 0 end })
for line in io.lines ("unigram_raw.txt") do
   dict[line] = dict[line] + 1
end

for key, value in pairs (dict) do
   print (key .. " " .. value)
end

実行してみる．

> run lua count.lua > tmp.lua
elapsed (real): 81.105s; RSS=271.8M

# LuaJIT
> run luajit count.lua > tmp.luajit
elapsed (real): 56.256s; RSS=208.1M

# Python
> run python2.6 count.py > tmp.py26    
elapsed (real): 126.397s; RSS=318.2M

Lua 実装 (LuaJIT) は Python/Perl 実装より2倍速く，C++ 実装より2倍遅い程度．Lua 実装 (Lua VM) でも Python 実装 (python2.6) より有意に高速だった．しかし，Lua VM -> LuaJIT でメモリ消費も減るのは驚きだ．
というわけで，LuaJIT の実力は本物．

*1:http://journal.mycom.co.jp/news/2011/04/19/016/index.html

*2:ゲームプログラマの間で最も利用されているスクリプト言語らしい．

*3:出典はhttp://shootout.alioth.debian.org/だと思われるが，Lua JIT, PyPy, Tracemonkey, Python 2.7, JRuby and others removed from the Benchmark Game [shootout.alioth.debian.org] : programming にあるように，PyPy などと共に二週間前にベンチマークから削除されてしまったようで，現在のページからは見られなくなっている．2011年2月のデータも見つけた．