c/c++语言开发共享如何有效编码/解码压缩位置描述？

我找到了一个更优雅的解决方案，使用64位整数，最多16个位置，单个循环用于编码和解码：

 #include  #include  void encode16(int dest[], int src[], int n) { unsigned long long state = 0xfedcba9876543210; for (int i = 0; i < n; i++) { int p4 = src[i] * 4; dest[i] = (state >> p4) & 15; state -= 0x1111111111111110 << p4; } } void decode16(int dest[], int src[], int n) { unsigned long long state = 0xfedcba9876543210; for (int i = 0; i < n; i++) { int p4 = src[i] * 4; dest[i] = (state >> p4) & 15; unsigned long long mask = ((unsigned long long)1 << p4) - 1; state = (state & mask) | ((state >> 4) & ~mask); } } int main(int argc, char *argv[]) { int naive[argc], compact[argc]; int n = argc - 1; for (int i = 0; i < n; i++) { naive[i] = atoi(argv[i + 1]); } encode16(compact, naive, n); for (int i = 0; i < n; i++) { printf("%d ", compact[i]); } printf("n"); decode16(naive, compact, n); for (int i = 0; i < n; i++) { printf("%d ", naive[i]); } printf("n"); return 0; } 

该代码使用64位无符号整数来保存16个值的数组，范围为0..15 。 这样的arrays可以在一个步骤中并行更新，提取值很简单，删除值有点麻烦，但仍然只有几个步骤。

您可以使用非可移植的128位整数将此方法扩展到25个位置（gcc和clang都支持__int128类型），将每个位置编码为5位，利用5 * 25 < 128这一事实，但神奇常量写起来比较麻烦。

问题的天真解决方案：创建一个数组，其中值最初等于索引。 使用正方形时，从数组中获取其值，并将所有值减少到右侧。 该解决方案的运行时间为O(n*p) ，其中n是板上的方块数， p是板上的块数。

 int codes[25]; void initCodes( void ) { for ( int i = 0; i < 25; i++ ) codes[i] = i; } int getCodeForLocation( int location ) { for ( int i = location + 1; i < 25; i++ ) codes[i]--; return codes[location]; } 

您可以尝试使用分箱来提高此代码的性能。 将板上的位置视为每个5个位置的5个箱。 每个箱具有偏移，并且箱中的每个位置具有值。 当从位置x处的bin y获取值时，则减小y以下的所有二进制位的偏移。 并且bin y中x右侧的所有值都递减。

 int codes[5][5]; int offset[5]; void initCodes( void ) { int code = 0; for ( int row = 0; row < 5; row++ ) { for ( int col = 0; col < 5; col++ ) codes[row][col] = code++; offset[row] = 0; } } int getCodeForLocation( int location ) { int startRow = location / 5; int startCol = location % 5; for ( int col = startCol+1; col < 5; col++ ) codes[startRow][col]--; for ( int row = startRow+1; row < 5; row++ ) offset[row]--; return codes[startRow][startCol] + offset[startRow]; } 

该解决方案的运行时间为O(sqrt(n) * p) 。 但是，在有25个方块的电路板上，您不会看到太多改进。 要了解为什么要考虑天真解决方案与分箱解决方案所做的实际操作。 最糟糕的情况是，天真的解决方案更新了24个位置。 最坏的情况是，分箱解决方案更新offset数组中的4个条目，以及codes数组中的4个位置。 所以这似乎是3：1的加速。 但是，分箱代码包含令人讨厌的分区/模数指令，并且总体上更复杂。 如果你幸运的话，你可能会获得2：1的加速。

如果电路板尺寸很大，例如256x256，那么装箱会很棒。 天真解决方案的最坏情况是65535个条目，而分箱将更新最多255 + 255 = 510个数组条目。 所以这肯定会弥补令人讨厌的划分和增加的代码复杂性。

其中存在尝试优化小问题集的徒劳无益。 如果n=25 sqrt(n)=5 log(n)=5则不会将O(n)更改为O(sqrt(n))或O(log(n)) 。 你得到了一个理论上的加速，但是当你考虑到大O这么轻易忽略的无数常数因素时，这几乎总是一种虚假的节省。

