2

我最近偶然发现了一个问题

当每个序列可以有重复的数字并且大小相当大（接近一百万）并且处理的数据类型是Long时，如何找到两个序列的交集。

我考虑过排序和查找交集，这不是一个可行的解决方案我什至考虑过哈希表它不起作用，因为空间考虑必须是最佳的

有人可以建议处理它的更好方法吗？

感谢您阅读帖子

4

4 回答 4

2

该问题声称“排序和查找交集......不是一个可行的解决方案”。但是，从编码的易用性和清晰性的角度来看，排序是最好的解决方案之一。对于任何一次性问题，花 10 分钟编写排序解决方案比花 15 分钟编写散列解决方案或半小时编写特殊树程序更合理。

在我的旧 PC（AMD Athlon 5000，约 2GHz）上，使用下面显示的 python 代码对一百万个 double 进行排序大约需要 1.3 秒，并且可能比当前处理器快四到五倍。在时间 O(n lg n) 中对两个数组进行排序，然后根据问题的要求在时间 O(n) 中查找匹配项，在现代 PC 上可能需要一两秒钟。

In [237]: import random

In [238]: v = [random.random() for i in range(1000000)]

In [239]: %time u = sorted(v)
CPU times: user 1.32 s, sys: 0.00 s, total: 1.32 s
Wall time: 1.33 s

请注意，问题 #8630965指的是在 1.168 秒内对一百万个浮点值进行排序。

于 2013-04-06T04:26:57.560 回答
1

假设 long 是固定大小，比如 64 位。计划一棵深度最大为 64 的部分二叉树。对于第一个序列中的每个数字，您将生长这棵树。所有叶子都出现在深度 64。每个叶子都有两个整数，它们是引用两个序列的计数器。

for each number n in the first list
    current_node = root
    for i ranging from 1 to 64
        if the i-th bit of n is zero
            grow/traverse edge labeled 'zero' from current_node
        else
            grow/traverse edge labeled 'one' from current_node
        set current_node to be at end of this edge
    if the current_node (now at depth 64) is brand new
        set the node's first counter to 1; second counter to zero
    else
        increment current_node's first counter by 1

第二部分是处理第二个列表，而是更新第二个计数器。如果需要，您也可以跳过创建新节点，因为那里不会有任何交叉点。然后遍历整个树并查看两个计数器都非零的位置。

于 2013-04-05T23:37:10.590 回答
1

我认为每个列表有 2M 个条目的哈希表（因此哈希表负载保持相当低，在 50% 或更低）是一个不错的选择。如果您使用最简单的实现，则速度快，不是太大，只有 2M*4B（您的 long 是 4 字节长，对吗？）。

如果列表中的唯一值很少，排序/搜索树将比哈希表更紧凑，但如果唯一数字很多（您需要树中的子/父指针），它将比哈希表大节点，这就是开销）。

统计数据是什么？

于 2013-04-05T23:37:59.087 回答
0

对我来说，问题归结为：

  • 使用某种数据结构表示稀疏的第一个输入
  • 将第二个输入作为键遍历它，进入上一步计算的数据结构。

我最初的想法也是一个哈希表。但是我们需要为每个数字一个节点。另一位作者已经有了这个想法。

我的第二个想法是 B+ 树。我们可以使用这棵树映射一个稀疏集。叶子可以包含一系列 nos ......这样，我们可以在寻找与第二个输入集的交集时消耗更多的 cpu 来搜索叶子。您确实支付了内部节点中 b+ 树索引的成本。假设我们不在树中存储重复项……不需要交集。我们可以使用基于位的存储来优化叶子以减少空间。

于 2013-04-06T00:13:49.937 回答