c - 在 C 中高效地实现三元数据类型的数组

Question

我需要在 C 语言中尽可能高效地实现三元数据类型的“大”数组(~1800 个元素)以进行密码学研究。我想到了以下几点:

使用任意大小的整数数组，用2个Bits分别代表一个元素

所以我会

typedef uint32_t block;
const int blocksize = sizeof(block)<<3;

block dataArray[3]; // 3*32 bit => 48 Elements

uint8_t getElementAt(block *data, int position)
{
    position = position * 2;
    return (data[position/blocksize] >> (position % blocksize)) & 3;
}

返回 0..2，我可以将其映射到我的三个值。

使用 uint8_t 数组直接寻址元素。

uint8_t data[48];

当然，这需要至少四倍的 RAM，但寻址和设置可能更有效 - 是吗？

这两种解决方案中是否还有我遗漏的任何其他好的可能性或特殊警告？

Answer 1

答案取决于数组的大小，以及您希望如何优化。我勾画了一些场景:

运行时，小数组。

只需使用unsigned long arr[N]。仅在机器字边界上读取是最快的，但会占用大量内存。当内存使用量太大时，您实际上不想这样做，因为缓存性能超过对齐读取。

运行时，大数组。

使用unsigned char arr[N]。这将使您以相当快的速度进行快速读/写。

良好的内存使用率，速度一般。

使用 unsigned long arr[N] 并将每个 trit 存储为两位，使用移位和掩码解包。

更好的内存使用，慢。

使用unsigned long arr[N]，并存储 floor(CHAR_BIT * sizeof(long) * log(2)/log(3)) 数，通过存储base-3 中的数字。您可以使用此方法将 20 个 trits 打包成 32 位。

最佳内存使用，可怕。

使用 bignum 实现将所有数字存储为一个以 3 为基数的数字。