为了完整起见，这里的驱动程序代码可以与上面的代码段一起使用

 int main( void ) { int locations[6] = { 5,2,3,0,7,4 }; initCodes(); for ( int i = 0; i < 6; i++ ) printf( "%d ", getCodeForLocation(locations[i]) ); printf( "n" ); } 

输出： 5 2 2 0 3 1

您的编码技术具有以下属性：输出元组的每个元素的值取决于相应元素的值和输入元组的所有前面元素。 我没有看到在计算一个编码元素期间累积部分结果的方法，这个编码元素可以在计算不同的编码元素时重复使用，没有这个，编码的计算可以比o（n ² ）更有效地（时间）扩展。在要编码的元素数量中。 因此，对于您描述的问题规模，我认为您不能做得比这更好：

 typedef  element_t; void encode(element_t in[], element_t out[], int num_elements) { for (int p = 0; p < num_elements; p++) { element_t temp = in[p]; for (int i = 0; i < p; i++) { temp -= (in[i] < in[p]); } out[p] = temp; } } 

相应的解码可以像这样完成：

 void decode(element_t in[], element_t out[], int num_elements) { for (int p = 0; p < num_elements; p++) { element_t temp = in[p]; for (int i = p - 1; i >= 0; i--) { temp += (in[i] <= temp); } out[p] = temp; } } 

有些方法可以更好地扩展，其中一些方法在评论和其他答案中进行了讨论，但我最好的猜测是，您的问题规模不足以改进扩展以克服其增加的开销。

显然，这些转换本身根本不会改变表示的大小。 但是，编码表示更容易validation，因为元组中的每个位置都可以独立于其他位置进行validation。 由于这个原因，有效元组的整个空间也可以在编码forms中比在解码forms中更有效地枚举。

我继续坚持认为解码后的表格几乎与编码表格一样有效，特别是如果你想能够处理个别位置描述。 如果您编码表单的目标是支持批量枚举，那么您可以考虑以“编码”forms枚举元组，但存储并随后以解码forms使用它们。 所需的少量额外空间可能非常值得，因为不需要在阅读后执行解码，特别是如果您打算阅读其中的大量内容。

更新：

为了回应你的评论，房间里的大象是你如何将编码forms转换为单个索引的问题，如你所描述的那样，使得尽可能少的未使用索引。 我认为这是产生如此多讨论的脱节，你认为是偏离主题的，我认为你有一些关于这种假设的假设，这可以为你节省24倍的空间。

编码forms更容易转换为紧凑索引。 例如，您可以将该位置视为小端数字，其中电路板大小为其基数：

 #define BOARD_SIZE 25 typedef  index_t; index_t to_index(element_t in[], int num_elements) { // The leading digit must not be zero index_t result = in[num_elements - 1] + 1; for (int i = num_elements - 1; i--; ) { result = result * BOARD_SIZE + in[i]; } } 

当然，仍然存在差距，但我估计它们在所使用的指数值的整个范围中构成相当小的比例（并且安排这样做是因为采用小端解释的原因）。 我将反向转换作为练习:)。

要从朴素位置转换为紧凑位置，您可以迭代n元组并为每个位置p执行以下步骤：

您可以通过为忙碌状态维护n位数组来完成此操作：

