c ++优化整数数组

a43*_*511 27 c++ arrays optimization multidimensional-array

我有一个int16_t的2D查找表.

int16_t my_array[37][73] = {{**DATA HERE**}}

我有一个值的混合,范围从int8_t的范围之上到刚好低于int8_t的范围,并且一些值重复自己.我试图减少这个查找表的大小.

到目前为止我所做的是将每个int16_t值拆分为两个int8_t值,以显示浪费的字节.

int8_t part_1 = original_value >> 4;
int8_t part_2 = original_value & 0x0000FFFF;

// If the upper 4 bits of the original_value were empty         
if(part_1 == 0) wasted_bytes_count++;
Run Code Online (Sandbox Code Playgroud)

我可以轻松删除浪费一个字节空间的零值int8_t,我也可以删除重复值,但我的问题是如何在保留基于两个索引查找的能力的同时删除这些值?

我打算将其转换为一维数组,并在每个重复值后添加一个数字,表示已删除的重复数量,但我正在努力解决我将如何识别什么是查找值以及什么是重复计数.此外,通过剥离浪费的字节的零int8_t值进一步复杂化.

编辑:此数组已存储在ROM中.RAM比ROM更受限制,因此它已经存储在ROM中.

编辑:我会尽快发布这个问题的赏金.我需要一个完整的答案,如何存储信息并检索它.只要我可以获得相同的值,它就不需要是2D数组.

编辑:添加下面的实际数组:

