使用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的哈希映射.我能想到的唯一的事情可能就是memoized版本没有达到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>性能与unmemoized版本相当.

Answer 1

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

例如,如果为所有对0 <= a <10,000,0 <= b <10,000计算GCD(a,b),则memoization表将以100,000,000个条目结束.由于在x86上每个条目都是12个字节,因此哈希表将占用至少1.2 GB的内存.使用这么多内存会很慢.

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

简介:一般来说,记忆GCD是一个坏主意,因为它会导致无限制的内存使用.

有一些可以讨论的细节:

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

但正如我所说,你发布的算法表现不佳并不奇怪.