c++ optimiser tableau d'entiers

Question

J'ai un 2D table de recherche de int16_t.

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

J'ai un mélange de valeurs qui vont de juste au-dessus de la plage de int8_t juste en dessous de la gamme de int8_t et certaines valeurs se répètent. Je suis en train de réduire la taille de cette table de recherche.

Ce que j'ai fait jusqu'à présent est de diviser chaque int16_t valeur en deux int8_t valeurs de visualiser le gaspillage d'octets.

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++;

Je peux facilement supprimer la valeur zéro int8_t qui gaspillent un octet d'espace et je peux aussi supprimer les valeurs en double, mais ma question est comment puis-je faire pour supprimer ces valeurs, tout en gardant la capacité de recherche sur la base de deux indices?

Je l'ai envisagé de traduire cela dans un tableau 1D et en ajoutant un nombre à la suite de chaque dupliqué valeur qui représente le nombre de doublons qui ont été supprimés, mais j'ai du mal avec la façon dont je serais alors en mesure de déterminer ce qui est une valeur de recherche et qu'est ce qu'un double comptage. Aussi, il est en outre compliquée par le décapage le zéro int8_t valeurs qui ont été gaspillés octets.

EDIT: Ce tableau est stocké dans la ROM déjà. La RAM est encore plus limité que la ROM de sorte qu'il est déjà enregistré dans la mémoire ROM.

EDIT: je vais poster une prime pour cette question dès que je peux. J'ai besoin d'une réponse complète de la façon de stocker les informations ET de les récupérer. Il n'a pas besoin d'être un tableau 2D aussi longtemps que je peux obtenir les mêmes valeurs.

EDIT: Ajout de la véritable tableau ci-dessous:

{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}, \

Merci pour votre temps.

Answer 1

Je vois plusieurs options pour votre tableau de compactage.

1. 8 bits et 1 bit de tableaux

Vous pouvez diviser votre tableau en 2 parties: d'abord l'un des magasins de 8 bits de bas de votre tableau d'origine, le second, les magasins '1' si la valeur ne correspond pas en 8 bits ou " 0 " sinon. Cela va prendre 9 bits par valeur (même l'espace comme dans le nightcracker de l'approche, mais un peu plus simple). Pour lire la valeur de ces deux tableaux, procédez de la manière suivante:

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;

2. Rapprochement

Si vous pouvez déterminer votre tableau avec quelques efficacement calculé en fonction (comme le polynôme ou exposant), vous pouvez stocker dans le tableau uniquement la différence entre la valeur et le rapprochement. Cela peut nécessiter seulement 8 bits par valeur ou même moins.

3. Delta encodage

Si vos données est assez lisse, en plus d'appliquer des méthodes précédentes, vous pouvez stocker un court tableau avec seulement une partie des données de valeurs et d'autre de la table, contenant uniquement les différences entre toutes les valeurs, absent dans la première table, et les valeurs de la première table. Cela nécessite moins de bits pour chaque valeur.

Par exemple, vous pouvez stocker chaque cinquième de la valeur et de différences pour les autres valeurs:

  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

Alternativement, vous pouvez utiliser les différences de valeur précédente, ce qui nécessite encore moins de bits par valeur:

  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

Approche avec delta matrice peut être efficacement mis en œuvre à l'aide des opérations bit à bit si un groupe de valeurs delta s'adapte exactement dans int16_t.

---

Initialisation

