c# - 如何在一个值中构建具有变量 1 到 4 字节的结构？

Question

我尝试做的事情:

我想在 RAM 中存储大量数据。为了更快的访问和更少的内存占用，我需要使用一个结构值数组:

MyStruct[] myStructArray = new MyStruct[10000000000];

现在我想在 MyStruct 中存储一个、两个、三个或四个字节的无符号整数值。但它应该只使用尽可能少的内存量。当我将一个值存储一个字节时，它应该只使用一个字节等等。

我可以用类来实现它，但这在这里是不合适的，因为指向对象的指针在 64 位系统上需要 8 个字节。所以最好只为每个数组条目存储 4 个字节。但我只想在需要时存储/使用一个/两个/三个字节。所以我不能使用一些花哨的类。

我也不能使用一个包含一个字节的数组，一个包含两个字节的数组等等，因为我需要值的特殊顺序。而且这些值非常复杂，因此在切换到另一个数组时存储额外的引用也无济于事。

无论我只需要存储一个字节，大约 60% 的时间存储两个字节，大约 25% 的时间存储三个字节，是否有可能想要存储 4 字节 uint 数组的唯一方法或唯一方法？

Answer 1

这是不可能的。 CLR 将如何处理以下表达式？

myStructArray[100000]

如果元素的大小可变，CLR 无法知道第 100000 个元素的地址。因此，数组元素始终具有固定大小。

如果您不需要 O(1) 访问权限，您可以在 byte[] 之上实现可变长度元素并自行搜索数组。

您可以将列表拆分为 1000 个子列表，这些子列表单独打包。这样您就可以获得 O(n/2000) 的平均搜索性能。也许这在实践中已经足够好了。

“压缩”数组平均只能在 O(n/2) 中搜索。但是，如果您的部分数组是大小的 1/1000，它将变为 O(n/2000)。您可以在 O(1) 中选择部分数组，因为它们的大小都相同。

此外，您还可以调整部分数组的数量，使它们的大小分别约为 1k 个元素。那时数组对象的开销和对它的引用消失了。这将为您提供 O(1000/2 + 1) 查找性能，我认为这比 O(n/2) 有了很大的改进。这是一个恒定时间查找(有一个很大的常数)。