{150,145,140,135,130,125,120,115,110,105,100,95,90,85,80,75,70,65,60,55,50,45,40,35,30,25,20,15,10,5,0,-4,-9,-14,-19,-24,-29,-34,-39,-44,-49,-54,-59,-64,-69,-74,-79,-84,-89,-94,-99,104,109,114,119,124,129,134,139,144,149,154,159,164,169,174,179,175,170,165,160,155,150}, \
{143,137,131,126,120,115,110,105,100,95,90,85,80,75,71,66,62,57,53,48,44,39,35,31,27,22,18,14,9,5,1,-3,-7,-11,-16,-20,-25,-29,-34,-38,-43,-47,-52,-57,-61,-66,-71,-76,-81,-86,-91,-96,101,107,112,117,123,128,134,140,146,151,157,163,169,175,178,172,166,160,154,148,143}, \
{130,124,118,112,107,101,96,92,87,82,78,74,70,65,61,57,54,50,46,42,38,34,31,27,23,19,16,12,8,4,1,-2,-6,-10,-14,-18,-22,-26,-30,-34,-38,-43,-47,-51,-56,-61,-65,-70,-75,-79,-84,-89,-94,100,105,111,116,122,128,135,141,148,155,162,170,177,174,166,159,151,144,137,130}, \
{111,104,99,94,89,85,81,77,73,70,66,63,60,56,53,50,46,43,40,36,33,30,26,23,20,16,13,10,6,3,0,-3,-6,-9,-13,-16,-20,-24,-28,-32,-36,-40,-44,-48,-52,-57,-61,-65,-70,-74,-79,-84,-88,-93,-98,103,109,115,121,128,135,143,152,162,172,176,165,154,144,134,125,118,111}, \
{85,81,77,74,71,68,65,63,60,58,56,53,51,49,46,43,41,38,35,32,29,26,23,19,16,13,10,7,4,1,-1,-3,-6,-9,-13,-16,-19,-23,-26,-30,-34,-38,-42,-46,-50,-54,-58,-62,-66,-70,-74,-78,-83,-87,-91,-95,100,105,110,117,124,133,144,159,178,160,141,125,112,103,96,90,85}, \
{62,60,58,57,55,54,52,51,50,48,47,46,44,42,41,39,36,34,31,28,25,22,19,16,13,10,7,4,2,0,-3,-5,-8,-10,-13,-16,-19,-22,-26,-29,-33,-37,-41,-45,-49,-53,-56,-60,-64,-67,-70,-74,-77,-80,-83,-86,-89,-91,-94,-97,101,105,111,130,109,84,77,74,71,68,66,64,62}, \
{46,46,45,44,44,43,42,42,41,41,40,39,38,37,36,35,33,31,28,26,23,20,16,13,10,7,4,1,-1,-3,-5,-7,-9,-12,-14,-16,-19,-22,-26,-29,-33,-36,-40,-44,-48,-51,-55,-58,-61,-64,-66,-68,-71,-72,-74,-74,-75,-74,-72,-68,-61,-48,-25,2,22,33,40,43,45,46,47,46,46}, \
{36,36,36,36,36,35,35,35,35,34,34,34,34,33,32,31,30,28,26,23,20,17,14,10,6,3,0,-2,-4,-7,-9,-10,-12,-14,-15,-17,-20,-23,-26,-29,-32,-36,-40,-43,-47,-50,-53,-56,-58,-60,-62,-63,-64,-64,-63,-62,-59,-55,-49,-41,-30,-17,-4,6,15,22,27,31,33,34,35,36,36}, \
{30,30,30,30,30,30,30,29,29,29,29,29,29,29,29,28,27,26,24,21,18,15,11,7,3,0,-3,-6,-9,-11,-12,-14,-15,-16,-17,-19,-21,-23,-26,-29,-32,-35,-39,-42,-45,-48,-51,-53,-55,-56,-57,-57,-56,-55,-53,-49,-44,-38,-31,-23,-14,-6,0,7,13,17,21,24,26,27,29,29,30}, \
{25,25,26,26,26,25,25,25,25,25,25,25,25,26,25,25,24,23,21,19,16,12,8,4,0,-3,-7,-10,-13,-15,-16,-17,-18,-19,-20,-21,-22,-23,-25,-28,-31,-34,-37,-40,-43,-46,-48,-49,-50,-51,-51,-50,-48,-45,-42,-37,-32,-26,-19,-13,-7,-1,3,7,11,14,17,19,21,23,24,25,25}, \
{21,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,21,20,18,16,13,9,5,1,-3,-7,-11,-14,-17,-18,-20,-21,-21,-22,-22,-22,-23,-23,-25,-27,-29,-32,-35,-37,-40,-42,-44,-45,-45,-45,-44,-42,-40,-36,-32,-27,-22,-17,-12,-7,-3,0,3,7,9,12,14,16,18,19,20,21,21}, \
{18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,18,17,16,14,10,7,2,-1,-6,-10,-14,-17,-19,-21,-22,-23,-24,-24,-24,-24,-23,-23,-23,-24,-26,-28,-30,-33,-35,-37,-38,-39,-39,-38,-36,-34,-31,-28,-24,-19,-15,-10,-6,-3,0,1,4,6,8,10,12,14,15,16,17,18,18}, \
{16,16,17,17,17,17,17,17,17,17,17,16,16,16,16,16,16,15,13,11,8,4,0,-4,-9,-13,-16,-19,-21,-23,-24,-25,-25,-25,-25,-24,-23,-21,-20,-20,-21,-22,-24,-26,-28,-30,-31,-32,-31,-30,-29,-27,-24,-21,-17,-13,-9,-6,-3,-1,0,2,4,5,7,9,10,12,13,14,15,16,16}, \
{14,14,14,15,15,15,15,15,15,15,14,14,14,14,14,14,13,12,11,9,5,2,-2,-6,-11,-15,-18,-21,-23,-24,-25,-25,-25,-25,-24,-22,-21,-18,-16,-15,-15,-15,-17,-19,-21,-22,-24,-24,-24,-23,-22,-20,-18,-15,-12,-9,-5,-3,-1,0,1,2,4,5,6,8,9,10,11,12,13,14,14}, \
{12,13,13,13,13,13,13,13,13,13,13,13,12,12,12,12,11,10,9,6,3,0,-4,-8,-12,-16,-19,-21,-23,-24,-24,-24,-24,-23,-22,-20,-17,-15,-12,-10,-9,-9,-10,-12,-13,-15,-17,-17,-18,-17,-16,-15,-13,-11,-8,-5,-3,-1,0,1,1,2,3,4,6,7,8,9,10,11,12,12,12}, \
{11,11,11,11,11,12,12,12,12,12,11,11,11,11,11,10,10,9,7,5,2,-1,-5,-9,-13,-17,-20,-22,-23,-23,-23,-23,-22,-20,-18,-16,-14,-11,-9,-6,-5,-4,-5,-6,-8,-9,-11,-12,-12,-12,-12,-11,-9,-8,-6,-3,-1,0,0,1,1,2,3,4,5,6,7,8,9,10,11,11,11}, \
{10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,9,9,7,6,3,0,-3,-6,-10,-14,-17,-20,-21,-22,-22,-22,-21,-19,-17,-15,-13,-10,-8,-6,-4,-2,-2,-2,-2,-4,-5,-7,-8,-8,-9,-8,-8,-7,-5,-4,-2,0,0,1,1,1,2,2,3,4,5,6,7,8,9,10,10,10}, \
{9,9,9,9,9,9,9,10,10,9,9,9,9,9,9,8,8,6,5,2,0,-4,-7,-11,-15,-17,-19,-21,-21,-21,-20,-18,-16,-14,-12,-10,-8,-6,-4,-2,-1,0,0,0,-1,-2,-4,-5,-5,-6,-6,-5,-5,-4,-3,-1,0,0,1,1,1,1,2,3,3,5,6,7,8,8,9,9,9}, \
{9,9,9,9,9,9,9,9,9,9,9,9,8,8,8,8,7,5,4,1,-1,-5,-8,-12,-15,-17,-19,-20,-20,-19,-18,-16,-14,-11,-9,-7,-5,-4,-2,-1,0,0,1,1,0,0,-2,-3,-3,-4,-4,-4,-3,-3,-2,-1,0,0,0,0,0,1,1,2,3,4,5,6,7,8,8,9,9}, \
{9,9,9,8,8,8,9,9,9,9,9,8,8,8,8,7,6,5,3,0,-2,-5,-9,-12,-15,-17,-18,-19,-19,-18,-16,-14,-12,-9,-7,-5,-4,-2,-1,0,0,1,1,1,1,0,0,-1,-2,-2,-3,-3,-2,-2,-1,-1,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8,9}, \
{8,8,8,8,8,8,9,9,9,9,9,9,8,8,8,7,6,4,2,0,-3,-6,-9,-12,-15,-17,-18,-18,-17,-16,-14,-12,-10,-8,-6,-4,-2,-1,0,0,1,2,2,2,2,1,0,0,-1,-1,-1,-2,-2,-1,-1,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8}, \
{8,8,8,8,9,9,9,9,9,9,9,9,9,8,8,7,5,3,1,-1,-4,-7,-10,-13,-15,-16,-17,-17,-16,-15,-13,-11,-9,-6,-5,-3,-2,0,0,0,1,2,2,2,2,1,1,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,-1,0,0,1,3,4,5,7,7,8}, \
{8,8,9,9,9,9,10,10,10,10,10,10,10,9,8,7,5,3,0,-2,-5,-8,-11,-13,-15,-16,-16,-16,-15,-13,-12,-10,-8,-6,-4,-2,-1,0,0,1,2,2,3,3,2,2,1,0,0,0,0,0,0,0,0,0,0,-1,-1,-2,-2,-2,-2,-2,-1,0,0,1,3,4,6,7,8}, \
{7,8,9,9,9,10,10,11,11,11,11,11,10,10,9,7,5,3,0,-2,-6,-9,-11,-13,-15,-16,-16,-15,-14,-13,-11,-9,-7,-5,-3,-2,0,0,1,1,2,3,3,3,3,2,2,1,1,0,0,0,0,0,0,0,-1,-1,-2,-3,-3,-4,-4,-4,-3,-2,-1,0,1,3,5,6,7}, \
{6,8,9,9,10,11,11,12,12,12,12,12,11,11,9,7,5,2,0,-3,-7,-10,-12,-14,-15,-16,-15,-15,-13,-12,-10,-8,-7,-5,-3,-1,0,0,1,2,2,3,3,4,3,3,3,2,2,1,1,1,0,0,0,0,-1,-2,-3,-4,-4,-5,-5,-5,-5,-4,-2,-1,0,2,3,5,6}, \
{6,7,8,10,11,12,12,13,13,14,14,13,13,11,10,8,5,2,0,-4,-8,-11,-13,-15,-16,-16,-16,-15,-13,-12,-10,-8,-6,-5,-3,-1,0,0,1,2,3,3,4,4,4,4,4,3,3,3,2,2,1,1,0,0,-1,-2,-3,-5,-6,-7,-7,-7,-6,-5,-4,-3,-1,0,2,4,6}, \
{5,7,8,10,11,12,13,14,15,15,15,14,14,12,11,8,5,2,-1,-5,-9,-12,-14,-16,-17,-17,-16,-15,-14,-12,-11,-9,-7,-5,-3,-1,0,0,1,2,3,4,4,5,5,5,5,5,5,4,4,3,3,2,1,0,-1,-2,-4,-6,-7,-8,-8,-8,-8,-7,-6,-4,-2,0,1,3,5}, \
{4,6,8,10,12,13,14,15,16,16,16,16,15,13,11,9,5,2,-2,-6,-10,-13,-16,-17,-18,-18,-17,-16,-15,-13,-11,-9,-7,-5,-4,-2,0,0,1,3,3,4,5,6,6,7,7,7,7,7,6,5,4,3,2,0,-1,-3,-5,-7,-8,-9,-10,-10,-10,-9,-7,-5,-4,-1,0,2,4}, \
{4,6,8,10,12,14,15,16,17,18,18,17,16,15,12,9,5,1,-3,-8,-12,-15,-18,-19,-20,-20,-19,-18,-16,-15,-13,-11,-8,-6,-4,-2,-1,0,1,3,4,5,6,7,8,9,9,9,9,9,9,8,7,5,3,1,-1,-3,-6,-8,-10,-11,-12,-12,-11,-10,-9,-7,-5,-2,0,1,4}, \
{4,6,8,11,13,15,16,18,19,19,19,19,18,16,13,10,5,0,-5,-10,-15,-18,-21,-22,-23,-22,-22,-20,-18,-17,-14,-12,-10,-8,-5,-3,-1,0,1,3,5,6,8,9,10,11,12,12,13,12,12,11,9,7,5,2,0,-3,-6,-9,-11,-12,-13,-13,-12,-11,-10,-8,-6,-3,-1,1,4}, \
{3,6,9,11,14,16,17,19,20,21,21,21,19,17,14,10,4,-1,-8,-14,-19,-22,-25,-26,-26,-26,-25,-23,-21,-19,-17,-14,-12,-9,-7,-4,-2,0,1,3,5,7,9,11,13,14,15,16,16,16,16,15,13,10,7,4,0,-3,-7,-10,-12,-14,-15,-14,-14,-12,-11,-9,-6,-4,-1,1,3}, \
{4,6,9,12,14,17,19,21,22,23,23,23,21,19,15,9,2,-5,-13,-20,-25,-28,-30,-31,-31,-30,-29,-27,-25,-22,-20,-17,-14,-11,-9,-6,-3,0,1,4,6,9,11,13,15,17,19,20,21,21,21,20,18,15,11,6,2,-2,-7,-11,-13,-15,-16,-16,-15,-13,-11,-9,-7,-4,-1,1,4}, \
{4,7,10,13,15,18,20,22,24,25,25,25,23,20,15,7,-2,-12,-22,-29,-34,-37,-38,-38,-37,-36,-34,-31,-29,-26,-23,-20,-17,-13,-10,-7,-4,-1,2,5,8,11,13,16,18,21,23,24,26,26,26,26,24,21,17,12,5,0,-6,-10,-14,-16,-16,-16,-15,-14,-12,-10,-7,-4,-1,1,4}, \
{4,7,10,13,16,19,22,24,26,27,27,26,24,19,11,-1,-15,-28,-37,-43,-46,-47,-47,-45,-44,-41,-39,-36,-32,-29,-26,-22,-19,-15,-11,-8,-4,-1,2,5,9,12,15,19,22,24,27,29,31,33,33,33,32,30,26,21,14,6,0,-6,-11,-14,-15,-16,-15,-14,-12,-9,-7,-4,-1,1,4}, \
{6,9,12,15,18,21,23,25,27,28,27,24,17,4,-14,-34,-49,-56,-60,-60,-60,-58,-56,-53,-50,-47,-43,-40,-36,-32,-28,-25,-21,-17,-13,-9,-5,-1,2,6,10,14,17,21,24,28,31,34,37,39,41,42,43,43,41,38,33,25,17,8,0,-4,-8,-10,-10,-10,-8,-7,-4,-2,0,3,6}, \
{22,24,26,28,30,32,33,31,23,-18,-81,-96,-99,-98,-95,-93,-89,-86,-82,-78,-74,-70,-66,-62,-57,-53,-49,-44,-40,-36,-32,-27,-23,-19,-14,-10,-6,-1,2,6,10,15,19,23,27,31,35,38,42,45,49,52,55,57,60,61,63,63,62,61,57,53,47,40,33,28,23,21,19,19,19,20,22}, \
{168,173,178,176,171,166,161,156,151,146,141,136,131,126,121,116,111,106,101,-96,-91,-86,-81,-76,-71,-66,-61,-56,-51,-46,-41,-36,-31,-26,-21,-16,-11,-6,-1,3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78,83,88,93,98,103,108,113,118,123,128,133,138,143,148,153,158,163,168}, \
Run Code Online (Sandbox Code Playgroud)

