高效地將18億BILLION輸入值映射到幾個輸出值

Question

看起來下面給出的信息（行）不夠清晰，所以我試圖更加清晰和簡潔。

我需要關於如何將數十億個ulong值映射到幾個int值的建議。在最壞的情況下，我有超過110億（基本上是隨機的ulong值），需要映射到40個int值。映射是已知的，除了所需的內存量之外，字典可以工作。目前，估計當使用字典時，大約199GB的RAM將用於所有需要的映射。

有沒有人知道任何一種算法或過程，可以用來完成這種映射，而不消耗這麼多的RAM？

---

我正在使用C＃.NET 4.5程序來幫助篩選我的數據並且遇到效率問題。我目前正在運行8個數據庫（我最終需要做20個）不同的過濾器，每個過濾器都以相同的方式過濾數據，但在不同的層次上。在過濾器過程中的某個點上，每個級別都有許多必須編碼到最終輸出值中的值。

一些例子：

在第3級有23個值被編碼到6個可能輸出值（0-5）。

在級別7有2,576個值被編碼成14個可能的輸出值（0-13）。

在第10級，有88,215個值被編碼爲20個可能的輸出值（0-19）。

當我達到20級時，我將有11個以上的BILLION值被編碼爲40個輸出值（0-39）。

爲每個過濾器編碼的值都是事先已知的，我正在從文件中讀取這些信息併爲每個過濾器（當前爲1到8）填充單獨的字典。按照這個速度，當我過濾20時，將會有超過16.5億的總字典條目，其中大多數是ulong值。

從長遠來看，這不是一個解決方案。

有誰知道一種方法將數百萬個唯一的輸入值映射到幾個唯一的輸出值更有效嗎？

是否有算法將輸入映射到輸出？

我在尋找任何想法，可能會指出我在正確的方向。

Answer 1

如果輸入CSV文件中的值被排序，並且數據永遠不會改變，我們可以從註釋中放棄桶方法，並將文件中的一個大陣列中的所有數據對填滿。我們的目標是更好地組織數據，以便快速閱讀，從而避免將整個數據集放在內存中。您必須將CSV文件轉換爲新的二進制格式，並在此過程中在內存中創建索引數組。這個索引數組也應該保存到某個索引文件中，以便在程序重新啓動時使用它。在內存中，您只能保存第一個數據對的位置數組，其值以item的索引開頭。在文件中，你只需要一個32位（4字節）的數字，每個數字的前3個字節是存儲器中索引項的剩餘部分，最後一個字節是我們的輸出。

要創建索引數組，您可以逐行讀取CSV文件。對於每個數據對（input_int,output_int）創建新的數據對（index，32-bit value）。 Index需要input_int的前2個字節，並且32-bit value被創建爲連接input_int的最後3個字節和output_int的唯一字節。如果index從先前的數據對改變，則將文件的位置存儲到新索引處的數組。無論如何在文件中附加32-bit value。重複，直到CSV文件結束。

假設我們有一個輸入值0x1234567890並需要相應的輸出值。算法會在索引爲0x1234和0x1235的內存中查找數組中的項目。這會給你在我們的項目可能在文件中的開始和結束位置。在這個範圍內，我們爲值0x567890做一個binary search並取其後的字節。這是我們的產值。