我有一组连续整数值和相应的一组非连续值,例如:
0 -> 22
1 -> 712
2 -> 53
3 -> 12323
...
等等。
项目的数量非常巨大(大约 10^9...10^10),因此仅使用普通数组不是一个选择。
是否存在能够在内存要求适中的情况下快速从第一个值映射到另一个值的数据结构?例如:
ret = map(0); // returns 22
ret = map(3); // returns 12323
编辑:该集中的值实际上是使用伪随机数生成器生成的,因此不可能建议某些特定的分布。问题是 - 是否可以降低内存要求(可能以查找速度为代价)?我的意思是使用“完美哈希”之类的东西 - 生成这种“完美哈希”所需的时间并不重要。
最佳答案
由于您的范围是连续的,因此显而易见的解决方案是将您的值存储在连续的 int[] 中。那么 i 的值就是arr[i]
。由于PRNG生成的值,很难进行进一步的压缩。
另一个以时间换空间的解决方案是存储 RNG 的种子并动态重新计算。通过存储中间种子,这种方法可以在时间上得到改进,在空间上变得更糟。 IE。 key 1000、2000 等的种子
关于c - 从一组映射到另一组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12005888/