只有3個不同的值優化數組？如何設計？

我想在C++中的資源不敏感的功能。我正在實現一個有10000條記錄的數組，但是任何記錄都只有可能的3個值，即0,1,2。所以我想知道，而不是爲10000個實例存儲內存所有3個一起，如果一些如何我可以保存每個實例和邏輯管理。不確定如何實施。只有3個不同的值優化數組？如何設計？

例如我的數組會是這樣的。

{1,0,0,1,2,1,1,1,0,2,2,0,0,0,2，......}

我們可能去超過10000條記錄也

來源

2012-09-22 Pritesh

3代表0,1和2中每一個的「count」的數組？ –

@KingsIndian我沒有明白，請描述.. – Pritesh

你需要澄清一點。用一個例子來更好地描述記錄，它的價值以及你想要達到的目標。 –

這聽起來像你可以只創建的2500個字節數組，每個字節的4個值（每個值需2位）。使用位移/屏蔽來訪問任何單個值。我懷疑這會比對價值進行分組的方案更簡單，並且對於訪問將更加「陣列化」。當然，很難確切地說，因爲我們不知道你需要怎樣處理這些值。

你可以實際上適合5點的值到各字節（如3 是243），所以你只需要大小2000字節數組...但接入代碼將是有點棘手。我會抵制這種額外的複雜性，除非你真的需要。

另外，如果值相對稀疏 - 例如，幾乎所有東西都是0，只有幾個1和2 - 那麼你顯然可以更有效地存儲它。

編輯：好的，所以我沒有做過很長一段時間的任何C++，但它會是這樣的：

// Entirely untested. Please test thoroughly, and make sure you understand it 
// before using it. 
int get_value(unsigned index) 
{ 
    // TODO: Argument validation 
    unsigned raw_index = index/4; 
    unsigned index_within_byte = (index % 4) * 2; 

    return (array[raw_index] >> index_within_byte) & 3; 
} 

void set_value(unsigned index, int value) 
{ 
    // TODO: Argument validation 
    unsigned raw_index = index/4; 
    unsigned index_within_byte = (index % 4) * 2; 

    int mask = 0xff^(3 << index_within_byte); 
    array[raw_index] = (array[raw_index] & mask) | (value << index_within_byte); 
}

編輯：關於它的進一步思考，你甚至可能希望創建一個數組uint32_t或uint64_t而不是字節，並將16或32個「真實」值放入每個數組元素中。我懷疑大多數處理器可能會提高內存訪問效率。

來源

2012-09-22 08:07:02

我同意。一些抵消數學，掩蔽和位移將使這個最有效的方式來做到這一點。 – WhozCraig

@CraigNelson不清楚鋤頭是否實施「偏移數學，掩蔽和位移」。一個例子會有很大幫助。 – Pritesh

@JonSkeet如何做這種位移/遮罩？ – Pritesh

製作一個向量std::pair<int, int>，使得該對中的first包含0,1或2並且second包含該特定元素已被看到的次數。

因此，對於你的例子

{1，0，0，1，2，1，1，1，0，2，2，0，0，0，2，..... ........}

可將其存儲象

{< 1,1>，< 0,2>，< 1,1>，< 2,1> ，< 1,3>，< 0,1>，< 2,2>，< 0,3>，< 2，...> ...}

你可以看到這是件好事，只有當有大量連續重複的，如果您不需要直接訪問。

來源

2012-09-22 08:13:27

只有3個不同的值優化數組？如何設計？

回答

相關問題