Comment puis-je encoder / décoder efficacement une description de poste compressée?

J’écris une base de table pour une variante d’échecs japonais. Pour indexer la base de la table, je code chaque position d’échecs en tant qu’entier. Dans l’une des étapes d’encodage, j’encode où les pièces sont sur le tableau. Puisque la méthode actuelle est un peu compliquée, laissez-moi vous expliquer le problème de manière simplifiée.

L’encodage

Dans le plateau final, j’ai (disons) six pièces d’échecs distinctes que je veux répartir sur un tableau de 9 cases. Je peux naïvement représenter leurs positions par un six-nuplet ( a , b , c , d , e , f ) où chacune des variables a à f est un nombre compris entre 0 et 8 inclus, indiquant l’emplacement de la pièce correspondante .

Cependant, cette représentation n’est pas optimale: deux pièces d’échecs ne peuvent occuper le même carré, mais l’encodage susmentionné le permet volontiers. Nous pouvons coder la même position par un six-nuplet [ a, b ‘, c’, d ‘, e’, f ‘ ] où a est identique a , b’ est un nombre compris entre 0 et 7, indiquant le numéro du carré sur lequel se trouve la deuxième pièce. Cela fonctionne en atsortingbuant un nombre de 0 à 7 à chaque carré le premier morceau n’est pas. Par exemple, si le premier morceau est au carré 3, les nombres carrés du deuxième morceau sont:

1st piece: 0 1 2 3 4 5 6 7 8 2nd piece: 0 1 2 - 3 4 5 6 7 

les autres morceaux sont codés de la même façon, c ‘ sous la forme d’un nombre compris entre 0 et 6, d’ sous la forme d’un nombre compris entre 0 et 5, etc. Par exemple, le codage naïf (5, 2, 3, 0, 7, 4) donne le codage (5, 2, 2, 0, 3, 1):

 1st: 0 1 2 3 4 5 6 7 8 --> 5 2nd: 0 1 2 3 4 - 5 6 7 --> 2 3rd: 0 1 - 2 3 - 4 5 6 --> 2 4th: 0 1 - - 2 - 3 4 5 --> 0 5th: - 0 - - 1 - 2 3 4 --> 3 6th: - 0 - - 1 - 2 - 3 --> 1 

Dans mon encodage actuel, le nombre de morceaux que je veux encoder n’est pas fixe. Le nombre de carrés sur le plateau est cependant.

La question

Comment convertir efficacement la représentation naïve en représentation compacte et vice versa? J’utilise la norme C99 pour le programme. Dans le contexte de cette question, les réponses qui utilisent des constructions non standard, un assemblage en ligne ou des éléments insortingnsèques ne m’intéressent pas.

Question de clarification

Comme il semble y avoir une certaine confusion à propos de la question:

  • La question est de trouver un moyen pratiquement efficace de mettre en œuvre la conversion entre les représentations de position naïves et compactes.
  • Les deux représentations sont des n- couples de nombres entiers dans certaines plages. La question n’est pas de savoir comment encoder ces représentations dans autre chose.
  • Dans l’un de mes cas, le nombre de carrés est de 25 et le nombre de pièces est inférieur à 12. Je suis toutefois intéressé par une implémentation qui fonctionne pour un espace de paramètre raisonnable (par exemple, jusqu’à 64 carrés et jusqu’à 32 pièces). .
  • Je ne m’intéresse pas aux représentations ou encodages alternatifs, en particulier aux représentations ou encodages non optimaux.
  • Je ne suis pas non plus intéressé par les remarques selon lesquelles la représentation compacte ne vaut pas la peine.
  • Je ne m’intéresse pas non plus aux réponses qui utilisent des composants insortingnsèques, un assemblage en ligne ou toute autre construction non standard (à l’exception peut-être de celles décrites par POSIX).

J’ai trouvé une solution plus élégante pour un maximum de 16 positions utilisant des entiers 64 bits avec une seule boucle pour le codage et le décodage:

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

Le code utilise des entiers non signés de 64 bits pour contenir des tableaux de 16 valeurs dans la plage 0..15 . Un tel tableau peut être mis à jour en parallèle en une seule étape, l'extraction d'une valeur est simple et la suppression d'une valeur est un peu plus lourde mais ne nécessite que quelques étapes.

Vous pouvez étendre cette méthode à 25 positions en utilisant des entiers non portables de 128 bits (le type __int128 est pris en charge à la fois par gcc et par clang), en codant chaque position sur 5 bits, en tirant parti du fait que 5 * 25 < 128 , les constantes sont plus lourdes à écrire.

La solution naïve au problème: créez un tableau où les valeurs sont initialement égales aux index. Lorsque vous utilisez un carré, prenez sa valeur dans le tableau et décrémentez toutes les valeurs à droite. Le temps d’exécution de cette solution est O(n*p)n est le nombre de carrés sur le tableau et p le nombre de pièces sur le tableau.

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