Pour l'option #2, le préprocesseur peut être utilisé. Pour obtenir d'autres options, de préprocesseur est possible, mais peut-être pas très pratique (préprocesseur n'est pas très bon pour traiter les longues listes de valeurs). Une combinaison de préprocesseur et les variadic templates peut-être mieux. Ou il peut être plus facile à utiliser certains de traitement de texte de script.

---

Mise à jour

Après avoir examiné les données réelles, je peux dire un peu plus de détails. Option #2 (Approximation) n'est pas très pratique pour vos données. Option #1 semble être mieux. Ou vous pouvez utiliser la Marque de Rançon ou de nightcracker de l'approche. Il n'a pas d'importance, dont l'un - dans tous les cas, vous économisez 7 bits sur 16.

Option #3 (Delta encodage) permet d'économiser beaucoup plus d'espace. Il ne peut pas être utilisé directement, car dans certaines cellules de la matrice de données change brusquement. Mais, autant que je sache, ces grands changements se produire au plus une fois pour chaque ligne. Ce qui peut être mis en œuvre par une colonne supplémentaire avec plein de données de valeur et une valeur particulière dans le delta du tableau.

J'ai remarqué, que (sans tenir compte de ces changements brusques) différence entre voisin valeurs ne sont pas plus de +/- 32. Cela nécessite 6 bits pour coder chaque valeur de delta. Cela signifie 6.6 bits par valeur. 58% de compression. Environ 2400 octets. (Pas beaucoup, mais un peu mieux que le 2464K dans vos commentaires).

Partie centrale du tableau est beaucoup plus lisse. Vous aurez besoin de seulement 5 bits pour la valeur à coder séparément. Cela peut aider à économiser 300..400 octets de plus. Probablement que c'est une bonne idée de diviser cet ensemble en plusieurs parties et de coder chaque partie différemment.

Answer 2

Comme nightcracker a noté vos valeurs d'ajustement en 9 bits. Il y a un moyen plus simple pour stocker ces valeurs si. Mettre les valeurs absolues dans un tableau d'octets et de mettre le signe de bits dans un des paniers tableau de bits.

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;

Ce est une réduction de 44% dans l'original de votre taille de la table sans trop d'effort.

Answer 3

Je sais par expérience que visualiser les choses peuvent aider à trouver une bonne solution à un problème. Car il n'est pas très clair ce que vos données est en fait de la représentation (et donc, nous ne savons rien ou très peu de choses sur le domaine du problème) on pourrait pas venir avec la "meilleure" solution (s'il en existe, bien sûr). J'ai donc pris la liberté et visualisé les données; comme dit l'adage, une image vaut 1000 mots :-)

Je suis désolé, je n'ai pas de solution (encore) mieux que ceux déjà posté mais je pensais que l'intrigue pourrait aider quelqu'un (ou à moi) trouver une meilleure solution.

Answer 4

Vous voulez la gamme +-179. Cela signifie que, avec 360 valeurs que vous serez installés. Il est possible d'exprimer 360 valeurs uniques de 9 bits. C'est un exemple de 9 bits en entier de la table de choix:

// 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;
}

Answer 5

Voici une autre approche, totalement différente de ma première qui est pourquoi il est une réponse distincte.

Si le nombre de valeurs qui ne rentre pas dans les 8 bits est inférieur à 1/8 du total, vous pouvez consacrer tout un octet supplémentaire à chaque et encore du vent avec une petite les résultats en fonction de maintien de l'autre 1-tableau de bits.

Dans l'intérêt de la simplicité et de la vitesse, je voulais rester avec plein valeurs d'octets, plutôt que de peu d'emballage. Vous n'avez jamais dit que si il y a des contraintes de vitesse à ce problème, mais le décodage de l'ensemble d'un fichier il suffit de rechercher une valeur semble inutile. Si ce n'est pas vraiment un problème pour vous, votre meilleurs résultats seraient probablement venu de mettre à exécution le décodage de certains facilement disponibles en open-source utilitaire de compression.

Pour cette application, j'ai gardé un très simple d'encodage. J'ai d'abord fait un delta comme suggéré par Evgeny Kluev, recommencer pour chaque ligne; vos données est rare se prêtent à cette approche. Chaque octet est alors codée par les règles suivantes:

• Une valeur absolue >= 97 est donné un octet de tête de 97. Cette valeur a été calculée en essayant différents seuils et en choisissant celui qui a généré le plus petit résultat. Il est suivi par la valeur de moins de 97.
• La longueur de course n'est activée que pour les valeurs entre -96 et 96. Les longueurs entre 3 et 32 sont codés de 98 à 127, et les longueurs entre 33 et 64 sont codés comme des -97 à -128.
• Enfin, les valeurs entre -96 et 96 sont de sortie comme.

Il en résulte un système de tableau de 2014 octets, plus un autre de 36 octets pour l'indexation au début de chaque ligne, pour un total de 2050, en octets.

La pleine mise en œuvre peut être trouvé à http://ideone.com/SNdRI . La sortie est identique à la table affichée dans la question.