6

我正在玩弄一些使用欧几里得算法来计算两个数字的 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研究哈希图。我唯一能想到的可能是 memoized 版本没有获得 TCO 并且gcd()确实获得了，或者通过仿函数调用std::function很慢（即使我同时使用它），或者我可能是智障。大师们，给我指路。

笔记

我已经在带有 g++ 4.7.0 的 win32 和 win64 以及带有 g++ 4.6.1 和 4.7.1 的 linux x86 上尝试过这个。

我还尝试了一个与std::map<std::pair<size_t, size_t>, size_t>未记忆版本具有可比性能的版本。

4

3 回答 3

6

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

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

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

摘要：一般来说，记忆 GCD 是一个坏主意，因为它会导致无限的内存使用。

有一些更好的观点可以讨论：

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

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

于 2012-07-13T05:23:27.043 回答
0

这并不奇怪。在现代 CPU 上，内存访问速度非常慢，尤其是当它不在缓存中时。重新计算一个值通常比将其存储在内存中更快。

于 2012-07-13T01:22:51.170 回答
0

频繁的堆分配（创建新条目时）。还有 std::unordered_map 查找开销（虽然它可能是常数时间，但肯定比普通数组偏移慢）。缓存也未命中（访问模式和大小的函数）。

如果要进行“纯”比较，可以尝试将其转换为使用静态的、堆栈分配的普通数组；这可能是一个使用更多内存的稀疏查找表，但如果您可以将整个 memoized 数组放入 CPU 缓存中，它将更能代表memoization。

于 2012-07-13T02:07:12.837 回答