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 !

2

3

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

4

Le but du projet n'est-il justement pas de le faire soit-même ? grin
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.
avatar
Que cache le pays des Dieux ? - Forum Ghibli - Forum Littéraire

La fin d'un monde souillé est venue. L'oiseau blanc plane dans le ciel annonçant le début d'une longue ère de purification. Détachons-nous à jamais de notre vie dans ce monde de souffrance. Ô toi l'oiseau blanc, l'être vêtu de bleu, guide nous vers ce monde de pureté. - Sutra originel dork.

5

drev : Au contraire smile 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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

6

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 !

7

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

8

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.
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

9

10

Bah ouais c'est le principe c'est de grouper les allocations hehe
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

11

Ç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 wink
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

12

13

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 grin
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

14

15

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

16

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.
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

17

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 ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

18

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

19

Les fonctions de Heap d'AMS ne sont pas connues pour leur rapidité...
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

20

./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++ tongue, et ce n'est pas à utiliser avec n'importe quel type d'objet vu que c'est juste une recopie octet par octet)
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

21

En C++, les opérateurs new et free ne sont pas déjà très rapides ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

22

Non, grossièrement new c'est un malloc avec en plus un appel de constructeur.
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

23

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.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

24

./23 ben oui c'est de ça qu'on parle depuis le début non grin ?
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

25

C'est implementation-defined, ça.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

26

./24: ben oui, je sais qu'on parle de ça depuis le début grin
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 grin
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

27

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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

28

Ç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.
avatar
Combien de tas de bois une marmotte pourrait couper si une marmotte pouvait couper du bois ?

29

En C++ tout n'est pas objet, et c'est bien la le problème
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

30

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).
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité