luaのtable処理
4827 ワード
luaの全体的な効率は高く,その中でtableが実現したのは巧みにこの効率に大きく貢献している.
luaのtableは配列とマッピングテーブルの二重機能として機能するので,実現時にこれらを考慮し,tableが配列をして使用する際にできるだけ効率的な罰を少なくする.
luaはそうしました.1つのtableを配列セグメントとhashセグメントの2つの部分に分けます.数値keyは一般的に配列セグメントに配置され、初期化されていないkey値はすべてnilに設定されます.数値keyがあまりにも離散している場合、部分的に大きい数値keyはhashセグメントに移動されます.この分割線は配列セグメントの利用率が50%を下回らないことを基準とする.0と負数をkeyするときはhashセグメントに必ず入れます.
stringとnumberは共にhashを行い,それぞれアルゴリズムがあるがhashの結果はいずれも数値セグメントにある.hashセグメントは、すべての値がテーブルに存在する閉ハッシュ法を採用する.hashが衝突した場合、余分なデータは空きスロットに記録され、スペースを追加して保存されません.テーブル全体が満たされるとhashセグメントが拡大し、すべてのセグメント内のデータが再hashされ、再hashされると衝突が大幅に減少します.
このtableの実装戦略は,まず検索効率を保証する.tableを配列として使用する場合、C配列と同様に効率的になります.hashセグメントの値の場合、検索はほとんどhash値を計算するプロセスであり(stringのhash値は事前に計算されて保存されている)、衝突したときにのみわずかな追加の検索時間があり、空間も無駄にならない.hashテーブルがいっぱいの場合、挿入は衝突しやすく、この場合、テーブルに空のスロットを見つける必要があります.luaはtableの構造において,一方のポインタが一方から他方へ順次挿入されて空溝の検索を解決することを記録した.各スロットポイントは、nextポインタを記録して衝突したkeyの関連性を保存する.
全体的に、この解決方法はとてもいいです.
マッピングテーブルの実装については,この間も個別の研究を行ったことがある.伝言帳に貼る:义齿
ableのコンストラクタとはtableを作成する式を指します.コンストラクタを評価するたびに、新しいtableが作成されます.コンストラクタは、空のテーブルまたは初期ドメインを持つテーブルを作成できます.コンストラクタの一般的な構文は、次のとおりです.
tableconstructor::= ‘{‘ [fieldlist] ’}’
fieldlist::= field {fieldsep field} [fieldsep] field::= ‘[‘ exp ‘]’‘=’exp | exp | Name ‘=’exp | exp fieldsep::= ‘,’ | ‘;’
[exp 1]=exp 2のような各形式のドメインは、新しいテーブルにエントリを追加します.キーはexp 1で、値はexp 2です.形式name=expのドメインは形式["name"]=expのドメインに等しい.最後に,exp形式のドメインは[i]=expに等しく,iは1からの連続整数であり,他の形式のドメインはiのカウントに影響を及ぼさない.例:
a = { [f(1)] = g; "x", "y"; x = 1, f(x), [30] = 23; 45 }
に等しい
do local t = {} t[f(1)] = g t[1] = "x"t[2] = "y"t.x = 1 t[3] = f(x) t[30] = 23 t[4] = 45 a=t
end
-- 1st exp -- 2nd exp
-- t["x"] = 1 -- 3rd exp
-- 4th exp
テーブルの最後のドメインの形式が関数呼び出し式または変数式である場合、この式が返すすべての値は、前のドメインに続いてテーブルに入ります(3.4.9参照).
ドメインリストの最後にオプションの区切り記号を追加できます.これは、コードのマシン生成を容易にするためです.
長さオペレータは1元オペレータ#です.文字列の長さは、そのバイト数(すなわち、各文字が1バイトである場合の従来の長さの意味)です.
プログラムはlenメタメソッド(2.4参照)は、文字列以外の数値の長さを求める動作を修正する.
定義されていない限りlenメタメソッド.そうでなければ、テーブルがシーケンステーブルである場合にのみ、その長さが明確になります.すなわち、テーブルの正の整数キー値は{1..n}です.この場合、nはテーブルの長さです.テーブルが
{10,20,nil,40}このようなテーブルは、キー4には値があるが、キー3には値がないため、シーケンステーブルではない.(この表は{1..n}のような正
整数キー値.)数値タイプ以外のキーは、テーブルがシーケンステーブルであるかどうかに影響しません.
Lua 5.1では、長さオペレータ「#」は、配列または線形テーブルの最後のインデックス値を返すために使用されます.実際のプロジェクトでは、このオペレータを使用して配列または線形テーブルの長さを取得することがよくあります.ただし、このオペレータを使用すると、次のコードのようなトラップが存在します.
luaのtableは配列とマッピングテーブルの二重機能として機能するので,実現時にこれらを考慮し,tableが配列をして使用する際にできるだけ効率的な罰を少なくする.
luaはそうしました.1つのtableを配列セグメントとhashセグメントの2つの部分に分けます.数値keyは一般的に配列セグメントに配置され、初期化されていないkey値はすべてnilに設定されます.数値keyがあまりにも離散している場合、部分的に大きい数値keyはhashセグメントに移動されます.この分割線は配列セグメントの利用率が50%を下回らないことを基準とする.0と負数をkeyするときはhashセグメントに必ず入れます.
stringとnumberは共にhashを行い,それぞれアルゴリズムがあるがhashの結果はいずれも数値セグメントにある.hashセグメントは、すべての値がテーブルに存在する閉ハッシュ法を採用する.hashが衝突した場合、余分なデータは空きスロットに記録され、スペースを追加して保存されません.テーブル全体が満たされるとhashセグメントが拡大し、すべてのセグメント内のデータが再hashされ、再hashされると衝突が大幅に減少します.
このtableの実装戦略は,まず検索効率を保証する.tableを配列として使用する場合、C配列と同様に効率的になります.hashセグメントの値の場合、検索はほとんどhash値を計算するプロセスであり(stringのhash値は事前に計算されて保存されている)、衝突したときにのみわずかな追加の検索時間があり、空間も無駄にならない.hashテーブルがいっぱいの場合、挿入は衝突しやすく、この場合、テーブルに空のスロットを見つける必要があります.luaはtableの構造において,一方のポインタが一方から他方へ順次挿入されて空溝の検索を解決することを記録した.各スロットポイントは、nextポインタを記録して衝突したkeyの関連性を保存する.
全体的に、この解決方法はとてもいいです.
マッピングテーブルの実装については,この間も個別の研究を行ったことがある.伝言帳に貼る:义齿
ableのコンストラクタとはtableを作成する式を指します.コンストラクタを評価するたびに、新しいtableが作成されます.コンストラクタは、空のテーブルまたは初期ドメインを持つテーブルを作成できます.コンストラクタの一般的な構文は、次のとおりです.
tableconstructor::= ‘{‘ [fieldlist] ’}’
fieldlist::= field {fieldsep field} [fieldsep] field::= ‘[‘ exp ‘]’‘=’exp | exp | Name ‘=’exp | exp fieldsep::= ‘,’ | ‘;’
[exp 1]=exp 2のような各形式のドメインは、新しいテーブルにエントリを追加します.キーはexp 1で、値はexp 2です.形式name=expのドメインは形式["name"]=expのドメインに等しい.最後に,exp形式のドメインは[i]=expに等しく,iは1からの連続整数であり,他の形式のドメインはiのカウントに影響を及ぼさない.例:
a = { [f(1)] = g; "x", "y"; x = 1, f(x), [30] = 23; 45 }
に等しい
do local t = {} t[f(1)] = g t[1] = "x"t[2] = "y"t.x = 1 t[3] = f(x) t[30] = 23 t[4] = 45 a=t
end
-- 1st exp -- 2nd exp
-- t["x"] = 1 -- 3rd exp
-- 4th exp
テーブルの最後のドメインの形式が関数呼び出し式または変数式である場合、この式が返すすべての値は、前のドメインに続いてテーブルに入ります(3.4.9参照).
ドメインリストの最後にオプションの区切り記号を追加できます.これは、コードのマシン生成を容易にするためです.
長さオペレータは1元オペレータ#です.文字列の長さは、そのバイト数(すなわち、各文字が1バイトである場合の従来の長さの意味)です.
プログラムはlenメタメソッド(2.4参照)は、文字列以外の数値の長さを求める動作を修正する.
定義されていない限りlenメタメソッド.そうでなければ、テーブルがシーケンステーブルである場合にのみ、その長さが明確になります.すなわち、テーブルの正の整数キー値は{1..n}です.この場合、nはテーブルの長さです.テーブルが
{10,20,nil,40}このようなテーブルは、キー4には値があるが、キー3には値がないため、シーケンステーブルではない.(この表は{1..n}のような正
整数キー値.)数値タイプ以外のキーは、テーブルがシーケンステーブルであるかどうかに影響しません.
Lua 5.1では、長さオペレータ「#」は、配列または線形テーブルの最後のインデックス値を返すために使用されます.実際のプロジェクトでは、このオペレータを使用して配列または線形テーブルの長さを取得することがよくあります.ただし、このオペレータを使用すると、次のコードのようなトラップが存在します.
local a = {} a[1000] = 1 print(#a)
?
Lua , nil。Lua nil 。 “ ” , nil , nil 。 a[1] = nil, , 0。 , table , 。 nil table, ? table.maxn, table , :
local a = {} a[1000] = 1 print(table.maxn(a)) -->1000
Lua ,table “ ”, “ ”, 。 table , ( )。table “ ” , {}。
table , table table , :
local a = {} -- table, a a["x"] = 10 local b = a -- b a table print(b["x"]) b["x"] = 20 print(a["x"]) b = nil -- a table -- :print(b["x"]) print(a["x"]) a = nil -- table