Lua の配列のサイズ

Programming in Lua (PiL) を読み始めた。今のところの印象としては Lua は C へのインタプリタの埋め込みのしやすさという点は Tcl に似ていて、他のところは JavaScript に似ているという感じかもしれない。まあ JavaScript は殆ど使ったことが無いのだけど。

さて Lua には table 型という連想配列の型が用意されていて、普通の配列もそれを使って済ませる。つまり添字が整数なだけの連想配列だ。この発想は多分 JavaScript に似ている [1]。でも JavaScript では添字はすべて文字列扱いになるようだけど Lua では数字の添字と文字列の添字は区別される。
連想配列に # という演算子を使うとその配列の普通の配列としての大きさを調べることができる。

> a = {} -- table を作る
> a[1] = "hello"
> a[2] = "howdy"
> print(#a)
2

じゃあ整数以外の余計なエントリがあった場合はサイズはどうなるのか？と思ってやってみた。

> a["hello"] = 1
> print(#a)
2
> a[1.5] = "Guten Tag"
> print(#a)
2
> a["3"] = "Buenos dias"
> print(#a)
2

変わらない。なので整数とみなされる添字以外はサイズに数えられないのだ。

さらに PiL には以下のような例がある。

a = {}
a[10000] = 1

これのサイズを # 演算子で求めると 0 が返るのだ。いわく配列の終点を識別するのに nil を使う。なのでこの場合は a[1] が未定義（Lua は慣例的に配列が1オリジン！）で nil なのでそこで数えるのをやめてサイズ 0 の配列とみなす。

この記述を素朴に解釈すると配列が大きくなればなるほどサイズの算出にかかる時間は増大するように思える。本当だろうか。やってみた。

a = {}; b = {}
for i=1,2000000 do a[i]=i end
for j=1,4000000 do b[j]=j end

point1 = os.clock()

  print(#a)

point2 = os.clock()

  print(#b)

point3 = os.clock()

print(point2 - point1)
print(point3 - point2)

このコードを3回実験してみた結果は以下の通り。

2000000
4000000
0.96
1.51

2000000
4000000
0.93
1.46

2000000
4000000
0.86
1.34

大きいほうが時間がかかる。あまり凝ったことはしていないようだ。

[1] http://www.tokumaru.org/JavaScript/index.htm