0

我已经设置了 A 和 B

集合A有1亿个数字（每个数字是64bit）

set B有1亿个数字（每个数字是64位）

两组大小相同。

数据都是随机的，没有排序。

你会推荐什么算法来找到两组之间的重复数字？

（我可以使用大约 4G 内存和 100~200 Gb 的磁盘空间）

先感谢您。

4

4 回答 4

2

假设第一个 arr 是 arr1，第二个是 arr2；

sort arr1//max O(n*log_n)
for(int i = 0; i < arr2.length; i++){ //n
    binarySearch(arr1, arr2[i]) //log_n
}

总共 O(n logn)

于 2013-04-14T19:40:16.843 回答
2

就执行时间（但不幸的是，编程时间）而言，可能最便宜的是将 A 中的元素放入一个开放寻址的哈希表中，然后在哈希表中查找 B 的每个元素。如果你能想出一个合理的散列函数（更多见下文），那么你可以使用负载因子约为 60% 的简单线性散列，这意味着你的表将占用 10 8 * (1/.6) * 8 字节，或者大约 1.3 GB。（我不知道在标准库中提供开放地址哈希表的语言；C++ 的 unordered_sets 是用存储桶链实现的，如果单个元素不是单独的存储分配，这只会稍微多一点开销。一个好的分配器可能会使这变得可行。）

幸运的是，开放寻址的线性探测哈希表很容易编写，尤其是在您不需要处理删除元素的情况下。你只有两个问题：

  1. 您需要保留一些值，这意味着“未占用”。

  2. 你需要一个好的散列函数。或者至少是一个合理的。

如果您的数据真正随机分布在 64 位空间中，那么散列很简单；您只需要将数据减少到所需的大小。一种简单的方法是使用模运算符，即使数据不是完全随机分布的，只要您安排将表大小设为素数（166666783 大约是 60% 负载的正确大小）具有 1 亿个元素的因子）。

找到一个意味着“未占用”的值可能会更棘手。您可能已经知道一个值是不可能的（可能是 value 0）。如果没有，您可以选择一个随机的 64 位数字；很有可能它不存在于您的数据集中，但如果它存在，您有一个简单的备份：不要将它放入哈希表中，并B对照它检查每个值。

伪 C++ 代码，基于上述描述，包括提到的“无价值”hack：

class HundredMillionSet {
  std::vector<uint64_t> h_;
  const size_t size_
  const uint64_t no_value_;
  bool has_no_value_;
  HundredMillionSet(size_t size, uint64_t no_value)
      : h_(size, no_value), size_(size), no_value_(no_value), has_no_value_(false) {}

  void insert(uint64_t v) {
    if (v == no_value_) { has_no_value_ = true; }
    else {
      size_t i = v % size_;
      while (h_[i] != no_value_) {
        if (++i == size_) i = 0;
      }
      h_[i] = v;
    }
  }

  bool check(uint64_t v) {
    if (v == no_value_) return has_no_value_;
    size_t i = v % size_;
    while (h_[i] != v && h_[i] != no_value_) {
      if (++i == size_) i = 0;
    }
    return h_[i] == v;
  }
};
于 2013-04-15T00:09:59.907 回答
0

64 位 = 8 字节。2*8*100,000,000byte = 1.6GB => 您可以将数字保存在 RAM 中（对于节点结构，您可能需要两倍...）。我会选择平衡二叉树（只需在 wiki 中搜索 AVL、AB ......树）。只需将数字从一组添加到一棵树，从另一组添加到另一棵树并进行交集。

您可能只想对两个数组进行排序并将它们相交。这应该是最简单的解决方案。

如果您无法处理内存中的所有数字，请使用数据库（MySQL、PostgreSQL...）。两个排序表和交叉点。它应该非常快，最重要的是易于实施。

于 2013-04-14T19:26:03.760 回答
0

由于您的整个数据集将（轻松）放入您的 RAM，因此您无需对它进行任何巧妙的排序，也无需使用磁盘空间（除了首先加载数据）。

我假设每个元素在每个列表中最多可以存在一次。

哑（蛮力）方法，O（n ^ 2）：

foreach a in A (this could be as you read it from disk)
    foreach b in B
        if a is b
            increase count
            break out of inner loop

预排序方法：(2*n*log(n)+n)，所以 O(n*log(n))

sort A
sort B
B_ind = 0
foreach a in A
    foreach b in B from B_ind
        if a is b
            increase count
            B_ind = current b index + 1
            break out of inner loop
        else if b > a
            B_ind = current b index
            break out of inner loop

我推荐前者，但需要并行处理。很容易将外部循环分解成块以在处理器/工作站之间分割。后者也可以在一定程度上并行化（同时执行两种类型），但远没有那么多。

同样在前者的情况下，您可以通过将 b 循环拆分为缓存大小的块来获得一些性能提升。即检查 A[0] 与 B[0...1023] （如果您的缓存可以容纳 1024 个项目），然后检查 A[1]，... A[final]，然后检查 A[0] 与 B[1024 ...2047] 等。

于 2013-04-14T19:36:10.527 回答