技術に関するメモ 9 技術に関するメモ 9 s = s..x などのコードでループ処理）は非常にコストがかかる可能性があります。このメモでは、Lua で分割して文字列を作成する効率的な方法について説明します。例えば、ファイルを行ごとに読み取って文字列を段階的に作成しているとしましょう。一般的なコードは次のようになります。
-- WARNING: bad code ahead!! local buff = "" while 1 do local line = read() if line == nil then break end buff = buff..line.."\n" end一見問題ないように見えますが、このコードは Lua では大きなファイルの場合に大幅なパフォーマンス低下を招く可能性があります。例えば、350 K バイトのファイルを読み取ると、約 1 分かかります。
多くの場合、これは問題ではありません。小さな文字列では、上記のループで十分です。ファイル全体を読み取るには、"*all" オプションを使用して一度に読み取ることができます。しかし、このような簡単な解決策がない場合もあります。そのとき、唯一の解決策は問題に対するより効率的なアルゴリズムです。ここでは 1 つ（問題ではなくアルゴリズム）を示します。
function newBuffer ()
return {n=0} -- 'n' counts number of elements in the stack
end
function addString (stack, s)
tinsert(stack, s) -- push 's' into the top of the stack
for i=stack.n-1, 1, -1 do
if strlen(stack[i]) > strlen(stack[i+1]) then break end
stack[i] = stack[i]..tremove(stack)
end
end
バッファーの最終的なコンテンツを取得するには、下部のすべての文字列を連結するだけです。function toString (stack)
for i=stack.n-1, 1, -1 do
stack[i] = stack[i]..tremove(stack)
end
return stack[1]
end
この新しいデータ構造を使用すると、プログラムを次のように書き直すことができます。
local s = newBuffer() while 1 do local line = read() if line == nil then break end addString(s, line.."\n") end s = toString(s)この新しいプログラムは、350 K バイトのファイルを読み取る元の時間から 40 秒から 0.5 秒に短縮されました。（
read"*all" の呼び出しの方がまだ高速で、0.02 秒でジョブが完了します。）ナイーブなアプローチの場合に何が起こるかを理解するために、読み取りの途中で buff がすでに 50 K バイトの文字列で、各行が 20 バイトであると仮定します。代入の後
buff = buff..line.."\n"
buff は 50,020 バイトの新しい文字列になり、古い文字列はガベージになります。ループのサイクルが 2 回繰り返された後、buff は 50,040 バイトの文字列になり、2 つの古い文字列が合わせて合計 100 K バイト以上のガベージになります。そのため、Lua はガベージコレクターを実行するのに適切な時機であると正しく判断し、それらの 100 K バイトを解放します。問題は、これが 2 サイクルごとに発生するため、Lua はループの完了前に 2,000 回ガベージコレクターを実行することになります。これだけの作業があっても、メモリ使用量はファイルサイズの約 3 倍になります。さらに悪いことに、各連結では文字列のコンテンツ全体（50 K バイト以上をどんどん増やしていく）を新しい文字列にコピーする必要があります。この問題は Lua に固有のものではありません。文字列が不変オブジェクトである真正的ガベージコレクションを使用した他の言語も、同様の動作を示します（最も有名な例は Java です）。
オリジナルのループでは、小さな文字列を一文字ずつアキュムレータに連結するという「線形」アプローチを採用しています。新しいアルゴリズムは、バイナリアプローチを採用することで、これを回避します。小さな文字列をまとめて結合し、しばらくすると、結合した大きな文字列をさらに大きな文字列に連結します。