関数の定義における落とし穴（解答編）

関数の定義における落とし穴（出題編） - 野良C++erの雑記帳
に対する解答例です。

その１

まず、ここ。

  for _, x in ipairs(t1) do

ipairs は標準関数、つまりグローバル環境に定義された値です。
なので ipairs(t) は、おおよそ _G["ipairs"] のように解釈され、
この文が実行されるたび、グローバル環境へのテーブルアクセスが生じることになります。

一般に Lua におけるテーブルアクセスは非常に高速であり、
普通はそれが速度上の問題になることは殆どありえないわけですが、
それでも、毎回テーブルをアクセスするのは、明らかな時間の無駄です。
また、無駄という他に、もし append を定義した後に、どっかで

ipairs = nil

といったコードが呼ばれた場合、この append は最早使えなくなってしまいます。

というわけで、 ipairs はローカル変数にキャッシュしましょう。

do
  local ipairs = ipairs   -- new!
  
  function append( t, t1, ... )
    -- 実装は変わらないので略
    -- ...
  end
end

その２

同様に、関数末尾の再帰部分でも、グローバル環境へのアクセスが起こっています。

  return append( t, ... )

それが証拠に、以下のようなコードは動きません。
http://ideone.com/ayPlQ

-- append の定義（略）
 
-- append を別の関数にする
appendtable = append
function append( s1, s2 )
  return s1..s2
end
 
-- テスト
local t = { 1, 2 }
appendtable( t, { 3 }, {}, { 4, 5 }, { 6, 7, 8, 9, 10 } ) -- エラー！

この問題に対処するには、まず local で関数を定義した後、グローバルに公開します。
この時、 local で定義した関数の名前と、グローバルで公開したい関数の名前が
一致している場合、うまくグローバルに公開することが出来ないので注意します。

というわけで、さっきの ipairs と合わせて、以下のように書き直しましょう。

http://ideone.com/sZEBw

do
  local ipairs = ipairs
 
  -- 再帰関数は local で定義して
  local function append_( t, t1, ... )
    if t1 == nil then return end
 
    local n = #t
    for _, x in ipairs(t1) do
      n = n + 1
      t[n] = x
    end
 
    return append_( t, ... )
  end
 
  -- 公開
  append = append_
 
end

これで安全になり、またテーブルアクセスが減って高速化出来ます。

その３

このコードでは、再帰のたびに、毎回 #t を呼び出して t のサイズを取得しています。

  local n = #t

この呼び出しは、確かに、最初の関数呼び出しの時には必要です。
なぜなら、テーブルに対する # 演算はテーブルサイズ N に対して大体 Ο(lgN) であり、
「単純にテーブルサイズを取得する」ならば、最も妥当な手段だからです。

しかし、よく見ると、最初の呼び出し以降は、既に t のサイズは分かっていますね？
そう、関数終了時点でローカル変数 n に格納された値が、それです。

というわけで、 n を再利用すれば、その分だけ高速化出来ます。
最終的に出来たコードは、以下の通りになるでしょう：

http://ideone.com/xBclj

do
  -- 使用するグローバル変数をローカル変数に格納
  local ipairs = ipairs
  
  -- 再帰関数は local で定義する
  local function append_( t, n, t1, ... )
    if t1 == nil then return end
    
    for _, x in ipairs(t1) do
      n = n + 1
      t[n] = x
    end
    
    return append_( t, n, ... )
  end
  
  -- 公開する関数は local で定義した再帰関数を単に呼び出すだけ
  function append( t, ... )
    return append_( t, #t, ... )
  end
end

-- テスト
local t = { 1, 2 }
append( t, { 3 }, {}, { 4, 5 }, { 6, 7, 8, 9, 10 } )
 
print( table.concat( t, ", " ) )

なお、再帰での処理をやめてループでの処理に書き換えれば、
再帰にかかるコスト（末尾再帰は goto ですが、それでもゼロではない）を削減できますし、
さっきの配列長取得問題も自然に解決できますが、それは僕はいちいち書かないことにします。

結論

グローバルな関数を使う場合は、ローカル変数に格納しておくと良い
その為に、 do 〜 end によるローカルスコープを積極的に使うのは良い習慣である
その場合、ローカルスコープは極力短くする方がいい*1
再帰関数を定義する場合にもローカルで定義したほうが良い
その場合、グローバルで公開するには代入するなり、「ローカル関数を呼ぶ」関数を作るなり
一般には、再帰関数には複雑なパラメータを与えたい場合が多いので*2、単純に代入で公開するよりは、関数を新たにつくって公開したほうが良いと思われる
が、関数呼び出しが増えるコストもあるので、一概には言えない

おまけ

実は、このコードには更に最適化の余地があったりします。
それはテーブルのバッファ確保の問題で、
もし Lua のテーブルに、配列部分のバッファサイズを伸長する関数が有った場合、
その関数を仮に table.reserve(t, n) とすると、

do
  local ipairs = ipairs
  
  local function append_( t, n, t1, ... )
    if t1 == nil then return end
    
    table.reserve( t, n + #t1 ) -- 配列バッファを確保する
    for _, x in ipairs(t1) do
      n = n + 1
      t[n] = x
    end
    
    return append_( t, n, ... )
  end
  
  function append( t, ... )
    return append_( t, #t, ... )
  end
end

このように、バッファ追記の前に呼び出すことで、更に最適化することが出来ます。
なぜそうすることが最適化になるかは、興味があったら調べてみてください。

問題は、そのような関数が Lua に存在していない点で、
かろうじて API ではテーブル製作時に配列バッファ長を指定できますが、
既に構築されたテーブルに対してバッファサイズを伸長するような動作は、今の Lua では行えません。
勿論、そんなものを明示的に呼び出す必要は、無いといえば無い、というか、
基本的に言語側に勝手によろしくやってもらった方が効率的な場合も多いのですが、
今回のような「言語側からは分からない情報」を使って最適化したい場合も多いので、
もし深い理由があってそうなっているのでなければ、 reserve 欲しいなーと思う次第です。

*1:詳しくはhttp://ideone.com/LlnCi。val欲しい。

*2:この例では n