Discussion :

[info_folie_linux]

Bonjour,

Je souhaiterais construire une classe C++ pour les mots sur un alphabet à deux lettres (par exemple 0,1) et une autre pour les mots sur quatre lettres (par exemple 00, 01, 10 et 11). Ces classes doivent implémenter toutes les opérations standards sur les mots : concaténation, recherche de caractère, recherche de sous-mot,... avec un grand soucis d'efficacité.

Pour le stockage des données, une première implémentation possible serait d'utiliser le type char pour stocker une lettre mais on voit bien que question optimisation on a vu mieux.

Une seconde implémentation consiste à utiliser un vector<unsigned int> et considérer que chaque élément contient sizeof(unsigned int) lettres (ou bien la même chose divisé par 2 pour les mots sur quatre lettres). Il faudra alors écraser les méthodes d'accès aux éléments et les itérateurs en utilisant les opérations de décalage de bits. Ca me semble un peu fumeux car on démonte précisément tout ce qui est utile dans cette classe. On peut aussi créer de nouveaux itérateurs iterator_on_bit, reverse_iterator_on_bit... et de nouvelles méthodes d'accès aux éléments at_bit()...

Cependant, la solution la plus naturelle pour les mots sur deux lettres devrait utiliser vector<bool> ou bit_vector. J'aimerais savoir si ces deux classes sont standardisées quand au stockage des données. En effet, pour effectuer une recherche de sous-mot, on compare des 'segments' de mots de 32 ou 64 bits... il faut donc pouvoir y accéder directement et non pas simplement aux lettres.

Une dernière solution consisterait à reconstruire depuis le début une classe de tableau dynamique (ce qui, je pense, n'est jamais une bonne idée en C++).


Que feriez-vous/est-il possible de faire ? Voyez-vous d'autres solutions ?


Merci,
IFFL

[loufoque]

Pour le stockage des données, une première implémentation possible serait d'utiliser le type char pour stocker une lettre mais on voit bien que question optimisation on a vu mieux.

Comme quoi ? Utiliser un mot matériel (i.e. un int) par lettre ?
Tu cherches à optimiser l'efficacité ou l'utilisation mémoire ?

Ce que je ferais, c'est que je ferais simplement un conteneur de lettre, où lettre est un type qui identifie une lettre de l'alphabet.
Que lettre puisse potentiellement tenir sur quelques bits, c'est pas vraiment ça le plus important...

[info_folie_linux]

La gestion du temps et de l'espace mémoire n'est pas négligeable.
codage sur char est 32 (voir 64) fois plus lent et plus couteux en mémoire que le codage sur bit.

Par exemple pour une comparaison d'égalité entre deux mots de longueurs 32 :
codage par bit --> une seule opération de processeur !
codage par char --> 32 comparaisons (sans compter l'itération)

Je suis d'accord, on ne gagne qu'un facteur. Mais je ne pense pas que ce facteur soit négligeable. Il y a quand même une différence entre 32 secondes et 1 seconde du point de vue de l'utilisateur.

[info_folie_linux]

Je veux à la fois optimiser la mémoire et le temps.

Qu'entends-tu par un type de conteneur ?

[JolyLoic]

Je veux à la fois optimiser la mémoire et le temps.

Et moi je veux le beurre, l'argent du beurre, et le sourire de la crémière...

Ces deux points sont souvent en conflit (bien qu'une faible utilisation mémoire soit favorable à la gestion du cache). Par exemple un vector<bool> va optimiser la mémoire, mais accéder à un bit va être plus lent, car on doit faire des opérations bit à bit. Tu pourrais peut-être encore plus optimiser la mémoire avec un algo de compression, mais l'accès sera encore plus long.

J'ai l'impression que tu ne sais pas encore vraiment quelles vont être les problèmes de perf que tu vas rencontrer. Dans ce cas là, je te conseille de commencer par le plus simple à utiliser (vector<bool>, peut-être), mais en l'encapsulant bien de manière à pouvoir le modifier par la suite et à faire des mesures quand ton programme tournera.

[info_folie_linux]

Merci beaucoup pour vos réponses.

En fait j'ai un programme qui tourne, ce dernier opère avec des données de type char (j'autorise 256 caractères). Mais très souvent, on est confronté à des alaphabets à deux lettres et trois lettres; ne-serait-ce que parce que les problèmes combinatoires sont plus simples. J'espérai gagner du temps en prévoyant une structure de donnée dans ce cadre là. Les opérations que j'effectue le plus souvent sont :
concaténer une chaîne à une autre chaîne
recherche de sous-mots
parcourir la chaîne dans l'ordre
accéder à un caractère

Vous me déconseilleriez donc de prévoir une structure de donnée spécialisée pour les mots sur deux lettres ?

[Davidbrcz]

La gestion du temps et de l'espace mémoire n'est pas négligeable.
codage sur char est 32 (voir 64) fois plus lent et plus couteux en mémoire que le codage sur bit.

Par exemple pour une comparaison d'égalité entre deux mots de longueurs 32 :
codage par bit --> une seule opération de processeur !
codage par char --> 32 comparaisons (sans compter l'itération)

Je suis d'accord, on ne gagne qu'un facteur. Mais je ne pense pas que ce facteur soit négligeable. Il y a quand même une différence entre 32 secondes et 1 seconde du point de vue de l'utilisateur.

premature optimization is the root of all evil

Tu rentre parfaitement dans ce cadre. Conseiller de coder sur un tableau de bit, c'est se compliquer la vie pour rien.

Un programmeur devrait se concentrer là où se joue les performances, c'est à dire dans les algorithmes. Après, et seulement après avoir épuisé toutes les méthodes algorithmique d'optimisation, il peut s'attaquer à ce genre de détails si les performances sont si critiques que ca, ce qui ne semble pas être le cas ici. Et même s'il le fait, on il ne battra jamais un compilateur avec toutes les options d'optimisation.