这是一个实现：

 #include  #include  /* version for up to 9 positions */ #define BC9(n) ((((n)>>0)&1) + (((n)>>1)&1) + (((n)>>2)&1) +  (((n)>>3)&1) + (((n)>>4)&1) + (((n)>>5)&1) +  (((n)>>6)&1) + (((n)>>7)&1) + (((n)>>8)&1)) #define x4(m,n) m(n), m((n)+1), m((n)+2), m((n)+3) #define x16(m,n) x4(m,n), x4(m,(n)+4), x4(m,(n)+8), x4(m,(n)+12) #define x64(m,n) x16(m,n), x16(m,(n)+16), x16(m,(n)+32), x16(m,(n)+48) #define x256(m,n) x64(m,n), x64(m,(n)+64), x64(m,(n)+128), x64(m,(n)+192) static int const bc512[1 << 9] = { x256(BC9, 0), x256(BC9, 256), }; int encode9(int dest[], int src[], int n) { unsigned int busy = 0; for (int i = 0; i < n; i++) { int p = src[i]; unsigned int bit = 1 << p; //if (busy & bit) return 1; // optional validity check busy |= bit; dest[i] = p - bc512[busy & (bit - 1)]; } return 0; } /* version for up to 64 positions */ static inline int bitcount64(unsigned long long m) { m = m - ((m >> 1) & 0x5555555555555555); m = (m & 0x3333333333333333) + ((m >> 2) & 0x3333333333333333); m = (m + (m >> 4)) & 0x0f0f0f0f0f0f0f0f; m = m + (m >> 8); m = m + (m >> 16); m = m + (m >> 16 >> 16); return m & 0x3f; } int encode64(int dest[], int src[], int n) { unsigned long long busy = 0; for (int i = 0; i < n; i++) { int p = src[i]; unsigned long long bit = 1ULL << p; //if (busy & bit) return 1; // optional validity check busy |= bit; dest[i] = p - bitcount64(busy & (bit - 1)); } return 0; } int main(int argc, char *argv[]) { int src[argc], dest[argc]; int cur, max = 0, n = argc - 1; for (int i = 0; i < n; i++) { src[i] = cur = atoi(argv[i + 1]); if (max < cur) max = cur; } if (max < 9) { encode9(dest, src, n); } else { encode64(dest, src, n); } for (int i = 0; i < n; i++) { printf("%d ", dest[i]); } printf("n"); return 0; } 

核心优化是在bitcount()的实现中，您可以通过将其专门化到实际的位置数来定制您的需求。 我发布了上述高效解决方案，适用于高达9的小数和高达64的大数，但您可以为12或32个位置制定更有效的解决方案。

就时间复杂度而言，在一般情况下，我们仍然有O（n ² ） ，但对于n小值，它实际上以O（n.Log（n））或更好的方式运行，因为bitcount()的实现并行可以减少到log（n）步或更少， n最多64。

您可以查看https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive获取灵感和惊奇。

不幸的是，我仍在寻找使用此方法或类似技巧进行解码的方法......

在这个答案中，我想展示一些我自己的实现转换的想法以及一些基准测试结果。

你可以在Github上找到代码。 这些是我的主机上的结果：

 algorithm ------ total time ------ ---------- per call ----------- decoding encoding total decoding encoding total baseline 0.0391s 0.0312s 0.0703s 3.9062ns 3.1250ns 7.0312ns count 1.5312s 1.4453s 2.9766s 153.1250ns 144.5312ns 297.6562ns bitcount 1.5078s 0.0703s 1.5781s 150.7812ns 7.0312ns 157.8125ns decrement 2.1875s 1.7969s 3.9844s 218.7500ns 179.6875ns 398.4375ns bin4 2.1562s 1.7734s 3.9297s 215.6250ns 177.3438ns 392.9688ns bin5 2.0703s 1.8281s 3.8984s 207.0312ns 182.8125ns 389.8438ns bin8 2.0547s 1.8672s 3.9219s 205.4688ns 186.7188ns 392.1875ns vector 0.3594s 0.2891s 0.6484s 35.9375ns 28.9062ns 64.8438ns shuffle 0.1328s 0.3438s 0.4766s 13.2812ns 34.3750ns 47.6562ns tree 2.0781s 1.7734s 3.8516s 207.8125ns 177.3438ns 385.1562ns treeasm 1.4297s 0.7422s 2.1719s 142.9688ns 74.2188ns 217.1875ns bmi2 0.0938s 0.0703s 0.1641s 9.3750ns 7.0312ns 16.4062ns 

实现

对于我的实际项目，我可能会使用shuffle实现，因为它是最快的，不依赖于任何不可移植的扩展（例如Intel内在函数）或实现细节（例如128位整数的可用性）。

要从（5,2,3,0,7,4）到（5,2,2,0,3,1）你必须：