查找表的尺寸減小

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％的壓縮。