稀疏的O(1)数组,索引是连续的产品

Question

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

我知道,我只需要值f(x),其中x是的形式a*b,其中两个a和b在范围内的整数0..N.

明显的时间优化选择只是制作一个大小的数组,N*N只是预先计算我稍后要阅读的元素.因为f(a*b),我只是检查和设置tab[a*b].这是最快的方法 - 但是,这将占用大量空间,因为此数组中有许多索引(从开头N+1),永远不会触及.

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

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

编辑

我可以听到很多关于哈希映射的评论......我将继续对一个人的行为进行基准测试(我预计由于分支而导致正常查找的性能显着下降;比在树中更少,但仍然......让我看看我是否"M吧!) .

我想强调一点:我主要赞赏一种分析解决方案,它可以使用一些聪明的方法(？)来利用只有"类似产品"指数的事实.我觉得这个事实可能会被利用来获得更好的结果,即平均通用哈希映射函数,但我自己也没有想法.

编辑

按照你的建议,我试过std::unordered_mapgcc 4.5.这比简单的数组查找慢一点,但确实比基于树的更快std::map- 最终我对这个解决方案很满意.我现在明白为什么不可能做我原本打算做的事情; 谢谢你的解释!

我只是不确定哈希映射是否实际上节省了任何内存!:)正如@Keith Randall所描述的那样,我无法将内存占用率降低N*N/4,并且@Sjoerd描述的三角矩阵方法给了我N*N/2.我认为N*N/2如果元素大小很小(取决于容器开销),哈希映射完全有可能使用空间以上- 这将使最快的方法也是最有效的内存!我会试着检查一下.

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

Answer 1

首先将其视为二维数组:tab[a][b].这仍然需要N*N尺寸.

每个条目都将被使用,但会有重复:f(a,b) = f(b,a).因此,只需要一个三角矩阵(以一个分支为代价,> b与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).我不认为如果不引入大量的分支和循环就可以消除这种情况,但这只是一种直觉.