聲明一個巨大的動態數組與細胞[C++]

Question

我有這個項目，我正在努力。下列條件適用

1. 在這個項目中我需要創建一個巨大的數組（希望我能創造一個大如〜7.13e + 17，但這一目標仍然高達遙遙領先。）
2. 數組中的每個單元格可以包含以下三個值之一：0,1,2
3. 我使用C++作爲我的語言。

我嘗試使用正常動態數組命令

int * p; 
int i;  
i=[size]; //This is calculated somewhere else. 
p= new (nothrow) int[i]; 

但據我所知，這個陣列使得與INT的最大尺寸的可能的最大大小的陣列。如果我改變我的代碼，並使用下面的代碼

long long * p; 
long long i;  
i=[size]; //This is calculated somewhere else. 
p= new (nothrow) long long [i]; 

然後數組中的每個單元的類型是「長長」，使得陣列非常沉重的記憶。 有沒有什麼辦法用long long創建一個數組來確定數組中的單元的數量並且讓每個單元的大小爲int？

非常感謝， Uriel。

編輯：進一步的信息。

1. 這個問題主要是理論上的，它是我碩士論文的一部分。我仍然希望這個計劃儘可能地發揮作用。
2. 我現在的步驟是使用2.56e + 09項的數組進行這項工作，快速計算顯示我們正在討論的數組至少有0.6千兆字節，這是我的系統應該能夠應對的。然而，即使所需的空間數量真的達到4.5GB，我仍無法用我當前的編碼解決方案實現這一目標。

Answer 1

是否有任何方式來創建使用長長來確定所述陣列中細胞的數目和大小具有INT的每一個細胞的陣列？

沒有理由數組的類型必須與用於指定大小的變量的類型相同。因此，使用long long作爲指定大小的變量，然後使用int作爲數組類型。

int * p; 
long long i;  
i=[size]; //This is calculated somewhere else. 
p= new (nothrow) int [i]; 

---

不過，我很擔心，當你說你需要創建一個數組「大如〜7.13e + 17」。我不知道你的意思是字節還是元素，但是對於一個直線陣列來說，這種方式是非常巨大的。這正在進入PB級數據領域。

在32位程序中，這根本不可能。從理論上講，你可以有一個數組達到幾千兆字節（儘管在實踐中大多數時候會少得多）。

在一個64位程序中，理論上你可以分配一個很大的數組，據我所知。然而，我懷疑大多數機器實際上可以處理它。由於該數據量遠遠超過機器中的RAM，因此操作系統將被迫將該數組的大部分推送到頁面文件中。但是，PB級大小的頁面文件現在遠遠超過大多數典型機器上的硬盤空間。

無論哪種方式，您可能需要認真考慮一個不同的方案，而不是一次只分配整個巨大的數組。

Answer 2

由於所有的值都小於255，所以您可能希望將此數組作爲char。 在任何情況下，指針類型都不會規定相同的最大可分配大小。

Answer 3

由於有一個有限的值列表，所以可能只使用一個char數組。一個字節可以很容易地保存三個不同的值。

值：
0 - > 0
1 - > 1
2.2 - > 2

存儲值：

char values[i]; 
values[i] = 0; 
values[i] = 1; 
values[i] = 2; // really the 2.2 value 

檢索值：

int zero = values[i] - 0; 
int one = values[i] - 0; 
double two_point_two values[i] - 0; 
if (two_point_two == 2) 
    two_point_tow = 2.2; 

小需要額外的注意力來獲得最後的值，但數組會很小（1字節）。

數組分配：

int main() 
{ 
    // static allocation requires a const size 
    const int static_array_size = 100; 
    char static_array[static_array_size]; 
    std::cout << "static array size is:" << sizeof(static_array) << std::endl; 

    // heap allocation can vary in size (i.e. non const heap_array_size variable) 
    int heap_array_size = 200; 
    char* heap_array = new char[heap_array_size]; 
    std::cout << "static array size is:" << sizeof(heap_array_size) << std::endl; 
} 

Answer 4

既然你想最大限度地提高封裝密度，你可能是最好關閉使用位字段：

struct item_pack { 
    char a:2; 
    char b:2: 
    char c:2; 
    char d:2; 
}; 

然後，您可以創建這些數組，並使用代理對象以支持讀寫個別項目 - 條件是你可以用代理對象做多少限制，所以你必須小心你如何使用它。有些關於vector<bool>的文章應該提供一些合理的提示 - 其大部分特徵來自這種通用類型的實現。儘管通用容器存在缺點，但它可以在有限的範圍內工作，並且比大多數明顯的替代方案提供更緊密的信息包裝。

