Discussion :

[denispir]

]Voilà: je conçois actuellement un set pour internaliser des chaînes. Mais mes questions pourraient s'appliquer à toute table de hachage, utilisée en tant que set ou table associative, et quel que soit le type d'élément ou de clé.

1°) Cela vaut-il le coup de stocker les valeurs de hachage pour éviter de les recalculer lorsqu'on doit replacer les noeuds (après chaque agrandissement de la table, donc) ? J'imagine que ça dépend du coût du hachage, donc du type d'élément ou clé, et que pour des strings ça peut valoir le coup. Mais qu'en pensez-vous ?

J'en profite pour explorer la conception de tables ordonnées qui (contrairement aux tables de hachage ordinaires) conservent l'ordre d'insertion des éléments ou paires. Je fais ça d'une façon toute bête: les nouveaux noeuds sont placés dans un tableau dynamique avant d'être liés dans les listes (buckets, qui assurent l'accès direct par clé via le hachage). (*)

2°) Du coup, seconde question: est-ce que je dois placer dans le tableau (d'ordre d'iinsertion) les noeuds eux-mêmes, où des pointeurs vers ces noeuds ? Dans le premier cas, je gagne:
* en espace, un pointeur par noeud,
* en temps, une "colocalisation" des noeuds qui augmente les chances d'usage du cache.
Dans le second cas, je gagne:
* en temps, lors de l'agrandissement de la table, pas de copie des noeuds mais seulement de pointeurs, et pas de libération desdits noeuds.

Le poids des noeuds est:
1- 1 pointeur de liste,
2- un élément ou clé (typiquement taille de mot, vu que c'est souvent un pointeur, un premier caractère de chaîne, ou un entier),
3- éventuellement une donnée associée à une clé, si c'est une table associative (ditto),
4- éventuellement la mémorisation de la valeur de hachage (32 ou 64 bits).

A vous de réfléchir ;-)

(*) Les tables associatives de Ruby sont aussi ordonnées depuis qq années. Mais ils font ça en liant les noeuds en // à une seconde liste, en l'occurrence une liste d'ordre d'insertion. Les noeuds ont donc deux paires de pointeurs (car en plus ils utilisent des listes doubles dans les deux cas; je comprends pas pourquoi, d'ailleurs, si qq'un peut m'expliquer... ).

[denispir]

Alors, je vais le clore s'il n'y a pas de réponses aujourd'hui. Si mon problème n'est pas clair, dites le moi.
Denis

[Médinoc]

1°) Je n'ai jamais fait de tables de hachage à taille dynamique, mais je pense que oui ça vaut le coup.

Les tables ordonnées, pour moi, cela ressemble à des listes normales doublées d'un "index" par hachage. Le genre de truc que tu peux faire séparément, je ne vois pas trop la nécessité de le mettre ensemble.

2°) Le cas le plus polyvalent est de placer des pointeurs vers les nœuds, cela évite les surprises (genre un objet extérieur gardant un pointeur vers un nœud, et le nœud qui est déplacé sous ses pieds lors d'un agrandissement de la table).

Je dirais que tu peux mettre directement les nœuds dans la table quand ils ont clairement une sémantique de valeur (genre, des entiers) et que tu es sûr qu'on ne prendra jamais l'adresse d'un nœud.

PS: Cela présuppose que les "sous-conteneurs" de ta table de hachage sont des listes chaînées. En théorie, ça pourrait être n'importe quoi, y compris d'autres tables de hachage selon une clé différente, dont les sous-sous-conteneurs seraient des arbres binaires de recherche

[denispir]

1°) Je n'ai jamais fait de tables de hachage à taille dynamique, mais je pense que oui ça vaut le coup.

Les tables ordonnées, pour moi, cela ressemble à des listes normales doublées d'un "index" par hachage. Le genre de truc que tu peux faire séparément, je ne vois pas trop la nécessité de le mettre ensemble.

