2

我想预先计算一些一元函数的值数组f。

我知道我只需要f(x)wherex形式为的值a*b，其中a和b都是 range 中的整数0..N。

显而易见的时间优化选择只是制作一个大小数组，N*N并仅预先计算我稍后将要阅读的元素。对于f(a*b)，我只需检查并设置tab[a*b]. 这是可能的最快方法 - 但是，这将占用大量空间，因为该数组中有很多索引（以 开头N+1）永远不会被触及。

另一种解决方案是制作一个简单的树形图......但这会通过引入大量分支来大大减慢查找本身的速度。不。

我想知道 - 是否有任何解决方案可以使这样的数组不那么稀疏和更小，但在查找中仍然快速无分支 O(1)？

编辑

我可以听到很多关于哈希映射的评论......我将继续对一个人的行为进行基准测试（我预计由于分支而导致正常查找的性能显着下降；低于树，但仍然......让我们看看我是否是对的！）。

我想强调一下：我最喜欢一种分析解决方案，它会使用一些聪明的方法（？）来利用仅采用“类产品”索引这一事实。我觉得这个事实可能会被利用来获得比普通的通用哈希映射函数更好的结果，但我自己没有想法。

编辑

按照您的建议，我std::unordered_map从 gcc 4.5 开始尝试。这比简单的数组查找要慢一点，但确实比基于树的查找要快得多std::map——最终我对这个解决方案感到满意。我现在明白为什么不能按照我最初的意图去做了；感谢您的解释！

我只是不确定哈希映射是否真的节省了任何内存！:) 正如@Keith Randall 所描述的，我无法使内存占用低于N*N/4，而@Sjoerd 描述的三角矩阵方法给了我N*N/2。我认为N*N/2如果元素大小很小（取决于容器开销），哈希映射完全有可能使用更多空间 - 这将使最快的方法也是最有效的内存！我会试着检查一下。

我希望我能接受2个答案...

4

4 回答 4

5

首先将其视为一个二维数组：tab[a][b]. 这仍然需要 N*N 大小。

每个条目都会被使用，但会有重复：f(a,b) = f(b,a). 所以只需要一个三角矩阵（以 a>b vs a<b 的一个分支为代价）。

if (a < b) return tab[b*(b+1) + a]; // assuming 0 <= a < b < N
else return tab[a*(a+1) + b];       // assuming 0 <= b <= a < N

或者

if (a < b) return tab[b*(b-1) + a]; // assuming 1 <= a < b <= N
else return tab[a*(a-1) + b];       // assuming 1 <= b <= a <= N

编辑：三角矩阵使用的内存是 (N+1)*N/2，大约是方阵大小的一半。仍然是二次的，虽然:(

EDIT2：请注意， er 仍然是矩阵中的重复项：例如f(3, 2) = f(6, 1). 我认为如果不引入大量分支和循环就无法消除这种情况，但这只是一种直觉。

于 2011-01-15T01:47:45.887 回答
2

这里似乎没有很多结构可以利用。如果你问是否有办法安排表格，这样你就可以避免存储不可能发生的条目（因为它们的素数大于 N），你不能节省太多。有一种平滑数理论指出，N^2 附近的 N 个平滑数的密度约为 2^-2。因此，绝对最佳情况下，您最多可以将（最大）存储需求减少 4 倍。

I think you're better off taking advantage of symmetry and then using a hash table if you expect most arguments to never occur.

于 2011-01-15T06:44:10.383 回答
0

为什么不简单地散列 A 和 B 组合并将结果放入地图中？懒惰地做，这样你就能得到你想要的？

public Result f(Type1 a, Type2 b) {
    TypePair key = new TypePair(a, b);
    Result res = map.get(key);
    if (res == null) {
        res = reallyCalculate(a, b);
        map.put(key, res);
    }
    return res;
}

基本记忆。

于 2011-01-15T01:44:56.157 回答
0

哈希表在查找速度和内存开销之间提供了很好的平衡。C++ 标准库不提供哈希表，尽管它有时可作为非标准扩展使用。例如，参见SGI hash_map。

Poco C++ 库还具有 HashTable 和 HashMap 类，请参阅文档。

于 2011-01-15T01:45:28.763 回答