Classes pour les mots

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

Citation:

---

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...

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.

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

Qu'entends-tu par un type de conteneur ?

Citation:

---

Envoyé par 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.

---

Citation:

---

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.

Citation:

---

Envoyé par info_folie_linux

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.

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 ?

Citation:

---

codage sur char est 32 (voir 64) fois plus lent et plus couteux en mémoire que le codage sur bit.

---

N'importe quoi.
Le codage sur un bit c'est plus lent que le codage sur un char, qui est lui même plus lent que le codage sur un int.

Après là on parle des opérations qui fonctionnent lettre par lettre... Bien sûr pour la comparaison de ton un mot ou sa copie, ça ne dépend que de la taille totale du truc.
Mais dès qu'il faut parcourir lettre par lettre, si tu passes par des bits ça va être super lent. Seule la concaténation en bénéficierait.

Salut,

A vrai dire, les comportements que tu souhaite me font à ce point penser à ceux que l'on observe pour la classe (w)string que je me demande réellement si tu n'a pas tout simplement intérêt... à l'utiliser :P

Ce que tu peux faire, c'est encapsuller cette classe dans une autre qui te permette de gérer la taille maximale de chaque chaine, si ça peut avoir un sens dans l'ensemble du programme, mais, je suis de l'avis général qu'il faut vraiment attendre d'être sur d'avoir l'algorithme "le meilleur possible" avant de commencer à s'inquiéter du problème de perfs que peut représenter le fait de travailler sur un char plutôt que sur un tableau de bits ;)