Algorithme de tri pour Excel / SharedStrings

Dans Excel, ils «compressent» les chaînes en un mappage numérique (même si je ne suis pas sûr que le mot compresser soit correct dans ce cas). Voici un exemple ci-dessous:

Bien que cela aide à réduire la taille globale du fichier et l'empreinte mémoire, comment Excel fait-il le tri sur un champ de chaîne? Est-ce que chaque chaîne aurait besoin de passer par le mappage de recherche: et si c'est le cas, cela n'augmenterait-il pas considérablement le coût / le ralentissement du tri sur un champ de chaîne (et s'il y avait 1 M de valeurs, les recherches de clés de 1 M ne seraient pas banal). Deux questions à ce sujet:

1. Les chaînes partagées sont-elles utilisées dans l'application Excel elle-même, ou uniquement lors de l'enregistrement des données?
2. Quel serait alors un exemple d'algorithme pour trier sur le terrain? Tout langage est parfait (c, c #, c ++, python).

Je ne peux pas trouver exactement comment Excel stocke les cellules avec SharedStringTable éléments en mémoire au moment de l'exécution, mais leur stockage en tant qu'index de l'élément dans SharedStringTablenécessite seulement une déréférence supplémentaire pour y accéder, en supposant que les éléments sont stockés sous forme de tableau. Donc, je suppose que c'est ainsi que cela se fait. C'est le moyen le plus simple et le seul moyen de l'accélérer est d'avoir une représentation d'exécution SharedStringTabledéjà triée par éléments. Dans ce cas, le tri par index équivaut au tri par valeur. Cette approche, cependant, rend l'opération d'insertion coûteuse comme lorsqu'une nouvelle chaîne est insérée au milieu du tableau, tous les index plus grands qu'il ne devrait être incrémenté et le nombre de ces cellules dans le document peut être très grand, jusqu'à tous les cellules se référant à SharedStringTable.

Si les cellules contiennent des index identiques à ceux du fichier, voici comment trier les cellules représentées par columnValue vecteur en fonction des chaînes vers lesquelles elles pointent stockées dans le sharedStringsvecteur (en C ++ puisque vous avez dit qu'il n'y a pas de différence) au coût de 2 déréférences supplémentaires par opération de comparaison:

// sort indexes from columnValue based on comparing values in sharedStrings
sort(columnValue.begin(), columnValue.end(), 
     [&sharedStrings](size_t i1, size_t i2){return sharedStrings[i1] < sharedStrings[i2];});

Ce n'était pas dans l'OP, mais l' SharedStringTableopération de recherche inversée est lente et la mise en cache des éléments dans un dictionnaire aide.

Tableau des chaînes partagées Microsoft Excel

La table des chaînes partagées est et la norme Open XML, telle que définie par la norme ISO - ISO / IEC 29500-1: 2016 (E)

Définition officielle des chaînes partagées (citée dans le document ISO)

Table de chaînes partagée

Les valeurs de chaîne peuvent être stockées directement à l'intérieur des éléments de cellule de feuille de calcul; cependant, le stockage de la même valeur dans plusieurs éléments de cellule peut entraîner des pièces de feuille de calcul très volumineuses, ce qui peut entraîner une dégradation des performances. La table de chaînes partagée est une liste indexée de valeurs de chaîne, partagée dans le classeur, qui permet aux implémentations de stocker les valeurs une seule fois.

La norme ISO sur les chaînes partagées peut être téléchargée à partir de

https://standards.iso.org/ittf/PubliclyAvailableStandards/c071691_ISO_IEC_29500-1_2016.zip

Réponses aux questions sur ce sujet

Question 1: les chaînes partagées sont-elles utilisées dans l'application Excel elle-même, ou uniquement lors de l'enregistrement des données?

Réponse: Les chaînes partagées sont utilisées par Excel uniquement au moment de l'enregistrement du document, IE, uniquement dans le but de stocker la feuille de calcul en tant que fichier sur le stockage.

Toutefois, lorsque le fichier est ouvert pour l'affichage, les cellules sont remplies avec des valeurs de chaîne réelles extraites de la table des chaînes partagées.

-

Question 2: Quel serait alors un exemple d'algorithme pour trier sur le terrain? Tout langage est parfait (c, c #, c ++, python).

Réponse: Pour une application comme Excel, je suppose qu'une variante propriétaire spéciale du tri rapide est l'algorithme le plus susceptible d'être utilisé pour trier les valeurs de chaîne.

Excel a une limite de 1 048 576 lignes. Pour cette taille, le tri rapide est définitivement un gagnant. Le tri rapide peut produire un résultat très efficace pour un ensemble de données de cette ampleur.

Voici le lien vers l'implémentation du tri rapide en C ++ pour trier les chaînes:

http://www.cplusplus.com/forum/beginner/101599/