稀疏 O(1) 数组，索引为连续乘积

发布于 2024-10-12 06:48:52 字数 1154 浏览 12 评论 0原文

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

我知道我只需要 f(x) 的值，其中 x 的形式为 a*b，其中 < code>a 和 b 是 0..N 范围内的整数。

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

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

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

编辑

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

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

编辑

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

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

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

原文

I'd like to pre-calculate an array of values of some unary function f.

I know that I'll only need the values for f(x) where x is of the form of a*b, where both a and b are integers in range 0..N.

The obvious time-optimized choice is just to make an array of size N*N and just pre-calculate just the elements which I'm going to read later. For f(a*b), I'd just check and set tab[a*b]. This is the fastest method possible - however, this is going to take a lot of space as there are lots of indices in this array (starting with N+1) which will never by touched.

Another solution is to make a simple tree map... but this slows down the lookup itself very heavily by introducing lots of branches. No.

I wonder - is there any solution to make such an array less sparse and smaller, but still quick branchless O(1) in lookup?

edit

I can hear lots of comments about a hash map... I'll proceed to benchmark how one behaves (I expect a significant performance drop over normal lookup due to branching; less than in trees, but still... let's see if I'm right!).

I'd like to emphasize: I'd mostly appreciate an analytical solution which would use some clever way (?) to take advantage of the fact that only "product-like" indices are taken. I feel that this fact might be exploited to get a way better result that an average generic hash map function, but I'm out of ideas myself.

edit

Following your advice, I've tried std::unordered_map from gcc 4.5. This was a tad slower than the simple array lookup, but indeed much faster than the tree-based std::map - ultimately I'm OK with this solution. I understand now why it's not possible to do what I originally intended to; thanks for the explanations!

I'm just unsure whether the hash-map actually saves any memory! :) As @Keith Randall has described, I cannot get the memory footprint lower than N*N/4, and the triangular matrix approach described by @Sjoerd gives me N*N/2. I think that it's entirely possible for the hash map to use more than N*N/2 space if the element size is small (depends on the container overhead) - which would make the fastest approach also the most memory-effective! I'll try to check that.

I wish I could accept 2 answers...

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

超可爱的懒熊 2024-10-19 06:48:52

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

每个条目都会被使用，但会出现重复：f(a,b) = f(b,a)。因此只需要一个三角矩阵（以 a>b 与 a

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，大约是方阵大小的一半。但仍然是二次的:(

编辑2：请注意 er 仍然是矩阵中的重复项：例如 f(3, 2) = f(6, 1)。我认为如果没有引入大量分支和循环，但这只是一种直觉。

Start with looking at it as a two-dimensional array: tab[a][b]. This still requires N*N size.

Each entry will be used, but there will be duplication: f(a,b) = f(b,a). So only a triangular matrix is required (at the cost of one branch for 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

EDIT: the memory used by a triangular matrix is (N+1)*N/2, about half the size of a square matrix. Still quadratic, though :(

EDIT2: Note that er is still duplication in the matrix: e.g. f(3, 2) = f(6, 1). I don't think this can be eliminated without introducing lots of branches and loops, but that's just a gut feeling.

回复收藏 0 原文

黎夕旧梦 2024-10-19 06:48:52

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

我认为，如果您希望大多数参数永远不会出现，那么最好利用对称性，然后使用哈希表。

回复收藏 0 原文

白昼 2024-10-19 06:48:52

为什么不简单地散列 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;
}

基本记忆。

Why not simply hash the A and B combo and put the results in a map? And do it lazily so you just get the ones you want?

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;
}

Basic memoization.

回复收藏 0 原文