18

我有大量的用户 ID（整数），可能数百万。这些用户都属于不同的组（整数组），因此有大约 1000 万个组。

为了简化我的示例并了解其本质，我们假设所有组都包含 20 个用户 ID。

我想找到所有具有 15 或更大交集的整数集对。

我应该比较每对套装吗？（如果我保留一个将用户 ID 映射到设置成员资格的数据结构，则没有必要这样做。）最快的方法是什么？也就是说，我的底层数据结构应该是什么来表示整数集？已排序的集合，未排序的——散列能以某种方式帮助吗？我应该使用什么算法来计算集合交集）？我更喜欢与 C/C++（尤其是 STL）相关的答案，但也欢迎任何更一般的算法见解。

更新 另外，请注意，我将在共享内存环境中并行运行它，因此首选干净地扩展到并行解决方案的想法。

另外，请注意，绝大多数集合对的交集大小为 0——这意味着使用将用户 ID 映射到集合以避免计算每对集合的交集可能是有利的。

4

4 回答 4

6

我会按照您的建议做：将用户映射到他们的组。也就是说，我会为每个用户保留一个组 ID 列表。然后我会使用以下算法：

foreach group:
  map = new Map<Group, int>  // maps groups to count
  foreach user in group:
    foreach userGroup in user.groups:
      map[userGroup]++
      if( map[userGroup] == 15 && userGroup.id > group.id )
        largeIntersection( group, userGroup )

假设您有G每个平均包含U用户的组，并且假设这些用户平均属于g组，那么这将在O( G*U*g ). 考虑到您的问题，这可能比在O(G*G*U).

于 2010-04-23T09:27:44.803 回答
4

如果绝大多数路口为0，则表示非空路口的数量相对较少。试试这个：

  • 开始前扔掉所有尺寸小于 15 的套装
  • 从用户 ID 计算您的查找 -> 它所属的集合列表
  • 创建一个map<pair<userset, userset>, int>
  • 对于每个用户，增加（在必要时创建之后）n*(n-1)/2该映射的条目，其中 n 是用户所属的集合数。
  • 完成后，扫描地图以查找值大于 15 的条目。

与计算每个交叉点的简单方法相比，它将使用更多的内存。事实上，它会遇到可行的情况：如果每个集合平均只与其他 10 个相交，也许在非常小的交叉点，那么地图需要 50M 条目，这开始占用大量 RAM。它也是可悲的缓存不友好。

它可能比执行所有集合交集更快，因为 O(n^2) 项与非空交集的数量和每个用户所属的组的数量有关，而不是与集合的数量有关。

由于巨大地图上的竞争，并行化并非易事。但是，您可以将其分片到每个线程的映射中，并定期给一个线程一个新的、空的映射，并将迄今为止的结果添加到总结果中。然后，不同的线程大部分时间完全独立运行，每个线程都有一个要处理的用户列表。

于 2010-04-23T09:17:43.970 回答
2

我应该比较每对套装吗？（如果我保留一个将用户 ID 映射到设置成员资格的数据结构，则没有必要。）

为了计算交集度，你仍然需要访问用户拥有的其他组，仍然是三次方。您可以有一个哈希表或其他稀疏数组来计算，但它最多仍需要为每个用户所在的每对组的每个用户增加一个增量。如果您在 G 个组中有 N 个用户，平均每个用户有 S 个用户group 和 T 每个用户所在的组数，如果你有一个用户到组的索引，你有 G G S/2 用于比较每对组和 N T T。T = G S/N，所以 N T T=G G S序号；对于 S = 20 和数百万的 N 应该有优势。不幸的是，您还需要至少 G*G 存储来存储交集计数（对于 4 位非稀疏计数器，需要 25 TB 左右），并且必须确保结构可以并行递增。

对于 1000 万个 20 个组中的 100 万个用户，一个用户在给定组中的概率非常近似为 2e-6，两个组共享用户的概率为 40e-6，因此 25TB 降为 1GB数据，因此对于普通大小的计算机上的稀疏数组来说并非不可能。

但是，将 20 个元素的集合与 15 个共同元素进行比较具有更明显的优化

  • 如果对组进行了排序，则不需要工作存储，只需直接输出输入组之间的差异程度即可。
  • 大多数内存访问在连续的内存区域中是线性的，结果仅取决于被比较的两组，而不是依赖于整个数据集的总和。随机访问主存比线性访问慢得多。使用总线锁随机更改主内存比在无需锁定总线的情况下访问缓存要慢几个数量级（尽管如果每个内核有几个 GB，则可以使用 user->group 方法而无需进行任何同步）。
  • 只需要计算集合之间不同的5个元素；如果数据是随机的，那么大多数集合将是不相交的，因此访问的元素的平均数量较小。
  • You can quickly discount certain groups by treating the difference as a distance (if A is 11 different from B, and C is 5 different from B, then C is between 6 and 16 different from A, so can be discounted without comparing A and C directly). Since most the sets are completely disjoint, this won't gain you much though.

There is also the option of a hybrid approach, using the user->group map to prune the set of group to group comparisons to be made. This has the advantage of not requiring incrementing of a shared data structure:

  • for each pair of groups that a user is in, add that pair to the list to investigate.
  • sort the list of pairs of groups with at least one user in common.
  • the number of times each pair occurs in the list is the number of users they have in common.

Using merge sort, this is very each to parallelise into pure streaming units. You would be sorting around 20*200*10 million/2 = 20 billion group ID pairs (each group of 20 users times the number of groups each user is in/2).

于 2010-04-23T10:08:34.040 回答
1

一种方法是将您的问题视为度量空间 半径搜索问题，其中距离函数是不匹配条目的数量，半径是r = max(number of elements in sets) - number of equal。需要过滤找到的元素以查看 Set 中是否有足够的值。因此，除非有人提出可以直接使用的度量函数，否则这个解决方案有很多限制。

度量搜索的数据结构之一是可用于字符串相似性搜索的BK-Tree 。

您的问题的候选者是 VP-tree 和 M-Trees。

当您在 O(log n * n) 中构建树并在 O 中搜索时，度量树的最坏情况是 O(n^2) (n^2)。

除此之外，实际的运行时复杂性取决于执行搜索时修剪度量树的子树的能力。在度量树中，如果枢轴元素到搜索元素的距离大于枢轴元素的半径（至少是祖先到枢轴元素的最大距离），则可以跳过子树。如果您的条目集相当分散，则整体运行时间将由度量树 O(log n * n) 的构建时间支配。

于 2010-04-23T09:27:13.997 回答