谢谢你的时间.

Evg*_*uev 31

我看到你的阵列压缩的几个选项.

1.分离8位和1位阵列

您可以将数组拆分为两部分:第一部分存储原始数组的8个低位,第二部分存储'1',如果值不适合8位,则存储'0'.每个值需要9位(与nightcracker的方法相同,但更简单一点).要从这两个数组中读取值,请执行以下操作:

int8_t array8[37*73] = {...};
uint16_t array1[(37*73+15)/16] = {...};
size_t offset = 37 * x + y;
int16_t item = static_cast<int16_t>(array8[offset]); // sign extend
int16_t overflow = ((array1[offset/16] >> (offset%16)) & 0x0001) << 7;
item ^= overflow;
Run Code Online (Sandbox Code Playgroud)

2.近似

如果您可以使用一些有效计算的函数(如多项式或指数)来近似数组,则只能在数组中存储值与近似值之间的差值.这可能每个值仅需要8位甚至更少.

3. Delta编码

如果您的数据足够平滑,除了应用以前的任何一种方法之外,您还可以存储一个只包含部分数据值和其他表的较短表,仅包含所有值之间的差异,第一个表中不存在,以及来自第一张桌子.这需要每个值更少的位.

例如,您可以存储其他值的每五个值和差异:

  Original array: 0 0 1 1 2 2 2 2 2 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7
     Short array: 0         2         3         5         6         6
