この初版はLua 5.0向けに書かれています。後のバージョンにも概ね該当しますが、いくつかの違いがあります。
第4版はLua 5.3を対象としており、Amazonなどの書店で入手できます。
本書をご購入いただくと、Luaプロジェクトの支援にもなります。

	Luaプログラミング
	第II部. テーブルとオブジェクト 第11章. データ構造

11.6 – 文字列バッファ

例えば、ファイルを行ごとに読み込んで文字列を少しずつ構築しているとします。典型的なコードは次のようになります。

    -- WARNING: bad code ahead!!
    local buff = ""
    for line in io.lines() do
    buff = buff .. line .. "\n"
    end

なぜでしょうか？ Luaは真のガベージコレクションアルゴリズムを使用しています。プログラムが過剰なメモリを使用していると検出すると、すべてのデータ構造を調べ、使用されていない構造（ガベージ）を解放します。通常、このアルゴリズムは良好なパフォーマンスを発揮しますが（Luaが高速なのは偶然ではありません）、上記のループはアルゴリズムの最悪のケースを引き起こします。

何が起こるかを理解するために、読み込みループの途中であると仮定しましょう。buffは既に50KBの文字列であり、各行は20バイトです。Luaがbuff..line.."\n"を連結すると、50,020バイトの新しい文字列が作成され、buffからこの新しい文字列に50KBがコピーされます。つまり、新しい行ごとに、Luaは50KBのメモリを移動し、それが増え続けます。100行（わずか2KB）を読み込んだ後、Luaは既に5MB以上のメモリを移動しています。さらに悪いことに、代入後

        buff = buff .. line .. "\n"

この問題はLua特有のものではありません。真のガベージコレクションを備え、文字列が不変オブジェクトである他の言語でも同様の動作が見られます。最も有名な例はJavaです。（Javaは問題を軽減するためにStringBuffer構造を提供しています。）

続ける前に、私が言ったことにもかかわらず、この状況は一般的な問題ではないことを注意しておきましょう。小さな文字列の場合、上記のループは問題ありません。ファイル全体を読み込むには、一度に読み込む"*all"オプションを使用します。しかし、単純な解決策がない場合もあります。その場合、唯一の解決策は、より効率的なアルゴリズムです。ここでは、その一つを紹介します。

元のループは問題に対して線形的なアプローチを取り、小さな文字列を1つずつアキュムレータに連結していました。この新しいアルゴリズムはこれを避け、代わりにバイナリアプローチを使用します。複数の小さな文字列を連結し、場合によっては、結果として得られる大きな文字列をさらに大きな文字列に連結します。アルゴリズムの中心は、既に作成された大きな文字列を底に保持するスタックであり、小さな文字列は上から入ります。このスタックの主要な不変条件は、（少なくともプログラマーの間では）有名な*ハノイの塔*の不変条件に似ています。スタック内の文字列は、短い文字列の上に配置することはできません。新しい文字列が短い文字列の上にプッシュされると、（そしてその場合にのみ）アルゴリズムは両方を連結します。この連結により、より大きな文字列が作成され、前の階層の隣接する文字列よりも大きくなる可能性があります。それが発生した場合、それらも結合されます。これらの連結は、ループがより大きな文字列またはスタックの底に到達するまでスタックを下っていきます。

    function newStack ()
      return {""}   -- starts with an empty string
    end
    
    function addString (stack, s)
      table.insert(stack, s)    -- push 's' into the the stack
      for i=table.getn(stack)-1, 1, -1 do
        if string.len(stack[i]) > string.len(stack[i+1]) then
          break
        end
        stack[i] = stack[i] .. table.remove(stack)
      end
    end

この新しいデータ構造を使用すると、プログラムを次のように書き直すことができます。

    local s = newStack()
    for line in io.lines() do
      addString(s, line .. "\n")
    end
    s = toString(s)

実際には、io.read("*all")を呼び出すと、io.readはここで紹介したデータ構造とまったく同じものをC言語で実装したものを使用します。Luaライブラリの他のいくつかの関数もこのC実装を使用します。これらの関数の1つはtable.concatです。 concatを使用すると、すべての文字列をテーブルに収集し、それらをすべて一度に連結できます。 concatはC実装を使用しているため、巨大な文字列の場合でも効率的です。

concat関数は、文字列の間に挿入される区切り文字であるオプションの2番目の引数を受け入れます。この区切り文字を使用すると、各行の後に改行を挿入する必要はありません。

    local t = {}
    for line in io.lines() do
      table.insert(t, line)
    end
    s = table.concat(t, "\n") .. "\n"

    table.insert(t, "")
    s = table.concat(t, "\n")

Copyright © 2003–2004 Roberto Ierusalimschy. All rights reserved. 著作権 © 2003–2004 Roberto Ierusalimschy. 無断転載禁止。