首页 文章

使用10 MB内存为40亿个整数（关于找到优化的块大小）[重复]

提问于
浏览 次
7

这个问题在这里已有答案：

问题是，给定一个包含40亿个整数的输入文件，提供一个算法来生成一个未包含在文件中的整数，假设只有10 MB的内存 .

搜索了一些解决方案，其中之一是将整数存储到位向量块（每个块表示40亿范围内的特定整数范围，块中的每个位表示整数），并为每个块使用另一个计数器，计算每个块中的整数数 . 因此，如果整数的数量小于整数的块容量，则扫描块的位向量以找到缺少的整数 .

我对此解决方案的困惑是，当块计数器阵列占用与位向量相同的存储器时，提到最佳最小占用空间 . 我很困惑为什么在这种情况下它是最佳的最小足迹？

这是我提到的计算细节，

Let N = 2^32.
counters (bytes): blocks * 4
bit vector (bytes): (N / blocks) / 8
blocks * 4 = (N / blocks) / 8
blocks^2 = N / 32
blocks = sqrt(N/2)/4

林先生，提前谢谢

algorithm bit-manipulation bit

2 回答

  • 1
    # assumes all integers are positive and fit into an int
# very slow, but definitely uses less than 10MB RAM
int generate_unique_integer(file input-file)
{
  int largest=0
  while (not eof(input-file))
  {
    i=read(integer)
    if (i>largest) largest=i
  }
  return i++; #larger than the largest integer in the input file
}
    回复于
  • 5

    为什么它是最小的内存占用：

    在您提出的解决方案中，有两个阶段：

    • 计算每个块中的整数数

    这使用 4*(#blocks) 字节的内存 .

    • 使用位向量表示块中的整数 .

    这使用 (blocksize/8) 字节的内存，即 (N/blocks)/8 .

    如上所述，将2设置为相等会导致 blocks = sqrt(N/32) .

    这是最佳的，因为所需的内存是每个阶段所需内存的最大值（必须同时执行） . 在第一阶段之后，您可以忘记计数器，除了要搜索第2阶段的块 .

    优化

    如果计数器在达到容量时饱和，那么每个计数器实际上不需要4个字节，而是需要3个字节 . 当计数器超过块中的整数数时，计数器达到容量 .

    在这种情况下，阶段1使用 3*blocks 的内存，阶段2使用 (N/blocks)/8 . 因此，最优的是 blocks = sqrt(N/24) . 如果 N 为40亿，则块数约为12910，块大小为每块309838个整数 . 这适合3个字节 .

    警告，以及具有良好平均案例表现的替代方案

    您提出的算法仅在所有输入整数不同时才有效 . 如果整数不明显，我建议你简单地使用随机候选整数集方法 . 在随机候选整数集方法中，您可以随机选择1000个候选整数，并检查输入文件中是否找不到任何整数 . 如果失败，您可以尝试找到另一组随机整数 . 虽然这样的最差情况表现不佳，但对于大多数输入来说，平均情况会更快 . 例如，如果输入整数的覆盖率为99％的可能整数，那么平均而言，有1000个候选整数，其中10个将无法找到 . 您可以伪随机选择候选整数，以便永远不会重复候选整数，并且还要保证在固定次数的尝试中，您将测试所有可能的整数 .

    如果每次检查 sqrt(N) 候选整数，则最坏情况下的性能可能与 N*sqrt(N) 一样好，因为您可能必须扫描所有N个整数 sqrt(N) 次 .

    如果使用此替代方法，则可以避免最坏情况时间，如果它不适用于第一组候选整数，则切换到建议的解决方案 . 这可能会提供更好的平均案例性能（这是排序中首先使用快速排序的常用策略，然后在切换到heapsort之前，例如，如果看起来存在最坏情况输入） .

    回复于

相关问题