4

2 つの ets テーブル間の相互要素を効率的に見つける方法を知りたいです。ETS および QLC モジュールを試しましたが、その方法を見つけることができませんでした。[bag] オプションで ets を使用しています。これは、複数の値があることを意味します。同じキー。

最速かつ最も効率的なソリューションを探しています。

4

2 に答える 2

1

テーブルのサイズ、コンテンツの構造、実行コンテキスト (並列処理?、頻度...) について何も知らないため、あなたの質問に答えるのは難しいです。

lists:filter/2 で基本的な解決策をテストしましたか?

1> ets:new(t,[bag,named_table]).
t
2> ets:new(s,[bag,named_table]).
s
3> ets:insert(t,[{1,a},{1,b},{2,c}]).
true
4> ets:insert(s,[{3,a},{1,b},{2,d}]).
true
5> lists:filter(fun(X) -> lists:member(X,ets:tab2list(s)) end, ets:tab2list(t)).
[{1,b}]
6>

(私が推測するに) テーブルが大きく、コンテンツが複雑な場合は、キーがテーブルの完全なレコードである新しい ets set テーブルを意図的に作成し、関数 ets を使用して 2 番目のテーブルのレコードをフィルター処理することができます。 :insert_new/2 を述語として使用すると、作成のオーバーヘッドは、要素の検索と比較して価値がある場合があります。

6> ets:new(r,[set,named_table]).                                                
r
7> lists:foreach(fun(X) -> ets:insert(r,{X}) end,ets:tab2list(s)).
ok
8> ets:tab2list(r).
[{{3,a}},{{2,d}},{{1,b}}]
9> lists:filter(fun(Y) -> ets:insert_new(r,{Y}) == false end,ets:tab2list(t)).
[{1,b}]
10>

この例では、シェルで簡単にデモを作成するために ets:tab2list/1 を使用しましたが、ets テーブルをトラバースする任意の方法を使用できます。

于 2015-08-06T14:04:41.323 に答える
0

1 つのテーブルを繰り返し、要素ごとに 2 番目のテーブルにあるかどうかを確認できます。を使用ets:selectすると、コピーされるデータを減らすことができます。

たとえば、次の表を作成するとします。

1> Tab = ets:new(foo, [bag]).
2> [ets:insert(Tab, {X, Y}) || X <- lists:seq(1,10), Y <- lists:seq(1, 10)].

ペア{3, 4}がテーブルにあるかどうかを確認するには、次のようにします。

3> ets:select(Tab, [{{3, 4}, [], [true]}]).
[true]

ペアがテーブルにない場合は、空のリストが表示されます。

4> ets:select(Tab, [{{3, 11}, [], [true]}]).
[]

パフォーマンスについては 100% 確信が持てませんが、キーを一致させているので、ルックアップは O(M) になると思います。ここで、M は同じキーの下にある項目の平均数です。

最後のピースは、別のテーブルからすべてをフェッチし、ets:select繰り返し呼び出すことです。最初のテーブルからすべてのデータをフェッチする必要があるため、ets:tab2listすべてのデータがコピーされることに注意してください。簡単な例を次に示します。

5> Tab2 = ets:new(bar, [bag]),
[ets:insert(Tab2, {X, Y}) || X <- lists:seq(7,12), Y <- lists:seq(7, 12)].

% iterate Tab2, return only tuples which exist in Tab
6> [Element || Element <- ets:tab2list(Tab2), ets:select(Tab, [{Element, [], [true]}]) =:= [true]].

両方のテーブルが非常に大きい場合は、すべてのデータを一度にコピーすることを避けるために、、、ets:firstおよびets:nextを手動で繰り返すことを検討してください。ets:lookup

もちろん、どのアプローチが自分のケースに最も適しているかを測定して検証することをお勧めします。

于 2015-08-07T14:11:50.937 に答える