Vous pouvez essayer d'améliorer les performances de ce code avec binning. Considérez les emplacements sur le tableau comme 5 cases de 5 emplacements chacun. Chaque bac a un décalage et chaque emplacement dans un bac a une valeur. Lorsqu'une valeur est extraite du bin y à l'emplacement x , les décalages de tous les bin inférieurs à y sont décrémentés. Et toutes les valeurs à la droite de x dans bin y sont décrémentées.

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

La durée d'exécution de cette solution est O(sqrt(n) * p) . Cependant, sur un tableau de 25 cases, vous ne verrez pas beaucoup d’amélioration. Pour voir pourquoi considérons les opérations effectives effectuées par la solution naïve par rapport à la solution regroupée. Dans le pire des cas, la solution naïve met à jour 24 emplacements. Dans le pire des cas, la solution regroupée met à jour 4 entrées dans le tableau offset et 4 emplacements dans le tableau de codes . Cela ressemble donc à une accélération de 3: 1. Cependant, le code regroupé contient une instruction division / modulo désagréable et est globalement plus compliqué. Donc, vous pourriez avoir une accélération de 2: 1 si vous êtes chanceux.

Si la taille de la carte était énorme, par exemple 256x256, alors le binning serait génial. Le pire des cas pour la solution naïve serait 65535 entrées, alors que binning mettrait à jour un maximum de 255 + 255 = 510 entrées de tableau. Donc, cela compenserait certainement la division méchante et la complexité accrue du code.

Et c'est là que réside la futilité d'essayer d'optimiser de petits ensembles de problèmes. Vous ne gagnez pas beaucoup en changeant O(n) en O(sqrt(n)) ou O(log(n)) lorsque vous avez n=25 sqrt(n)=5 log(n)=5 . Vous obtenez une accélération théorique, mais c’est presque toujours une fausse économie lorsque vous considérez la myriade de facteurs constants que big-O ignore si allègrement.


Pour être complet, voici le code de pilote qui peut être utilisé avec l'un des extraits ci-dessus.

 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" ); } 

Sortie: 5 2 2 0 3 1

Votre technique de codage a la propriété que la valeur de chaque élément du tuple de sortie dépend des valeurs de l’élément correspondant et de tous les éléments précédents du tuple d’entrée. Je ne vois pas le moyen d’accumuler des résultats partiels lors du calcul d’un élément codé qui pourrait être réutilisé dans le calcul d’un élément différent, et sans cela, aucun calcul du codage ne peut évoluer plus efficacement (temps) que o (n 2 ) dans le nombre d’éléments à encoder. Par conséquent, pour la taille du problème que vous décrivez, je ne pense pas que vous puissiez faire mieux que cela:

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

Le décodage correspondant pourrait être fait comme ceci:

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

Certaines approches sont mieux adaptées, certaines d'entre elles étant discutées dans des commentaires et d'autres réponses, mais la meilleure hypothèse est que la taille de votre problème n'est pas assez importante pour que sa mise à l'échelle améliorée permette de dépasser ses frais généraux supplémentaires.

De toute évidence, ces transformations ne changent pas elles-mêmes la taille de la représentation. La représentation codée est cependant plus facile à valider car chaque position dans un tuple peut être validée indépendamment des autres. Pour cette raison, l’espace entier des tuples valides peut également être énuméré beaucoup plus efficacement sous la forme codée que sous la forme décodée.

Je continue à soutenir que la forme décodée peut être stockée presque aussi efficacement que la forme codée, en particulier si vous souhaitez pouvoir traiter des descriptions de poste individuelles. Si votre objective pour la forme codée est de prendre en charge l'énumération en bloc, vous pouvez alors envisager d'énumérer les n-uplets sous la forme "codée", mais de les stocker puis de les utiliser sous forme décodée . La petite quantité d’espace supplémentaire nécessaire pourrait très bien en valoir la peine, car elle n’aurait pas besoin d’effectuer le décodage après la lecture, en particulier si vous envisagez de lire beaucoup de celles-ci.


Mettre à jour:

En réponse à votre commentaire, l'éléphant dans la pièce se demande comment vous convertissez la forme codée en un seul index, tel que vous le décrivez, afin qu'il y ait le moins possible d'indices inutilisés. Je pense que c’est l’écart qui a suscité tant de discussions que vous avez considéré hors sujet, et je présume que vous avez des hypothèses à ce sujet qui alimentent votre affirmation d’économies d’espace 24x.

La forme encodée est plus facilement convertie en un index compact. Par exemple, vous pouvez traiter la position comme un nombre little-endian avec la taille du tableau comme base:

 #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]; } } 

Certes, il y a encore des lacunes, mais j'estime qu'elles constituent une proportion relativement petite de la plage globale des valeurs d'indice utilisées (et le faire en ce sens est la raison pour laquelle on a choisi une interprétation peu profonde). Je laisse la transformation inverse comme un exercice :).

Pour convertir une position naïve en position compacte, vous pouvez effectuer une itération sur le n-tuple et effectuer les étapes suivantes pour chaque position p :

  1. vérifier éventuellement que la position p est disponible
  2. définir la position p comme occupé
  3. soustrayez de p le nombre de postes inférieurs occupés
  4. stocker le résultat dans le n-tuple de destination

