Lua によるプログラミング: 11.2

この初版は Lua 5.0 に合わせて書かれました。依然として以降のバージョンとの関連性は大きいですが、若干の違いがあります。
第 4 版は Lua 5.3 を対象としており、Amazon やその他の書店でご購入いただけます。
この本を購入することで、Lua プロジェクトを支援することもできます。

Lua によるプログラミング

第 II 部。テーブルとオブジェクト第 11 章。データ構造

11.2 – 行列と多次元配列

Lua で行列を表すには、主に 2 つの方法があります。1 つ目は配列の配列、つまり各要素が別のテーブルであるテーブルを使用することです。たとえば、N 行 M 列のゼロ行列を作成するコードを以下に示します。

    mt = {}          -- create the matrix
    for i=1,N do
      mt[i] = {}     -- create a new row
      for j=1,M do
        mt[i][j] = 0
      end
    end

テーブルは Lua のオブジェクトであるため、行列を作成するには各行を明示的に作成する必要があります。明らかに、C や Pascal のように単に行列を宣言するよりも冗長になります。一方で、これにより柔軟性が向上します。たとえば、前の例の行を変えて三角行列を作成できます。

      for j=1,M do

      for j=1,i do

このコードでは、三角行列は元の行列の半分のメモリしか使用しません。

Lua で行列を表す 2 つ目の方法は、2 つのインデックスを 1 つにまとめることです。2 つのインデックスが整数の場合、1 つ目に定数を乗算し、2 番目インデックスを加算できます。この方法では、以下のコードによって N 行 M 列のゼロ行列を作成できます。

    mt = {}          -- create the matrix
    for i=1,N do
      for j=1,M do
        mt[i*M + j] = 0
      end
    end

インデックスが文字列の場合、その間を区切る文字で 2 つのインデックスを連結して 1 つのインデックスを作成できます。たとえば、文字列インデックス s と t を持つ行列 m を、m[s..':'..t] のコードでインデックスできます。ただし、s と t の両方にコロンが含まれていてはなりません（そうでないと、（"a:"、"b"）と（"a"、":b"）のようなペアが単一のインデックス "a::b" にまとめられてしまいます）。疑問がある場合は、\0 などの制御文字を使用してインデックスを区切ることができます。

アプリケーションでは、ほとんどの要素が 0 または nil の行列である、「スパース行列」がよく使用されます。たとえば、グラフを隣接行列で表すことができます。この行列は、ノード m と n がコスト x で接続されている場合にのみ、位置 m, n の値に x が含まれます。これらのノードが接続されていない場合、位置 m, n の値は NIL になります。約 5 つの近接ノードを持つ 10000 個のノードを持つグラフを表すには、1 億個のエントリ（10000 列と 10000 行の正方行列）を持つ行列が必要になりますが、およそ 5 万個のエントリのみが NIL 以外になります（各行の 5 個の NIL 以外の列が、各ノードの 5 つの近接ノードに対応します）。多くのデータ構造に関する書籍では、400 MB のメモリを無駄にせずにスパース行列を実装する方法について詳細に説明されていますが、Lua でプログラミングする場合にはそのような手法は必要ありません。配列はテーブルで表されるため、本質的にスパースです。最初の表現方法（テーブルのテーブル）の場合、約 5 つの要素を持つ 10000 個のテーブルが必要であり、合計エントリ数は 50000 個になります。 2 番目の表現方法の場合、50000 個のエントリを持つ単一のテーブルを持つことになります。どちらの表現方法であっても、NIL 以外の要素分のスペースのみが必要になります。