Liste chaine - Page 1

Bonjour,

je dois utilise une liste chaine pour un de mes projets. Existe il une lib optimisé pour ti (j'ai peur que celles que j'ai ne soit trop gourmandes).
Merci !

je vais faire un graphe orianté, soit une liste de liste. Il n'y a vraiment rien de disponible ?
remarque, connaissant le C cela ne m'étonnerai pas..

Le but du projet n'est-il justement pas de le faire soit-même ?
Sinon vu la simplicité de la chose, faire une lib pour l'implémentation basique de la liste chaînée serait un peu bourrin, mais ça doit pouvoir se trouver.

drev : Au contraire Le C est un langage très âgé, les millions de geeks qui bossent avec depuis sa naissance ont eu le temps de développer un paquet de bibliothèques.

Mais c'est vraiment très simple à programmer un graphe. Il te faut une structure et 2-3 fonctions. Par contre, si on veut une gestion de la mémoire efficace (pour que la création des noeuds soit rapide), il faut passer par des bibliothèques spécialisées afin de remplacer malloc/free. Sur TI89/92+/V200, il y a genalib qui fait ça très bien je crois.

ouép, en fait h'ai déjà fait pas mal de structures de données en C, ma linked list devrait faire l'affaire (j ai un struct element avec un next element et un void *data) et meme des fonctions de tri avec pointeur de fonctions, et justement, ca pese !

Pour faire un peu plus efficace, il faut mettre le pointeur vers le prochain élément directement dans tes structures, pas utiliser la double indirection.

Thibaut (./5) :
Par contre, si on veut une gestion de la mémoire efficace (pour que la création des noeuds soit rapide), il faut passer par des bibliothèques spécialisées afin de remplacer malloc/free.

bah pas forcément, on peut simplement allouer au début un tableau de n structures, et par la suite utiliser une fonction du type getNewTruc qui renvoie un élément du tableau préalloué, de 0 à n-1 par exemple.

Bah ouais c'est le principe c'est de grouper les allocations

Ça paraît simple... mais en cas de libération de structures, tu fais comment ? Ton espace commence à se fragmenter de partout, il faut repérer les blocs libres, pouvoir les retrouver très rapidement lors d'une allocation future, tout en minimisant la fragmentation... On arrive tout de suite à quelque chose de complexe, voir très complexe si on rajoute une contrainte importante : minimiser l'overhead. Tout ça pour dire qu'une bibliothèque spécialisée est bienvenue

Dans le cas où tous les blocs ont une taille identique, c'est la meilleure chose à faire je crois. Mais la recherche de blocs libres peut devenir lente quand beaucoup sont alloués. On doit de toute façon gérer l'allocation des espaces conteneurs et minimiser la dispersion des blocs alloués de façon à ne pas se retrouver avec 10 espaces qui bouffent de la RAM alors qu'ils sont à moitié vides.

Une bibliothèque est sans doute bienvenue

thibault: beh ta fonction qui renvoie la structure (qui aurait etre etre fait par un malloc) n'a qu'a renvoye celle qui a un indice le moins eleve dans le tableau de structure et libre...
et si tout est plein, beh tu refais la meme chose... gros buffer de structure...

Ouais on peut même utiliser une pile/file pour stocker les indices libres (elle est donc pleine au début), et ça nous fait une allocation en temps constant. Bien sûr tout ça dans le cas où c'est de l'allocation d'un type de structure bien précis.

L'overhead deviendrait gênant après de nombreuses libérations. La mémoire de cette liste chaînée est gérée comment ? avec malloc/free ? par son propre gestionnaire ? au sein des blocs libres ? Pour diminuer l'overhead, il faudrait un algo pour repérer les blocs consécutifs et les noter en une fois. Comment tu fais pour savoir quels blocs sont à allouer en premier (afin de limiter la dispersion) ?
On commence à compliquer les choses... Une bibliothèque ferait sans doute économiser du temps et des bugs au programmeur !

Tu as déjà essayé de mettre en place ce genre de gestionnaire ? Si oui, ça m'intéresse de voir ton code. J'ai essayé de construire une lib générique en début d'année et j'ai laissé tomber, aucune des solutions auxquelles je pensais ne me satisfaisait. On bouffait soit trop de mémoire, soit trop de temps.

Folco : Mais tous les pointeurs deviennent invalides ?

et utiliser le truc con déja prévu, la heap, éventuellement par handles et pas pointeurs pour gérer la défragmentation, non?

Les fonctions de Heap d'AMS ne sont pas connues pour leur rapidité...

./17 Je parle exclusivement du cas où on veut une liste chaînée d'un type de structure bien précis.

Et j'avais fait un truc du style dans le cas je connaissait à l'avance le nombre maximal d'éléments.
Les seules opérations dont j'avais besoin étaient l'ajout en fin de liste et la suppression d'éléments.
C'est pas parfait mais voilà : TwList.h TwList.inl
(c'est pas spécialement pour TI vu que c'est du c++ , et ce n'est pas à utiliser avec n'importe quel type d'objet vu que c'est juste une recopie octet par octet)

En C++, les opérateurs new et free ne sont pas déjà très rapides ?

Non, grossièrement new c'est un malloc avec en plus un appel de constructeur.

Quand on a un besoin précis, et c'est le cas ici, on peut faire des politiques d'allocation beaucoup plus efficaces que celles de malloc/free, qui sont des politiques d'allocation génériques.

./23 ben oui c'est de ça qu'on parle depuis le début non ?

C'est implementation-defined, ça.

./24: ben oui, je sais qu'on parle de ça depuis le début
Thibaut dit en ./22 que les opérateurs new/delete (les fonctions malloc/free) sont rapides, je dis en ./23 qu'on peut mieux faire. C'est tout

C'est pour ça (entre autres) que le C++ est lent ? Vu que tout est objet, les choses aussi fréquentes que "chaine 1"+"chaine2" demandent une allocation.

Ça se passe sur la pile tout ça donc c'est pas vraiment des allocations.
Mais par contre il est facile des choses lentes si on ne fait pas attention. Dans l'exemple que tu donnes: "a = b + c" sera plus lent que "a = b, a += c" car dans le premier cas il y a création d'un objet temporaire qui représente "b + c".
Dire que le C++ est lent ça veut pas dire grand chose tout dépend de ce que fait le programmeur.

En C++ tout n'est pas objet, et c'est bien la le problème

Twindruff (./28) :
Mais par contre il est facile des choses lentes si on ne fait pas attention. Dans l'exemple que tu donnes: "a = b + c" sera plus lent que "a = b, a += c" car dans le premier cas il y a création d'un objet temporaire qui représente "b + c".

C'est pour ça que toutes les classes de données bien fichues sont implicitement partagées (sauf évidemment les petites structures de l'ordre de 8 octets, où ce serait contreproductif).