8

这个问题有最优解吗？

描述一种在包含一百万个电话号码的文件中查找重复项的算法。该算法在运行时只有 2 兆字节的可用内存，这意味着您不能一次将所有电话号码加载到内存中。

我的“天真”解决方案将是一个 O(n^2) 解决方案，它迭代值并仅以块的形式加载文件，而不是一次全部加载。

对于 i = 0 到 999,999

string currentVal = get the item at index i

for j = i+1 to 999,999
  if (j - i mod fileChunkSize == 0)
    load file chunk into array
  if data[j] == currentVal
    add currentVal to duplicateList and exit for

必须有另一种情况，您可以以一种非常独特的方式加载整个数据集并验证一个数字是否重复。有人有吗？

4

4 回答 4

8

将文件分成 M 个块，每个块都足够大，可以在内存中排序。在内存中对它们进行排序。

对于每两个块的集合，我们将对两个块执行最后一步合并排序以生成一个更大的块 (c_1 + c_2) (c_3 + c_4) .. (c_m-1 + c_m)

指向磁盘上 c_1 和 c_2 上的第一个元素，并创建一个新文件（我们将其称为 c_1+2）。

如果 c_1 的指向元素小于 c_2 的指向元素，则将其复制到 c_1+2 并指向 c_1 的下一个元素。
否则，将 c_2 的指向元素复制到并指向 c_2 的下一个元素。

重复上一步，直到两个数组都为空。您只需要使用存储两个指向数字所需的内存空间。在此过程中，如果您遇到 c_1 和 c_2 的指向元素相等，则您找到了重复项 - 您可以将其复制两次并递增两个指针。

生成的 m/2 数组可以以相同的方式递归合并 - 这些合并步骤需要 log(m) 来生成正确的数组。每个数字都将与其他数字进行比较，以找到重复项。

或者，@Evgeny Kluev 提到的一个快速而肮脏的解决方案是制作一个尽可能大的布隆过滤器，它可以合理地容纳在内存中。然后，您可以列出未通过布隆过滤器的每个元素的索引列表，并再次遍历文件，以测试这些成员是否重复。

于 2013-03-14T17:22:18.123 回答
4

我认为 Airza 的解决方案正朝着一个好的方向发展，但由于排序不是您想要的，而且成本更高，您可以结合 angelatlarge 的方法执行以下操作：

取一个适合大小为 M/2 的内存的块 C 。

获取块 C i

  1. 遍历i并将每个元素散列到散列表中。如果元素已经存在，那么您就知道它是重复的，您可以将其标记为重复。（将其索引添加到数组或其他东西中）。

  2. 获取下一个块 C i+1 并检查哈希表中是否已存在任何键。如果元素存在，则将其标记为删除。

  3. 对所有块重复，直到您知道它们不会包含来自块 C i的任何重复项

  4. 对块 C i+1重复步骤 1,2

  5. 删除了所有标记为要删除的元素（可以在更合适的情况下在此期间完成，如果您必须转移其他所有内容，那么一次删除一个可能会更昂贵）。

这在 O((N/M)*|C|) 中运行，其中 |C| 是块大小。请注意，如果 M > 2N，那么我们只有一个块，并且运行时间为 O(N)，这对于删除重复项是最佳的。我们只需对它们进行哈希处理并确保删除所有冲突。

编辑：根据要求，我提供详细信息：* N 是电话号码。

  • 块的大小取决于内存，它的大小应该是 M/2。这是将加载文件块的内存大小，因为整个文件太大而无法加载到内存中。

  • 这会留下另外 M/2 个字节来保存哈希表2和/或重复列表1。

  • 因此，应该有 N/(M/2) 个块，每个块的大小为 |C| = 米/2

  • 运行时间将是块的数量(N/(M/2))，乘以每个块的大小|C| （或 M/2）。总的来说，这应该是线性的（加上或减去从一个块更改为另一个块的开销，这就是为什么描述它的最佳方式是 O( (N/M) * |C| ）

一个。加载一个块 C i。O(|C|)
b. 遍历每个元素，测试并设置如果不存在O(1)将在其中插入和查找应该进行散列。
C。如果元素已经存在，您可以将其删除。1
天。获取下一个块，冲洗并重复（2N/M 个块，所以O(N/M)）

1移除一个元素可能会花费 O(N)，除非我们保留一个列表并一次性移除它们，避免在移除一个元素时移动所有剩余的元素。

2如果电话号码都可以表示为小于 2 32 - 1 的整数，我们可以避免使用完整的哈希表，而只需使用标志映射，从而节省大量内存（我们只需要 N 位内存）

这是一个有点详细的伪代码：

void DeleteDuplicate(File file, int numberOfPhones, int maxMemory)
{
    //Assume each 1'000'000 number of phones that fit in 32-bits.
    //Assume 2MB of memory
    //Assume that arrays of bool are coalesced into 8 bools per byte instead of 1 bool per byte
    int chunkSize = maxMemory / 2; // 2MB / 2 / 4-byes per int = 1MB or 256K integers

    //numberOfPhones-bits. C++ vector<bool> for example would be space efficient
    //  Coalesced-size ~= 122KB  | Non-Coalesced-size (worst-case) ~= 977KB 
    bool[] exists = new bool[numberOfPhones];

    byte[] numberData = new byte[chunkSize];
    int fileIndex = 0;
    int bytesLoaded;
    do //O(chunkNumber)
    {
        bytesLoaded = file.GetNextByes(chunkSize, /*out*/ numberData);
        List<int> toRemove = new List<int>(); //we still got some 30KB-odd to spare, enough for some 6 thousand-odd duplicates that could be found

        for (int ii = 0; ii < bytesLoaded; ii += 4)//O(chunkSize)
        {
            int phone = BytesToInt(numberData, ii);
            if (exists[phone])
                toRemove.push(ii);
            else
                exists[phone] = true;
        }

        for (int ii = toRemove.Length - 1; ii >= 0; --ii)
            numberData.removeAt(toRemove[ii], 4);

        File.Write(fileIndex, numberData);
        fileIndex += bytesLoaded;

    } while (bytesLoaded > 0); // while still stuff to load
}
于 2014-09-29T03:14:58.867 回答
1

如果您可以存储临时文件，则可以将文件加载到块中，对每个块进行排序，将其写入文件，然后遍历块并查找重复项。您可以通过将数字与文件中的下一个数字以及每个块中的下一个数字进行比较来轻松判断该数字是否重复。然后移动到所有块中的下一个最小数字并重复直到用完数字。

由于排序，您的运行时间为 O(n log n)。

于 2013-03-14T17:01:42.850 回答
1

我喜欢@airza 解决方案，但也许还有另一种算法需要考虑：也许一百万个电话号码不能一次加载到内存中，因为它们的表达效率低下，即每个电话号码使用的字节数超过了必要的字节数。在这种情况下，您可以通过对电话号码进行散列并将散列存储在（散列）表中来获得有效的解决方案。哈希表支持字典操作（例如in），让您轻松找到骗子。

更具体地说，如果每个电话号码都是 13 个字节（例如 format 中(NNN)NNN-NNNN的字符串），则该字符串表示十亿个数字中的一个。作为一个整数，这可以存储为 4 个字节（而不是字符串格式的 13 个字节）。然后我们可能能够将这个 4 字节的“哈希”存储在哈希表中，因为现在我们的 10 亿个哈希数字占用了 3.08 亿个数字的空间，而不是 10 亿个。排除不可能的数字（区号000,555等中的所有内容）可能会让我们进一步减小散列大小。

于 2013-03-14T17:45:47.827 回答