用於在C++中存儲超大型2D數據的數據結構

我需要處理最多1億行和30列的數據表（2D）。表格元素只包含0，1和破折號（ - ）。該表格以文本文件形式發給我。我具有本數據存儲到一些數據結構和執行像排序該表中，刪除行，比較元件（無論是在不同的行和列）操作等用於在C++中存儲超大型2D數據的數據結構

目前我使用此一2D向量。我嘗試使用整數向量和位向量。兩者都適用於10mil行和25列，但都不適用於上述最大限制（我有一個壞分配）。

我假設這是因爲矢量需要連續的內存。什麼纔是正確的數據結構呢？時間安排也是我的考慮因素之一，同時也需要較低的訪問時間。另外，如果一個矢量實際上是正確的數據結構，是否有更好的實現可以用來實現這個工作？我必須堅持C++，不能使用數據庫和東西。

非常感謝！

來源

2014-04-03 TheJack

如果你可以設計一個方案來收拾你的tribool分成2個存儲位，你需要大約2.25GB的存儲空間。如果你要爲你的tribool使用一個完整的字節，你需要大約9GB。 – Anycorn

退房NSTATE。

這是對於任意基數打包數組庫（所以三態資格）。

http://nstate.hostilefork.com

免責聲明：我寫NSTATE。

來源

2014-04-04 00:04:58 HostileFork

+1免責聲明。 –

@TanmayPatil謝謝你指出了澄清，但它不僅僅適用於三態，你選擇了基數，它做了數學。因此「N」狀態。每個字節包裝4個4狀態，這種事情。另外我的網站生成器降價有一個錯誤，aaaargh。修復它。 – HostileFork

當然可以。我只是想避免這個有用的答案只能鏈接。 –

你可以考慮的boost::tribool

數組見

你也可以考慮一個包裝過std::bitset使得對於每一個tribool有2位在bitset中。

大小N的tribool需要大小的bitset2*N

映射：

tribool(i) maps to bitset(2*i) and bitset(2*i+1) 

if tribool(i) == indeterminate, then bitset(2*i) = false 
if tribool(i) == true, then bitset(2*i) = true, bitset(2*i) = true 
if tribool(i) == false, then bitset(2*i) = true, bitset(2*i) = false

C++ ISH僞代碼：

template<size_t N> 
class PackedTribool { 
public: 
    ??? test(i) { 
    if(bits_[ 2 * i ] == false) { 
     return indeterminate; 
    } 
    else { 
     return(bits_[ 2 * i + i ]; 
    } 
    } 
private: 
    std::bitset<2*N> bits_;  // note: size is doubled 
};

來源

2014-04-04 00:11:38 Arun

用於在C++中存儲超大型2D數據的數據結構

回答

相關問題