我想pre-计算的一些一元函数的值的数组 F 。

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

我知道，我只需要 F的值（x），其中 X 的形式为对 A * B ，其中两个 A 和 B 是在范围内的整数 0..N 。

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.

最明显的时间优化的选择只是为了让大小的数组 N *ñ，只是pre-计算只是我要去元素后来读。对于 F（A * B），我刚刚检查和设置标签[a * b] 。这是最快的方法可能 - 但是，这将占用大量的空间，有很多指标的数组（从 N + 1 ），它永远不会受感动。

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.

我不知道 - ？有没有什么解决方案，使这样一个数组少疏小，但还是很快网点O（1）中查找

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

修改

我可以听到许多关于哈希映射评论...我会继续基准的行为方式是如何的（我希望过正常的查找，由于分支一个显著的性能下降;小于在树上，但仍。 ..让我们来看看，如果我是对的！）的。

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!).

我想强调的是：（？）我主要是AP preciate的分析解决方案，它会使用一些巧妙的方式，采取的事实，即只有产品状指数取。我觉得，这个事实可能被利用来得到一个更好的方式结果的平均通用哈希地图功能，但我的想法我自己。

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.

修改

按照你的建议，我从GCC 4.5试过的std :: unordered_map 。这是一点点比简单数组的查找速度慢，但比基于树的的std ::地图的确是更快 - 最终我与这个解决方案确定。我现在明白为什么它不能做什么，我本来打算;感谢您的解释！

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!

我只是不确定的哈希映射是否真正节省任何内存！ :)至于@Keith兰德尔描述了，我不能比内存占用较低的N * N / 4 ，并通过@Sjoerd描述三角矩阵的方法给我 N * N / 2 。我认为这是完全有可能的哈希映​​射使用超过 N * N / 2 空间，如果该单元尺寸小（取决于容器开销） - 这将使最快的方法也是最内存高效！我会尽力检查。

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.

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

I wish I could accept 2 answers...

推荐答案

似乎没有被大量结构，以充分利用这里的优势。如果你问，如果有一种方式来安排，安排表，这样就可以避免存储能不会发生条目（因为他们有一个质因数大于N），你不能节省很多。有一种光滑的数字的理论其中指出，近N N光滑数字的密度^ 2〜2 ^ -2。所以，绝对最好的情况下，可以通过4个，最多的一个因素降低（最大）的存储需求。

There doesn't seem to be a lot of structure to take advantage of here. If you're asking if there is a way to arrange to arrange the table such that you can avoid storage for entries that can't happen (because they have a prime factor larger than N), you can't save much. There is a theory of smooth numbers which states that the density of N-smooth numbers near N^2 is ~2^-2. So, absolute best case, you can reduce the (maximum) storage requirement by at most a factor of 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.