Vous pouvez faire cela en maintenant un tableau de n bits pour l’état occupé:

  • les étapes 1, 2 et 4 sont calculées en temps constant
  • l’étape 3 peut être calculée efficacement si le tableau est petit, c’est-à-dire: 64 bits.

Voici une implémentation:

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

L'optimisation principale réside dans la mise en œuvre de bitcount() , que vous pouvez adapter à vos besoins en le spécialisant en fonction du nombre réel de positions. J'ai posté ci-dessus des solutions efficaces pour les petits nombres jusqu'à 9 et les grands nombres jusqu'à 64, mais vous pouvez concevoir une solution plus efficace pour 12 ou 32 postes.

En termes de complexité temporelle, dans le cas général, nous avons toujours O (n 2 ) , mais pour de petites valeurs de n , il s’exécute en fait dans O (n.Log (n)) ou mieux, depuis l’implémentation de bitcount() en parallèle peut être réduit à log (n) pas ou moins pour n à 64.

Vous pouvez consulter http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive pour vous inspirer et vous émerveiller.

Malheureusement, je suis toujours à la recherche de moyens d'utiliser cette astuce ou une astuce similaire pour le décodage ...

Dans cette réponse, je souhaite montrer certaines de mes propres idées pour la mise en œuvre des conversions ainsi que des résultats d’parsing comparative.

Vous pouvez trouver le code sur Github . Voici les résultats sur ma machine principale:

 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 

Implémentations

  • baseline est une implémentation qui ne fait rien sauf lire les entrées. Son but est de mesurer l’appel de fonction et la surcharge d’access à la mémoire.
  • count est une implémentation «naïve» qui stocke une carte d’occupation indiquant les carrés contenant déjà des morceaux.
  • bitcount est la même chose mais avec la carte d’occupation stockée sous forme de bitmap. __builtin_popcount est utilisé pour l’encodage, ce qui accélère considérablement les choses. Si vous utilisez plutôt un popcount écrit à la main, bitcount rest l’implémentation portable la plus rapide de l’encodage.
  • décrément est la deuxième implémentation naïve. Il stocke l’encodage pour chaque carré du tableau, après avoir ajouté une pièce, tous les nombres carrés à droite sont décrémentés.
  • bin4 , bin5 et bin8 utilisent le binning avec des bacs de tailles 4, 5 et 8, comme suggéré par user3386109 .
  • shuffle calcule un encodage légèrement différent basé sur le shuffle de Fisher-Yates . Cela fonctionne en reconstruisant les valeurs aléatoires qui seraient entrées dans un mélange générant la permutation que nous voulons coder. Le code est sans twig et rapide, en particulier lors du décodage.
  • Le vecteur utilise un vecteur de cinq nombres de bits comme suggéré par chqrlie .
  • tree utilise un arbre de différence qui est une structure de données que j’ai composée. C’est un arbre binary complet de profondeur ⌈log 2 n où les feuilles représentent chaque carré et les nœuds internes sur le chemin d’access à chaque sum sont ajoutés au code de ce carré (seuls les nœuds où vous allez à droite sont ajoutés). Les nombres carrés ne sont pas stockés, conduisant à n – 1 mots de mémoire supplémentaire.

    Avec cette structure de données, nous pouvons calculer le code pour chaque carré dans ⌈log 2 n – 1 pas et marquer un carré comme étant occupé dans le même nombre d’étapes. La boucle interne est très simple et comprend une twig et deux actions, selon que vous descendez à gauche ou à droite. Sur ARM, cette twig comstack quelques instructions conditionnelles, ce qui permet une implémentation très rapide. Sur x86, ni gcc ni clang ne sont assez intelligents pour se débarrasser des twigs.

  • treeasm est une variante de tree qui utilise l’ assemblage en ligne pour implémenter la boucle interne de tree sans twigs en manipulant avec précaution l’indicateur de portage.
  • bmi2 utilise les instructions pdep et pext du jeu d’instructions BMI2 pour implémenter l’algorithme de manière très rapide.

Pour mon projet actuel, je vais probablement utiliser l’implémentation shuffle car c’est la plus rapide qui ne dépend d’aucune extension non transférable (telle que les propriétés insortingnsèques d’Intel) ou de détails d’implémentation (tels que la disponibilité d’entiers 128 bits).

Pour aller de (5, 2, 3, 0, 7, 4) à (5, 2, 2, 0, 3, 1), il vous suffit de:

  • commencer par (5, 2, 3, 0, 7, 4), appuyer cinq fois dans le résultat (5)
  • prenez 2 et comptez le nombre de valeurs précédentes inférieur à 2, 0 puis appuyez sur 2-0: (5, 2)
  • prenez 3, comptez le nombre de valeurs précédentes inférieur à 3, 1 puis appuyez sur 3-1: (5, 2, 2)
  • prendre 0, compter le nombre de valeurs précédentes inférieur à 0, 0 puis appuyer sur 0-0 (5,2, 2, 0)
  • prenez 7, comptez …, 4 puis appuyez sur 7-4: (5,2,2,0,3)
  • prenez 4, comptez …, 3 puis appuyez sur 4-3: (5,2,2,0,3,1)