c++ - 如何执行高效的集合交集操作？

Question

我得到了称为 token 的元素。它们中的每一个都是某种关联容器(不一定是标准容器之一)。我得到了某种类型的容器存储，它存储 token (不一定是 std 容器之一)。存储 是一组 token 。
我需要能够通过指定的键和指定的比较器对 token 值的 token 集(storage)执行交集操作。作为该操作的结果，我想获得另一组 token (另一个 storage )。

伪代码中的用例:

  if ( (storage0[key1]==storage1[key1])[key2]<storage1[key2] )
    ...

我正在寻找一种高效的算法。
注意:我得到了几十个代币。
问题:
1) 如何组织存储？
2)如何实现交集运算？

更新一些解释:
token 是一组(键，值)对。存储是一组(键，值)对的集合

我需要相交(P1,K1,P2,K2,cmp)
P1 - 第一个存储
P2 - 二次存储
K1 - 第一次存储的 key
K2 - 二次存储的 key
cmp - 类似 cmp(value,value) 的比较函数，返回 true 或 false

相交应该穿过P1的每个元素e1，并穿过P2的每个元素e2并提取满足 cmp(e1[K1],e2[K2]) 的那些元素((键，值)对)

Answer 1

Inverted index有效地处理交集，所以你可以做类似的事情。

想法是:每个集合实际上是一个列表，具有高效的 getFirstAfter(key) 函数 - 它返回 key 之后的第一个标记。对于每个集合 - 您需要检查相关元素是否在其中 - 如果不存在 - 前进到集合中的下一个元素。

(*) 请注意，此算法中枚举了标记

(*)假设 T 包含您想要相交的所有列表 [算法有效地相交超过两个列表]

伪代码:

lastTok <- 0 //the first token in the collection
currSet <- 0 //the first set 
while (lastTok != infinity):
  if (currSet > T.last): //if we have passed the last set
     insert lastTok into result
     currSet <- 0
     lastTok <- lastTok + 1
     continue
  currentToken<- T[currSet].getFirstAfter(lastTok-1)
  if (currentToken!= lastTok):
     lastTok<- currentToken
     currSet <- 0
  else: 
     currSet <- currSet + 1

该算法假定有效的 getFirstAfter() 可以为您提供符合该术语的第一个文档，并且其 docId 大于指定参数。如果没有，它应该返回无穷大。

如果对术语进行排序，使最稀有的术语排在最前面，则该算法将是最有效的。

该算法最多可确保 #docs_matching_first_term * #terms 次迭代，但实际上 - 通常迭代次数要少得多。

更多信息可以在 this lecture notes 中找到幻灯片 11-13 [讲座首页的版权]