2

I have an application in which I have to store a couple of millions of integers, I have to store them in a Look up table, obviously I cannot store such amount of data in memory and in my requirements I am very limited I have to store the data in an embebedded system so I am very limited in the space, so I would like to ask you about recommended methods that I can use for the reduction of the look up table. I cannot use function approximation such as neural networks, the values needs to be in a table. The range of the integers is not known at the moment. When I say integers I mean a 32 bit value.

Basically the idea is use some copmpression method to reduce the amount of memory but without losing many precision. This thing needs to run in hardware so the computation overhead cannot be very high.

In my algorithm I have to access to one value of the table do some operations with it and after update the value. In the end what I should have is a function which I pass an index to it and then I get a value, and after I have to use another function to write a value in the table.

I found one called tile coding http://www.cs.ualberta.ca/~sutton/book/8/node6.html, this one is based on several look up tables, does anyone know any other method?.

Thanks.

4

5 回答 5

1

我会查看您需要存储的数字类型，并提取其中许多常见的信息。例如，如果它们紧密聚集，您可以取平均值、存储它并存储偏移量。偏移量的位数将少于原始数字。或者，如果它们或多或少均匀分布，您可以存储第一个数字，然后将偏移量存储到下一个数字。

知道查找数字的关键是什么会有所帮助。

于 2008-12-02T22:08:08.453 回答
0

我需要更多关于这个问题的细节。如果您不能存储整数的实际值而是一个近似值，这意味着您将减少（丢弃）一些数据（细节），对吗？我认为您正在寻找哈希，它本身就是一种艺术形式。例如，假设您有 32 位值，一个哈希是取 4 个字节并将它们异或在一起，这将产生一个 8 位值，将您的存储量减少 4 倍，但也减少了原始数据的实际值. 通常你可以/会走得更远，也许只使用这 8 位中的几个，比如较低的 4 位，并进一步降低该值。

我认为我真正的问题是要么你需要数据，要么你不需要，如果你需要数据，你需要压缩它或找到更多的内存来存储它。如果你不这样做，那么使用某种散列来减少位数，直到你达到你有存储的内存量。

于 2008-12-02T22:05:41.530 回答
0

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

“函数逼近”是指使用参数化函数形式来表示价值函数（和/或策略），而不是简单的表格。”

也许这适用。此外，用其他事实更新您的问题——不要仅仅在评论中回答。

编辑。

位数组可以轻松地为数百万个数字中的每一个存储一个位。假设您的数字在 1 到 800 万之间。在单个兆字节的存储空间中，您的集合中的每个数字都可以有一个位，而您集合中的每个数字都可以有一个 0。

如果您的数字在 1 到 3200 万之间，则需要 4Mb 的内存来存储所有 32M 不同数字的大表。

看到我对Python 中现代、高性能布隆过滤器的回答了吗？用于无限大小的位数组的 Python 实现。

于 2008-12-02T22:23:04.040 回答
0

如果您只是在寻找存在问题的数字布隆过滤器，可能就是您正在寻找的东西。老实说，尽管您的问题相当模糊和令人困惑。这将有助于解释 Q 值是什么，以及在表格中找到它们后如何处理它们。

于 2008-12-02T22:40:47.577 回答
0

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

所以假设一个桶是一个指向数组的指针和一个计数。在 32 位系统上，最大为 64 位。如果整数的数量足够小，我们也许可以做一些花哨的事情并使用 32 位作为存储桶。16k * 8 字节 = 524k，200 万条短片 = 4mb。因此，这为您提供了一种查找整数和大约 40% 压缩率的方法。

于 2014-06-16T02:45:01.243 回答