映射從一組到另一

我有連續整數值的一組和非連續的值的對應集合，例如：映射從一組到另一

0 -> 22 
1 -> 712 
2 -> 53 
3 -> 12323 
...

等。

項目數量非常大（大約10^9 ... 10^10），所以只使用普通數組不是一個選項。

是否有數據結構能夠從第一個值到另一個具有適度內存要求的快速映射？例如：

ret = map(0); // returns 22 
ret = map(3); // returns 12323

編輯：採用僞隨機數發生器產生真正在這個設定值，所以無法提出了一些具體的分佈。問題是 - 是否有可能降低內存要求（可能是查找速度的價格）？我的意思是使用諸如「完美哈希」之類的東西 - 生成這種「完美哈希」所需的時間並不重要。

來源

2012-08-17 John Rivers

在您的例子的關係爲1; 1，是現實的或只有本實施例的特徵/ – 2012-08-17 12:34:03

@High性能標誌是，每個索引相關聯的具有隻有一個值，因此，使用陣列不僅是可能的因爲內存要求。 – 2012-08-17 12:36:43

您聲明瞭適度的內存要求，但10^10 int - > int會在沒有壓縮的情況下運行100個GB。你能告訴我們關於數據集的其他信息嗎？ – cmh 2012-08-17 12:37:00

您可能能夠通過使用確切地說節省一些空間每個值所需的位數。例如，如果你的值只有24位，你可以保存一個字節在32位整數。也就是說，只有這麼多的記憶可以保存。

對於64位的機器，將mmap()文件轉換爲內存地址是可行的，因此以性能爲代價通過使用磁盤存儲來克服物理內存限制。

但是，既然您提到使用僞隨機生成器來生成值，那麼如何爲特定索引存儲RNG種子並根據需要計算其餘值？例如，你可以存儲索引0,100,200，...的種子並計算例如102將RNG重新播種100次並調用發生器功能三次。

這樣的方法可以減少一個很大的因素（在這種情況下爲100）所需的內存，並且可以通過聚合或緩存查詢來降低性能成本。

來源

2012-08-17 12:52:06 thkala

如果函數的範圍是由僞隨機數生成器按順序生成的數字集，那麼您可以將該序列向下壓縮到生成序列的代碼加上PRNG的狀態開始。例如，包含pi小數展開的（無限）一系列數字很容易（並且在技術上無限地）壓縮到代碼中以生成該系列;你的系列可以被看作是幾乎完全相同的例子。因此，如果您願意等待很長時間才能獲得系列中的最後一個元素，那麼您可以通過將您的系列文章寫入數據結構而不是函數來獲得非常好的壓縮效果。這是您的時間/空間權衡頻譜的一端。

在譜的另一端是所有數字的數組;這會佔用大量空間，但會非常快速地（O(1)）訪問該集合中的任何所需元素。由於各種原因，這似乎並不吸引你，但我不確定比數組更聰明的數據結構將節省很多空間，或者爲此節省時間。

的一個顯而易見的解決方案我看到的是保存在間隔一組PRNG的中間狀態的，所以你的「數據」的結構將變爲：

ret(0) = prng(seed, other_parameters, ...) 
ret(10^5-1) = prng(seed', other_parameters, ...) 
ret(2*(10^5)-1) = prng(seed'', other_parameters, ...)

等。然後，爲了獲得元素9765，比方說，你讀取（PRNG的狀態）ret(0)，然後生成第9765個僞隨機數。

來源

2012-08-17 12:52:40

由於您的範圍是連續的，顯而易見的解決方案是將您的值存儲在連續的int []中。那麼我的價值是arr[i]。作爲PRNG生成的值，將難以應用進一步的壓縮。

另一種解決空間交換問題的方法是存儲RNG的種子並實時重新計算。這種方法可以通過存儲中間種子來及時改善，並且在空間上變差。即種子密鑰1000,2000等

來源

2012-08-17 12:52:55 cmh

好吧，所以意圖是交換速度以減少內存使用量。假設你有某種循環來填充數組。

int array[intendedArraySize]; 

seed = 3; 
for (size_t z = 0; z < intendedArraySize; z++) 
{ 
    array[z] = some_int_psn_generator(seed); 
}

之後您可以顯示值。

for (size_t z = 0; z < intendedArraySize; z++) 
{ 
    std::cout << z << " " << array[z] << std::endl; 
}

如果確實如此，可以考慮全部丟棄數組，每次只需重新計算一次數值。

for (size_t z = 0; z < intendedArraySize; z++) 
{ 
    std::cout << z << " " << some_int_psn_generator(z) << std::endl; 
}

來源

2012-08-17 15:35:23 EvilTeach

映射從一組到另一

回答

相關問題