Difference array:   0 1 1 2   0 0 0 1   0 1 1 2   0 0 0 1   0 0 0 0   0 1 1 1
Run Code Online (Sandbox Code Playgroud)

或者,您可以使用先前值的差异,这需要每个值更少的位:

  Original array: 0 0 1 1 2 2 2 2 2 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7
     Short array: 0         2         3         5         6         6
     Delta array:   0 1 0 1   0 0 0 1   0 1 0 1   0 0 0 1   0 0 0 0   0 1 0 0
Run Code Online (Sandbox Code Playgroud)

如果一组delta值恰好适合int16_t,则可以使用按位运算有效地实现具有delta数组的方法.


初始化

对于选项#2,可以使用预处理器.对于其他选项,预处理器是可能的,但可能不是很方便(预处理器不是很好处理长值列表).预处理器和可变参数模板的某种组合可能更好.或者使用一些文本处理脚本可能更容易.


更新

在查看实际数据后,我可以了解更多细节.选项#2(近似)对您的数据不是很方便.选项#1似乎更好.或者您可以使用Mark Ransom或Nightcracker的方法.没关系,哪一个 - 在所有情况下你都可以从16个中保存7位.

选项#3(Delta编码)允许节省更多空间.它不能直接使用,因为在阵列数据的某些单元格中突然发生变化.但是,据我所知,这些大的变化每行最多发生一次.这可以通过一个额外的列来实现,该列具有完整数据值和delta数组中的一个特殊值.

