与输入

的大序列打交道时，选择什么我最近遇到一个问题与输入

如何找到两个序列的路口时，每个序列可以有重复号码和规模是相当大的（接近一百万）处理的数据类型为Long。

我想到了排序，并找到交集这不是一个可行的解决方案我甚至想过哈希表中这是行不通的空间考虑必须是最佳

能有人建议什么将是更好的办法处理它？

感谢您阅读帖子

2013-04-05 linux developer

正在@linuxdeveloper然后gnu排序可以工作，如果你有足够的磁盘空间。然后，您可以执行您声明可以执行的已排序序列的交集。 – Paddy3118 2013-04-06 12:27:22

这个问题声称“排序和发现相交...不是一个可行的解决方案”。但是，从编码的简易性和清晰度的角度来看，排序是最好的解决方案之一。对于任何一次性问题，花10分钟时间写分类解决方案比花15分钟写一个哈希解决方案更合理，或者花半小时写一个特殊的树程序。

使用下面显示的python代码排序一百万双，我的旧PC（AMD Athlon 5000，大约2GHz）大约需要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

请注意，question #8630965是指在1.168秒内对100万个浮点值进行排序。

来源

2013-04-06 04:26:57

假设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-05 23:37:10 dan

我认为每个列表有2M个条目的哈希表（所以哈希表加载保持合理的低，在50％或更低）是一个不错的选择。如果使用最简单的实现方式，那么快速，不是非常大，只有2M * 4B（你的长整型是4字节长，对吗？）。

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

什么是统计数字？

来源

2013-04-05 23:37:59

对我来说，问题归结为：

使用某种数据结构代表稀疏第一输入
与第二输入作为密钥到数据结构在现有步骤中计算遍历它。

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

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

来源

2013-04-06 00:13:49 lsk

回答

相关问题