c++ - 使用 memoized 函数观察到奇怪的性能

Question

我正在研究使用欧几里德算法计算两个数的 GCD 的东西。我像往常一样实现了标准的单线，并且效果很好。它用于计算系列并调用 gcd() 的算法中每个元素多次，如 n变大。我决定看看我是否可以通过内存来做得更好，所以这是我尝试过的:

size_t const gcd(size_t const a, size_t const b) {
  return b == 0 ? a : gcd(b, a % b);
}

struct memoized_gcd : private std::unordered_map<unsigned long long, size_t> {
  size_t const operator()(size_t const a, size_t const b) {
    unsigned long long const key = (static_cast<unsigned long long>(a) << 32) | b;
    if (find(key) == end()) (*this)[key] = b == 0 ? a : (*this)(b, a % b);
    return (*this)[key];
  }
};

//std::function<size_t (size_t, size_t)> gcd_impl = gcd<size_t,size_t>;
std::function<size_t (size_t, size_t)> gcd_impl = memoized_gcd();

我通过 std::function 调用所选函数稍后举例。有趣的是，例如当 n = 10,000 时，计算在这台计算机上运行 8 秒，而使用内存版本接近一分钟，其他一切都相同。

我是否遗漏了一些明显的东西？我正在使用 key作为权宜之计，这样我就不需要专门研究std::hash对于 HashMap 。我唯一能想到的可能是内存版本没有获得 TCO 和 gcd()确实如此，或者通过 std::function 调用对于仿函数来说很慢(即使我同时使用它)，或者我可能是弱智。大师们，给我指明方向。

注意事项

我已经在 win32 和 win64 上用 g++ 4.7.0 和 linux x86 上用 g++ 4.6.1 和 4.7.1 试过了。

我还尝试了带有 std::map<std::pair<size_t, size_t>, size_t> 的版本具有与未内存版本相当的性能。

Answer 1

您的 GCD 版本的主要问题是它可能会占用大量内存，具体取决于使用模式。

例如，如果您为所有对 0 <= a < 10,000、0 <= b < 10,000 计算 GCD(a,b)，则内存表最终将包含 100,000,000 个条目。由于在 x86 上每个条目为 12 字节，哈希表将占用至少 1.2 GB 的内存。使用那么大的内存会很慢。

当然，如果您使用 >=10,000 的值评估 GCD，您可以使表任意大......至少直到您用完地址空间或提交限制。

总结:一般来说，内存化 GCD 是一个坏主意，因为它会导致无限的内存使用。

还有一些可以讨论的细节:

• 当表超过各种大小时，它将存储在越来越慢的内存中:首先是 L1 缓存，然后是 L2 缓存、L3 缓存(如果存在)、物理内存、磁盘。显然，随着表的增长，记忆化的成本会急剧增加。
• 如果您知道所有输入都在一个小范围内(例如，0 <= x < 100)，使用内存或预先计算的表格仍然是一种优化。很难确定 - 您必须在特定情况下进行衡量。
• 可能还有其他优化 GCD 的方法。例如，在此示例中，我不确定 g++ 是否自动识别尾递归。如果不是，您可以通过将递归重写为循环来提高性能。

但正如我所说，您发布的算法表现不佳并不奇怪。