最近，在一个项目中，出现了一个问题：存在一组集合（Set），必须将其有效地存储在RAM中。因为有很多套，但是内存很少。我们必须对此做些事情。
由于编写所有这些代码的语言都是C＃，即细微差别。即，标准HashSet <int>花费16个字节来存储一个数字，填充因子也会影响。有更有效的实现（有一天我会写它们），但是另一方面，您可以愚蠢地将数组存储在数组中，每个数字4个字节（您需要存储整数），这是非常有效的。但是可以进一步减少吗？
我必须马上说，我没有最佳方法的答案，也许它不存在，因为与特定数据的分配相关的因素很多。但是，我将分享一些想法：那里有哪些节省内存的选项。我还建议您在阅读本文之前先三思，毕竟，这对头脑来说是一种很好的锻炼方法。具体来说，我将问题表达如下：
有一组非负唯一整数（32位）。需要通过操作将它们有效地存储在RAM中-创建集合并获取所有元素。无需按索引获取项目，添加新项目或删除它们。
该文章将包含许多字母和数字，而不是一张图片（KDPV上的打包猫除外）。
我没有具体指出什么样的项目，什么样的任务是特定的，因为一般而言，没关系。有效的解决方案高度依赖数据。有些更适合某些人，有些适合其他人，也不要忘记工作的速度。在某个地方最好尽可能节省内存，但是在某个地方值得保持平衡。
另外，我不考虑这种形式的解决方案-将其存储在磁盘上并使用高速缓存存储热数据是愚蠢的，这是一项单独的任务。
只是为了了解我所遇到的数据量：几百万套，每套从一个元素到200万个。内存大约需要10 GB
因此，我们有了基本数据-一个整数数组，每个数字4个字节（32位）。我们将以此指标为基础。
首先，我将表达一个绝妙的主意：为了使一个数字在内存中占据少于32位，必须使用更少的位来存储它。好主意，对吧？人们为此而声名远扬。所以我更糟。
抒情离题：几年前，来自俄罗斯铁路公司的专家发现，如果您将车轮转成相同大小的车轮，火车将行驶得更快，更安静。
按大小分隔数字
一个简单的开始解决方案：每个数字可以使用1个字节存储从0到255的数字，最多2个可以存储到65536，3个可以存储到16777216。因此，第一个解决方案是：
我们创建4个数组，其中一个数组按1个字节存储数字，另一个数组按2个存储数字，第三个数组按3存储，第四个数组我建议自己猜测。
拍手，我们已经在保存。但是为什么要呆在原地？让我们使用32个数组！并将数字存储为1、2 ...位。它变得更加经济。
另一方面，什么是数组？这是指向一块内存（8个字节），长度的指针，对于C＃来说，它也是数组对象本身的内存（20个字节）的指针。总的来说，每个数组花费我们32个字节（实际上，在C＃中，一个对象至少占用24个字节，以8为增量，其中20个字节用于该对象，而4个用于剩余的或愚蠢的对齐对象）。在下文中，针对64位系统的计算。对于32位，指针少2倍，对齐方式也为4，因此几乎所有东西都比原来便宜2倍。
这是什么意思？此外，32个阵列仅会为自己占用1KB的内存。怎么办呢？一切都很简单：我们将这32个数组存储在一个数组中！
在第一个元素中，我们存储一个位数组的长度，然后存储数组本身，然后存储两位的长度，依此类推。结果，只有32个字节的开销和有效的存储空间。
一个好奇的读者（我一直很喜欢这个短语）可能会注意到一个问题：要存储一位中的数字，我们首先将2位用于长度（0、1或2），然后将2位用于数字本身。但是您只能花费2位：第一位是是否为0，第二位是是否为1。
我们只是想出了一个bitmap。您不必担心，可以使用此方法存储从0到255的数字-有一个数字-1，无-0。并在上面花费32个字节（8个字节在一个字节中* 32 = 256）。自然，随着每个新值的出现，卡的有效性开始下降。那些。要存储所有整数，我们需要536870912字节...太多了。因此，何时停止：在256，在16，在65536-取决于数据。设为256。我喜欢这个数字，它很漂亮。
那些。我们使用位图存储前256个数字，然后以位为单位存储一定长度的数字长度以及数字本身。
但是看看会发生什么：从0到511的数字需要9位存储。同时，我们有0到255之间的数字-我们已经保存了它们。那些。在9位范围内，找不到数字12，只有256个或更多。那么，如果可以存储0到255之间的数字，然后将丢失的256加到您的头部，为什么还要将它们存储在9位中呢？又节省了一位！当然，每个下一个范围也将节省1位。我们真棒！
你还能做什么？您可以查看数据。如果它们非常密集（1、2、3、5、6），那么您可以不存储数字本身，而可以存储不存在的数字（4）。那些。而不是存储有条件的5个数字，我们将存储一个。一个简单的规则：一半以上-我们保留不存在的那些，反之亦然。在哪里存放？而且长度！请看：要存储10位长的数字，我们需要11位（因为从0到1024（含0和1024）。但是同时，您可以将2048个值推入11位中，而我们仅使用1025.所以我们将存储：正长度-我们存储数字。负数-我们存储不是的。我建议读者自己做一个独立的练习来进行详细的计算（因为我不确定所有内容是否都可以放在一起，所以我装作有必要）。
结果，我们得到了：一个数组，其中前16个字节是存在0到255之间数字的位掩码，然后-带有指示的长度-我们存储数字或数字的缺失，数字本身，下一个的位长等。
在实现这一点之后，即使没有错误，我也认为您会直接进入durke，随后尝试理解此代码的程序员也会跟随您。因此，让我们尝试更多选择。
考虑订货
看。我们有一个数组。与许多人相比，他有什么？他有：元素的顺序。这是其他信息，我们还没有使用过。您能对此做什么？
您可以存储的不是元素本身，而是元素之间的差异：
1,2,3,4,8 => 1,1,1,1,4
Ie。我们按原样存储第一个，第二个存储-我们将第一个的值添加到第二个，依此类推。它给我们带来什么？而且如果我们事先对数组进行排序的事实，那么数组中的值通常会变小，并且可以存储在更少的位中。
另外，根据问题陈述，所有元素都是不同的，即我们仍然可以从差中减去1来保存位：
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
这并不困难，所以为什么不和不。
但是现在问题已经解决了。因为现在我们不能单独存储数字，而只能以相同顺序存储，那么具有数组和长度的方法不再适用。您必须提出其他建议，因为所有数字必须按顺序存储。
将数字的长度存储在数字本身之前的位中，这
不是一个坏选择。该数字从1到32位，即对于长度，我们需要5位，然后是数字本身。为了方便起见，您可以截断极端情况（好吧，为什么我们要保存在那里？ 2,3,4,5位（我们已经知道我们可以转移到不可能的地方），等等。
还是可以在数字本身中存储数字的长度？
变长量
无论我们如何第一个提出这个问题，都有一个标准的解决方案。用于将字符串存储在UTF-8和许多其他地方。意思很简单。
如果该数字在0到127之间（含0和127），我们会将其存储在1个字节中（尽管我们仅使用了7位）。如果更多，则将第8位设置为1，并以相同的方式使用下一个字节（7位，丢失-复选框和下一个）。那些。小数字将被存储在一个字节中，更多的将被存储在两个字节中，依此类推，直到5。
您可以说-fuu ...我们只是玩位，然后字节就消失了，不酷！是的，这并不酷，另一方面，使用字节仍然比使用位更容易，节省的费用少了一些，但是工作速度更高，代码更清晰。但是...每字节花费一点点不是很酷，也许有更好的解决方案？
将值用作标志
让我们跳过所有推理，立即决定。我们将其存储如下：
- 从0到252的数字将存储在一个字节中。如果更多，则：
- 如果数字是从252到252 + 256 = 508，则我们将值设置为252，在下一个字节中，数字是252（是的，我们已经知道如何移动值）
- 如果从252 + 256到252 + 256 + 65536，则设置253并使用接下来的2个字节存储数字本身-不必要的区别
- 如果从252 + 256 + 65536到252 + 256 + 65536 + 16777216，则输入254和3个字节
- 否则-255和4个字节。
这是个好方法吗？一切都是相对的。在一个字节中，我们最多可以将值推送到252，而在VLQ中，最多可以推送值127，但是在2字节中只能推送508，而在VLQ中已经是16383。如果您的数字足够密集，该方法将是不错的选择，在这里我们将赢。但是该方法的优点是可以将其调整为不同的范围。例如，如果我们知道大多数数字是从10,000到50,000，那么我们总是可以将它们存储在两个字节中，但是如果出现较大的数字，我们将写65535并使用4，实际上，我们以低效率存储为代价优化了所需范围的存储。不必要。
结论
我们研究了节省内存的主要方法（实际上，我的想象力已经用尽，但我不会承认）。这些技术可以组合在一起，用于其他任务，也可以根据情况进行修改。到底什么是最好的技术？这完全取决于您的数据。接受它们并尝试。幸运的是，没有必要一次全部完成所有工作。编写简单评估长度的代码很容易。经过评估，已经实施了您喜欢的东西。
不要忘了整个过程的速度：您准备好花很多时间准备或获取数据了吗？值得用位开始一场战斗，还是不应该走字节以下。是否足以优化频繁的情况，而使罕见的情况无法有效实施。是否有可能根据数据使用不同的存储方法（例如，在一个数组中存储多达8个字节是愚蠢的，因为附带的成本会吞噬所有收益，并且从1个字节开始-通常存储在一个元素的伪数组中，即在数）。
另外，关于压缩的几句话：在这里它不是很有效。压缩算法非常喜欢重复，但是这里没有很多。如果您使用由LZ77 + Huffman组成的有条件的Zip，LZ77不太可能出现有用的东西，但是Huffman可能会尝试保存字节。因此，Zip会变成一半没用。但是速度会非常非常下降。
我们知道我们有很多集合并且可以使用不同的切片将它们全部存储在一起的情况尚未被考虑。我承认在这里-我不确定是否会成功。立刻，我没有提出选择。但是我意识到这将是困难的。但是，您可能有不同的意见。
因此，在评论中分享您的想法，也许我错过了一些明显的大象，它将节省更多的字节，并得到这样的结果，洗涤剂广告中的家庭主妇（足够一滴）会让我们所有人羡慕不已！