erlang - Erlang - ETS 表之间的比较

Question

我们想知道如何有效地找到两个 ets 表之间的相互元素，我们尝试了 ETS 和 QLC 模块，但找不到方法，我们在 [bag] 选项上使用 ets，这意味着我们有几个值同一把钥匙。

我们正在寻找最快和最有效的解决方案。

Answer 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 过滤你的第二个表的记录: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 来轻松地在 shell 中进行演示，但是可以使用任何遍历 ets 表的方法。

Answer 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一次复制所有数据。

当然，最好衡量和验证哪种方法最适合您的情况。