我注意到,(忽略这些突然的变化)邻居值之间的差异永远不会超过+/- 32.这需要6位来编码每个delta值.这意味着每个值6.6位.压缩率为58%.大约2400字节.(不多,但在评论中比2464K好一点).

阵列的中间部分更加平滑.每个值只需要5位就可以单独编码.这可以节省300..400个字节.将这个数组分成几个部分并对每个部分进行不同的编码可能是个好主意.


Mar*_*som 19

正如Nightcracker已经注意到你的值将适合9位.有一种更简单的方法来存储这些值.将绝对值放入字节数组中,并将符号位放入单独的打包位数组中.

int8_t my_array[37][73] = {{**DATA ABSOLUTE VALUES HERE**}};
int8_t my_signs[37][10] = {{**SIGN BITS HERE**}};
int16_t my_value = my_array[i][j];
if (my_signs[i][j/8] & (1 << j%8))
    my_value = -my_value;
Run Code Online (Sandbox Code Playgroud)

这样可以减少44%的原始桌面尺寸,而不需要太多精力.

  • @ a432511,我认为结构不会起作用,因为每个结构都将对齐一个字节边界,从而填充到2个字节. (4认同)

Rob*_*III 16

我从经验中知道,可视化的东西可以帮助找到解决问题的好方法.由于不清楚你的数据实际代表什么(因此我们对问题领域一无所知/很少)我们可能不会提出"最好的"解决方案(如果一个存在于所有方面).所以我冒昧地把数据可视化 ; 俗话说:一张图片值1000字:-)

