排序數組對（整數，字節）的緊湊數據結構？

我有一個相當特定的數據集，我需要以最緊湊的方式存儲爲字節數組。它是一個不斷增加的整數直播流，通常是一個整數，但並不總是一個整數。每個整數值都有一個字節值的標籤。可能存在具有相同值和標記的值，但我只需要存儲區別。只有支持的操作是添加新元素，刪除並檢查元素是否存在 - 我保留這個數據集以檢查最近是否有一對「已見」。排序數組對（整數，字節）的緊湊數據結構？

一些樣本數據：

# | value | tag | 
1 | 1000 | 0 | 
2 | 1000 | 1 | 
3 | 1000 | 2 | 
4 | 1001 | 0 | 
5 | 1002 | 2 | 
6 | 1004 | 1 | 
7 | 1004 | 2 | 
8 | 1005 | 0 |

正如我所說的，這是一個實時數據流，但我只能承受存儲最後幾十萬。我們的目標是在存儲（和RAM）中儘可能提高內存的使用效率，操作可能會花費很多。

如果我沒有標籤，我可以存儲範圍或值，（1000-1002），（1002-1005）等，通常有一排約5-6值無間隙。但標籤混淆了這一切。

我目前的做法是在幾個字節的每個值+標記對編碼 - 用於標籤和用於從以前的值「增量」 1個或多個字節的一個字節。這種方式我需要存儲第一個值，1000以上的情況下，並比我存儲增量-0爲＃1，＃2,1爲＃4,1爲＃5，2爲＃6等。

大多數增量是小1-10，所以我可以將它存儲在一個字節中 - 如果值足夠小以適應7位，則第一位是標誌，否則 - 接下來的7位存儲字節delta如何佔用的值。

也許有更好，更緊湊的方法？

來源

2015-12-02 user1987133

請給我們你的整數和你的標籤的範圍。請告訴我們是否還有其他可以利用的東西。例如，這些標籤是否總是在一系列相同的整數內增加或至少不減少？ –

範圍 - 大多數是0 - 1000000.但有時可能會出現Int.MaxValue。但最通常我存儲一個幾乎連續的值的數組，相差1-2。標籤是0-255，一個字節，沒有排序。但是我可以通過標籤對相同的整數進行分類。 – user1987133

絕對限制 - 值可以是任何非負的int。標籤 - 可以是任何非負的字節值，不含任何順序。 – user1987133

因爲你只有127個不同的變量值，可以維持127頁不同的表，每個標籤，從而節省自己不必存儲標籤。在每個表格中，您仍然可以使用帶有增量變化的妙用技巧。

來源

2015-12-02 16:42:25

讓對(value, tag)其中value是uint32和tag是uint8是存儲在數據結構的典型項目。

使用關聯數組數據結構將uint32映射到uint16的數組列表。用C++術語來說，數據結構如下。

std::map<std::uint32_t, std::vector<std::uint16_t>>

每個陣列列表保持與不同的值排序，並從不超過一個尺寸的2 。

讓D成爲這個數據結構的一個實例。我們將(value, tag)存儲在數組列表D[value >> 8]中作爲(static_cast<std::uint16_t>(value) << 8) + tag。

這個想法基本上是數據被分頁。最重要的3個字節value確定頁面，然後value的最低有效字節和tag的單字節存儲在頁面中。

這應該非常有效地利用您的數據結構，因爲假設每個頁面都擁有很多值，則每個項目使用2個字節。

來源

2015-12-02 17:11:47

排序數組對（整數，字節）的緊湊數據結構？

回答

相關問題