查找表的尺寸减小

Question

我有，我有保存几百万整数的应用，我已经将它们存储在一个查找表，很明显，我可以将数据的这种量不存储在内存中，在我的要求我我非常有限，我不得不将数据存储在嵌入式系统中，所以我在空间上非常有限，所以我想问你一些我可以用来减少查找表的推荐方法。我不能使用函数逼近（如神经网络），这些值需要放在一个表中。整数的范围目前还不知道。当我说整数时，我的意思是一个32位的值。

基本想法是使用一些copmpression方法来减少内存却不失许多精密量。这件事需要在硬件上运行，所以计算开销不能太高。

在我的算法我有访问表中的一个值做一些操作与它和更新后的值。最后我应该有一个函数，我将一个索引传递给它，然后我得到一个值，并且在我必须使用另一个函数在表中写入一个值之后。

我找到了一个叫瓦编码http://www.cs.ualberta.ca/~sutton/book/8/node6.html，这一个是基于几个查找表，没有人知道任何其他方法？

谢谢。

Answer 1

我需要更详细的问题。如果你不能存储整数的实际值，而是存储一个近似值，那意味着你要减少（扔掉）一些数据（细节），对吗？我认为你正在寻找一个散列，它本身可以是一个艺术形式。例如，假设您有32位值，则一个散列值将是4个字节并将它们放在一起，这会导致一个8位值，将存储量减少4倍，但也会减少原始数据的实际值。通常情况下，你可能会/会走得更远，也许只会使用这8位中的几个，比如说较低的4位，并进一步降低这个值。

我想我真正的问题是不是你所需要的数据，或者你不，如果你需要的数据，你需要对其进行压缩或发现更多的内存来存储它。如果你不这样做，那么使用某种类型的散列来减少位数，直到达到用于存储的内存量。

Answer 2

我看类型，您需要存储和拔出，对许多人很常见的信息数字。例如，如果它们紧密聚集在一起，您可以采取措施，存储它并存储偏移量。偏移量将比原始数字少。或者，如果它们或多或少均匀分布，则可以存储第一个数字，然后将偏移量存储到下一个数字。

这将有助于知道你的关键是查找数字。

Answer 3

读http://www.cs.ualberta.ca/~sutton/RL-FAQ.html

“函数近似”指的是 使用参数化的函数形式 的代表值函数 （和/或策略），而不是一个 简单的表“。

或许这也适用，用更多的事实更新您的问题 - 。不要在评论只是回答

---

编辑。

位数组可以轻松地为您的数百万数字中的每一位存储一个位。假设您的数字在1至8百万的范围内。在单个兆字节的存储空间中，您可以为您的设备中的每个号码设置1位，并且您的设置中的每个号码都为0。

如果你的数字在1到32百万的范围内，那么你需要4Mb的内存用于所有32M不同数字的大表。

请参阅我对Modern, high performance bloom filter in Python?的回答，以获取无限大小的位数组的Python实现。

Answer 4

如果您只是在寻找存在的号码问题a bloom filter，可能是你在找什么。老实说，虽然你的问题是相当模糊和混乱。这将有助于解释Q值是什么，以及一旦你在表格中找到它们，你会怎么做。

Answer 5

如果你的一组整数是同伦的，那么你可以尝试一个哈希表，因为有一个技巧，你可以用来减少存储整数的大小，在你的情况下，一半。 假设整数n，因为它的集合是同质的，可以是散列。假设你有0x10000（16k）桶。每个桶索引，iBucket = n & FFFF。由于前16位是存储桶索引，因此存储桶中的每个项目只需存储16位。为了保持数据量小，您必须做的另一件事是将项目的数量放在存储区中，并使用数组来保存存储区中的项目。使用链表会太大而且太慢。当您迭代数组寻找匹配时，请记住您只需比较存储的16位数据。

因此，假设一个存储桶是一个指向数组和指针的指针。在32位系统上，这是最大64位。如果整数的数量足够小，我们可能会做一些奇特的事情，并使用32位的桶。 16k * 8字节= 524k，200万短裤= 4mb。所以这可以让你找到一个方法来查找整数和大约40％的压缩。