抱歉,我没有一个解决方案(还)不是已经发布的那些好,但我觉得剧情可能帮助别人(或自己)想出了一个更好的解决方案.

在此输入图像描述


orl*_*rlp 8

你想要的范围是+ -179.这意味着使用360值,您将得到解决.可以用9位表示360个唯一值.这是一个9位整数查找表的示例:

// size is ceil(37 * 73 * 9 / 16)
uint16_t my_array[1520];

int16_t get_lookup_item(int x, int y) {
    // calculate bitoffset
    size_t bitoffset = (37 * x + y) * 9;

    // calculate difference with 16 bit array offset
    size_t diff = bitoffset % 16;

    uint16_t item;

    // our item doesn't overlap a 16 bit boundary
    if (diff < (16 - 9)) {
        item = my_array[bitoffset / 16]; // get item
        item >>= diff;
        item &= (1 << 9) - 1;

    // our item does overlap a 16 bit boundary
    } else {
        item = my_array[bitoffset / 16];
        item >>= diff;
        item &= (1 << (16 - diff)) - 1;
        item += my_array[bitoffset / 16 + 1] & ((1 << (9 - 16 + diff)) - 1);
    }

    // we now have the unsigned item, substract 179 to bring in the correct range
    return item - 179;
}
Run Code Online (Sandbox Code Playgroud)


Mar*_*som 6

这是另一种方法,与我的第一种完全不同,这就是为什么它是一个单独的答案.

如果不适合8位的值的数量小于总数的1/8,则可以将每个额外的字节用于每个,并且与保持另一个1位数组相比,结果仍然较小.

为了简单和速度,我想坚持使用完整的字节值,而不是比特打包.你从来没有说过这个问题是否存在速度限制,但解码整个文件只是为了查找一个值似乎很浪费.如果这对您来说确实不是问题,那么您最好的结果可能来自实现一些现成的开源压缩实用程序的解码部分.

对于这个实现,我保持一个非常简单的编码.首先,我按照Evgeny Kluev的建议做了一个三角洲,从每一行开始; 您的数据非常适合这种方法.然后通过以下规则对每个字节进行编码:

  • 绝对值> = 97的前导字节为97.通过尝试不同的阈值并选择生成最小结果的阈值来获得该值.接下来是值减去97.
  • 仅检查运行长度为-96到96之间的值.3到32之间的运行长度编码为98到127,运行长度介于33和64之间,编码为-97到-128.
  • 最后,按原样输出-96和96之间的值.

这导致2014字节的编码数组加上另外36个字节,用于索引到每行的开始,总共2050个字节.

可以在http://ideone.com/SNdRI上找到完整的实施方案.输出与问题中发布的表格相同.