Answer 5

但據我所知，這個數組產生了一個最大尺寸爲int的數組。如果我更改我的代碼並使用以下代碼

這絕對是錯誤的！數組的大小完全獨立於數組類型的最大值。

所以沒有必要使它成爲long long陣列。相反，你甚至應該使它成爲一個char數組，甚至更少。

如果你只需要存儲三個不同的值，你應該玩char或任何其他類型的位。然後製作這些數組。

A char通常是1個字節，所以8位。要存儲3個值，您需要2位;因此您可以將4個值存儲在char中。

使用binary masks你應該找出一種方法來優化它。

Answer 6

在這個項目中我需要創建一個巨大的數組（希望我能創造一個大如〜7.13e + 17，但這一目標仍然高達遙遙領先。）

那調用創建一個專用結構，一個la digital tree（或b-tree），鍵是索引，以避免執行大量分配。

大量分配和特別是重新分配可能會導致不必要的memory fragmentation。如果將大數組分成更小的塊，那麼不僅數組擴展變得容易，而且稀疏數組的呈現變得可能。

N.B. ~7.13e+17大約有60位長。你甚至有硬件可以支持那麼多的RAM嗎？這並不是說我密切關注着行業，但是我簡要地聽說過使用58位地址總線的NUMA拱形結構 - 但沒有任何關於60位拱形結構的東西。

數組內的每個單元格可以包含三個值之一：0,1,2.2。

如果單元格可能只包含3個值（2.2可以表示爲2），使其成爲2位信息。這意味着您可以將數值打包成uint32_t 32值。

您可以嘗試找到一些現有的數字樹實現（或自己推出）並將其用作索引的關鍵高位。原始索引的剩餘位是樹葉的索引，它將是一個具有打包值的數組。爲了舉例說明代替特里結構的使用std::map，未測試：

enum { 
    LS_BITS = 16, 
    MS_BITS = 64-LS_BITS 
}; 

enum { 
    VALUE_BITS = 2, 
    VALUE_MASK = ((1<<VALUE_BITS)-1) 
}; 

// this represents an array of `1<<LS_BITS` values 
struct leaf_node { 
    uint64_t packed_data[ ((1<<LS_BITS)*VALUE_BITS)/(sizeof(uint64_t)*8) ]; 
}; 

// that should be a trie, to provide faster look-up 
typedef std::map< uint64_t, leaf_node > big_array_type; 

void 
big_array_set_value(big_array_type &b, uint64_t index, uint64_t value) 
{ 
    leaf_node &n = b[index >> LS_BITS]; 
    uint64_t li = index & ((1<<LS_BITS)-1); 
    li *= VALUE_BITS; // convert into bit offset 
    uint64_t &x = n.packed_data[ li/(sizeof(uint64_t)*8) ]; 
    li %= (sizeof(uint64_t)*8); 
    x = (x & (VALUE_MASK<<li)) | (value << li); 
} 

int 
big_array_get_value(big_array_type &b, uint64_t index, uint64_t value) 
{ 
    leaf_node &n = b[index >> LS_BITS]; 
    uint64_t li = index & ((1<<LS_BITS)-1); 
    li *= VALUE_BITS; // convert into bit offset 
    uint64_t &x = n.packed_data[ li/(sizeof(uint64_t)*8) ]; 
    li %= (sizeof(uint64_t)*8); 
    return (x >> li) & VALUE_MASK; 
} 

這樣一個靜止廢物的信息比特0.5自存儲爲2個比特什麼允許4個值，但只有3被使用。這也可以得到改善，但是訪問性能成本要高得多。

Answer 7

用於指定數組大小的大小需要爲size_t。 new表達式中使用的類型是數組元素的類型。無論您的示例中的i的類型如何，它都將轉換爲size_t以創建陣列。

現在在一臺32位機器上，最大的size_t大概是4e + 9，所以製作一個大小爲1e + 17的數組是正確的。在64位計算機上，理論上size_t可能會上升到1e + 19左右，但您無法在任何位置接近該內存量，因此分配將失敗。

因此，您需要某種稀疏的數據結構，正如其他人所討論的。這裏的關鍵是決定你的3個值中哪一個最常見，並且只存儲數組是其他2個值之一的值。您可以使用std :: map來保存這些值（甚至支持使用[index]語法）或其他類型的值，具體取決於您想要執行的操作以及數據的細節。