Oui, tu as raison. D'un autre côté, je ne vois pas la nécessité de les mettre séparément .
L'intérêt, pour moi, c'est que très souvent en plus d'un accès efficace par item ou clé (qui nécessite une table associative, quelle que soit l'implantation) l'ordre d'insertion peut avoir un sens ou un intérêt pratique ou sémantique. Par exemple une liste de courses est non ordonnée au sens où l'ordre d'insertion n'indique pas l'ordre d'achat par exemple (c'est un donc set en fait) (*), mais rien ne t'empêche de grouper les articles par type, ou lieu d'achat, ou... Autre exemple en programmation, une table de symboles est un cas de table associative, et je déteste les langages qui me ressortent à l'affichage dans le désordre , par exemple, les méthodes d'un type que j'ai moi soigneusement ordonnées par fonctionnalité, ou autre classification.

(*) C'est vrai pour la plupart des listes, comme les listes d'invitation, c'est pourquoi je trouve le terme "list" en lisp ou python "enduisant d'erreur" (misleading).

2°) Le cas le plus polyvalent est de placer des pointeurs vers les nœuds, cela évite les surprises (genre un objet extérieur gardant un pointeur vers un nœud, et le nœud qui est déplacé sous ses pieds lors d'un agrandissement de la table).

Je dirais que tu peux mettre directement les nœuds dans la table quand ils ont clairement une sémantique de valeur (genre, des entiers) et que tu es sûr qu'on ne prendra jamais l'adresse d'un nœud.

PS: Cela présuppose que les "sous-conteneurs" de ta table de hachage sont des listes chaînées. En théorie, ça pourrait être n'importe quoi, y compris d'autres tables de hachage selon une clé différente, dont les sous-sous-conteneurs seraient des arbres binaires de recherche

Oui. Pour une table associative généraliste, je crois que l'usage de listes chaînées pour implanter les buckets (cases?) est quasiment universel: le bon outil pour le bon usage.

[fred1599]

C'est vrai pour la plupart des listes, comme les listes d'invitation, c'est pourquoi je trouve le terme "list" en lisp ou python "enduisant d'erreur" (misleading).

J'ai pas tout compris, tu peux m'expliquer où tu veux en venir?

Tu veux dire qu'une liste en python est ordonnée?

c'est un donc set en fait

Je ne comprend pas le rapport entre un set et l'ordre, ça mériterait une explication.

[denispir]

J'ai pas tout compris, tu peux m'expliquer où tu veux en venir?
Tu veux dire qu'une liste en python est ordonnée?

Est-ce que tu ne connais pas python du tout, ou est-ce que tu plaisantes?
En imaginant le premier cas, oui, en Python List est le nom de type des tableaux dynamiques. Donc ordonnées pour ainsi dire par nature. Note (au cas où je t'apprendrais quelque chose) qu'en programmation le terme "ordre" est particulièrement ambigu. Dans le cas présent (et par opposition en particulier à trié), quand on discute les types de collection, ordonné signifie:
(1) que la collection préserve l'ordre d'insertion des éléments dans ma colection; en gros ils sont placés l'un derrière l'autre et y restent si on les bouge pas
(2) que cette ordre a un certain sens pour l'application, par exemple les mots d'un texte

En théorie, on devrait employer une collection séquentielle dans ce cas (l'ordre des items a un sens), et d'autres plus appropriés (par ex un set, ou un arbre) pour d'autre cas. Mais en pratique on emploie souvent des séquences pour à peu près n'importe quoi, et ce pour diverses raisons dont le fait que la séquence est le type de collection unique ou principal de nombreux langages historiques et importants (deLisp à python en passant par C).

Je ne comprend pas le rapport entre un set et l'ordre, ça mériterait une explication.

Justement, un set est une collection la plus simple conceptuellement, juste un paquet d'items. Sa principale qualité est de pouvoir chercher rapidement (si) un élément (est là ou pas). Pour cela, il privilégie une organisation interne particulièrement rusée (il y en a plusieurs possibles) qui rend difficile ou lourd d'avoir en même temps la préservation de l'odre des éléments.
Donc en gros tu as soit la séquence (et donc l'ordre, mais aussi l'accès direct par index), soit le set avec accès rapide (pas vraiment direc) aux éléments.
Une table associative (map, dict, hash) c'est un set procure un accès rapide par clé (au lieu de l'élément d'un set simple) et y associent un second item couramment nommé valeur.

Denis