我有一个非常具体的数据集，我需要以最紧凑的方式将其存储为字节数组。它是一个不断增加的实时整数流，通常是一个，但并不总是一个。每个整数值都有一个字节值标记。可能存在具有相同值和标签的值，但我只需要存储不同的值。仅支持的操作是添加新元素、删除和检查元素是否存在 - 我保留此数据集以检查最近是否“看到”了某些对。
一些示例数据:
# | 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 个或多个字节用于与先前值的“delta”。 这样我需要存储第一个值，在上述情况下为 1000，然后存储增量 - #1 为 0，#2 为 1，#4 为 1，#5 为 1，#6 为 2 等。
大多数增量很小，为 1-10，所以我只能将其存储在一个字节中 - 如果值足够小以适合 7 位，则第一位是标志，否则 - 接下来的 7 位存储一个值的字节数delta占用。
也许有更好、更紧凑的方法？
最佳答案
由于您只有 127 个不同的标签值，因此您可以维护 127 个不同的表，每个表对应一个标签，从而使您不必存储标签。在每个表中，您仍然可以对增量使用漂亮的技巧。
关于algorithm - 用于排序的成对数组(整数，字节)的紧凑数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34047122/