J'aurais besoin de stoquer (en mémoire) une liste dynamique
d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou
l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4
(sans compter que malloc il doit bien utiliser un peu
de mémoire quelque part pour se souvenir qu'il a alloué
ce bout de mémoire là).
J'avais donc pensé à une solution ou l'on alloue des
tableaux, et on chaine les tableaux.
Je dois pas être le premier à penser à ça, vous avez
des pointeurs ?
Marc Boyer
--
Lying for having sex or lying for making war? Trust US presidents :-(
| J'avais donc pensé à une solution ou l'on alloue des | tableaux, et on chaine les tableaux.
Tu veux parler du « pool allocator », §19.4.2, TC++PL3 ?
-- Gaby
Bertrand Mollinier Toublet
Marc Boyer wrote:
J'aurais besoin de stoquer (en mémoire) une liste dynamique d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4 (sans compter que malloc il doit bien utiliser un peu de mémoire quelque part pour se souvenir qu'il a alloué ce bout de mémoire là).
J'avais donc pensé à une solution ou l'on alloue des tableaux, et on chaine les tableaux.
Je dois pas être le premier à penser à ça, vous avez des pointeurs ?
Je viens d'ecrire un "tableau dynamique". Basiquement, c'est un tableau,
encapsule dans une structure, qui croit au fur et a mesure que tu ajoutes des objets. Si ca t'interesse, le code est en ligne sur http://www.bmt.dnsalias.org/employment, rubrique projets, tout en bas de la page.
L'interface est commentee dans le .h. Les grandes regles sont:
1) c'est un ADT: creation/destruction via des fonctions et manipulation via pointeur d'une structure incomplete.
2) on ajoute les elements a la fin ou a l'index que l'on veut.
3) on ne peut pas reellement "detruire" d'elements, mais on peut toujours redimensioner le tableau a une taille plus petite (et effectivement detruire les elements de queue).
4) il y a un iterateur pour se balader dans le tableau dans l'ordre croissant des indices.
5) on peut trier le tableau. -- Bertrand Mollinier Toublet int main(){char*strchr();int j34;char t[]=":@abcdefghij-lmnopqrstuv" "wxyz.n",*i="iqgbgxmbbla.llsvoaz:";while (*i){j+=strchr(t,*i++)-t;j%=sizeof t-1;putchar(t[j]);}return 0;}
Marc Boyer wrote:
J'aurais besoin de stoquer (en mémoire) une liste dynamique
d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou
l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4
(sans compter que malloc il doit bien utiliser un peu
de mémoire quelque part pour se souvenir qu'il a alloué
ce bout de mémoire là).
J'avais donc pensé à une solution ou l'on alloue des
tableaux, et on chaine les tableaux.
Je dois pas être le premier à penser à ça, vous avez
des pointeurs ?
Je viens d'ecrire un "tableau dynamique". Basiquement, c'est un tableau,
encapsule dans une structure, qui croit au fur et a mesure que tu
ajoutes des objets. Si ca t'interesse, le code est en ligne sur
http://www.bmt.dnsalias.org/employment, rubrique projets, tout en bas de
la page.
L'interface est commentee dans le .h. Les grandes regles sont:
1) c'est un ADT: creation/destruction via des fonctions et manipulation
via pointeur d'une structure incomplete.
2) on ajoute les elements a la fin ou a l'index que l'on veut.
3) on ne peut pas reellement "detruire" d'elements, mais on peut
toujours redimensioner le tableau a une taille plus petite (et
effectivement detruire les elements de queue).
4) il y a un iterateur pour se balader dans le tableau dans l'ordre
croissant des indices.
5) on peut trier le tableau.
--
Bertrand Mollinier Toublet
int main(){char*strchr();int j34;char t[]=":@abcdefghij-lmnopqrstuv"
"wxyz.n",*i="iqgbgxmbbla.llsvoaz:zdxylaxejivnidhd@ttopnjeftuh-i";while
(*i){j+=strchr(t,*i++)-t;j%=sizeof t-1;putchar(t[j]);}return 0;}
J'aurais besoin de stoquer (en mémoire) une liste dynamique d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4 (sans compter que malloc il doit bien utiliser un peu de mémoire quelque part pour se souvenir qu'il a alloué ce bout de mémoire là).
J'avais donc pensé à une solution ou l'on alloue des tableaux, et on chaine les tableaux.
Je dois pas être le premier à penser à ça, vous avez des pointeurs ?
Je viens d'ecrire un "tableau dynamique". Basiquement, c'est un tableau,
encapsule dans une structure, qui croit au fur et a mesure que tu ajoutes des objets. Si ca t'interesse, le code est en ligne sur http://www.bmt.dnsalias.org/employment, rubrique projets, tout en bas de la page.
L'interface est commentee dans le .h. Les grandes regles sont:
1) c'est un ADT: creation/destruction via des fonctions et manipulation via pointeur d'une structure incomplete.
2) on ajoute les elements a la fin ou a l'index que l'on veut.
3) on ne peut pas reellement "detruire" d'elements, mais on peut toujours redimensioner le tableau a une taille plus petite (et effectivement detruire les elements de queue).
4) il y a un iterateur pour se balader dans le tableau dans l'ordre croissant des indices.
5) on peut trier le tableau. -- Bertrand Mollinier Toublet int main(){char*strchr();int j34;char t[]=":@abcdefghij-lmnopqrstuv" "wxyz.n",*i="iqgbgxmbbla.llsvoaz:";while (*i){j+=strchr(t,*i++)-t;j%=sizeof t-1;putchar(t[j]);}return 0;}
Gabriel Dos Reis
Bertrand Mollinier Toublet writes:
| Marc Boyer wrote: | > J'aurais besoin de stoquer (en mémoire) une liste dynamique | > d'objets O de taille 8. | > La solution "liste chainée" est couteuse, dans le sens ou | > l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4 | > (sans compter que malloc il doit bien utiliser un peu | > de mémoire quelque part pour se souvenir qu'il a alloué | > ce bout de mémoire là). | > J'avais donc pensé à une solution ou l'on alloue des | > tableaux, et on chaine les tableaux. | > Je dois pas être le premier à penser à ça, vous avez | > des pointeurs ? | > | Je viens d'ecrire un "tableau dynamique". Basiquement, c'est un | tableau, encapsule dans une structure, qui croit au fur et a mesure | que tu ajoutes des objets.
| Marc Boyer wrote:
| > J'aurais besoin de stoquer (en mémoire) une liste dynamique
| > d'objets O de taille 8.
| > La solution "liste chainée" est couteuse, dans le sens ou
| > l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4
| > (sans compter que malloc il doit bien utiliser un peu
| > de mémoire quelque part pour se souvenir qu'il a alloué
| > ce bout de mémoire là).
| > J'avais donc pensé à une solution ou l'on alloue des
| > tableaux, et on chaine les tableaux.
| > Je dois pas être le premier à penser à ça, vous avez
| > des pointeurs ?
| >
| Je viens d'ecrire un "tableau dynamique". Basiquement, c'est un
| tableau, encapsule dans une structure, qui croit au fur et a mesure
| que tu ajoutes des objets.
| Marc Boyer wrote: | > J'aurais besoin de stoquer (en mémoire) une liste dynamique | > d'objets O de taille 8. | > La solution "liste chainée" est couteuse, dans le sens ou | > l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4 | > (sans compter que malloc il doit bien utiliser un peu | > de mémoire quelque part pour se souvenir qu'il a alloué | > ce bout de mémoire là). | > J'avais donc pensé à une solution ou l'on alloue des | > tableaux, et on chaine les tableaux. | > Je dois pas être le premier à penser à ça, vous avez | > des pointeurs ? | > | Je viens d'ecrire un "tableau dynamique". Basiquement, c'est un | tableau, encapsule dans une structure, qui croit au fur et a mesure | que tu ajoutes des objets.
Comment est-il différent de « obstack » ?
-- Gaby
Tobias Oed
Marc Boyer wrote:
J'aurais besoin de stoquer (en mémoire) une liste dynamique d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4
pour le membre O *next; ?
(sans compter que malloc il doit bien utiliser un peu de mémoire quelque part pour se souvenir qu'il a alloué ce bout de mémoire là).
C'est sur. En plus tu n'a aucun controle sur le placement en memoire de tes objets. En fonction du pattern selon lequel tu les accedes tu risque des pertes en performances.
J'avais donc pensé à une solution ou l'on alloue des tableaux, et on chaine les tableaux.
C'est une idee.
Je dois pas être le premier à penser à ça, vous avez des pointeurs ?
Ca serait interssant de savoir quelles operations tu veux faire sur ta collection d'objets. Style ajouter/enlever un objet au debut/fin/milieu, recherche, etc. avec un idee de la preponderance de chaqune.
Pour stoquer des donnes experimentales, j'ai une liste chainee d'experiences, ou chaque experience contient deux tableaux dynamiques pour les points experimentaux. (Deux tableaux: un pour la valeur experimentale et qq autre trucs et un pour les coordonnes. Je ne peux pas tout mettre dans un seul tableau parceque le nombre de coordonnes depends de l'experience.) C'est une parti d'un progromme assez gros qui ne factorise pas exatement dans un module. Si ca t'interesse je peux te l'envoyer en prive. (trop gros pour ce ng). Tobias.
J'aurais besoin de stoquer (en mémoire) une liste dynamique
d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou
l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4
pour le membre O *next; ?
(sans compter que malloc il doit bien utiliser un peu
de mémoire quelque part pour se souvenir qu'il a alloué
ce bout de mémoire là).
C'est sur. En plus tu n'a aucun controle sur le placement en memoire de tes
objets. En fonction du pattern selon lequel tu les accedes tu risque des
pertes en performances.
J'avais donc pensé à une solution ou l'on alloue des
tableaux, et on chaine les tableaux.
C'est une idee.
Je dois pas être le premier à penser à ça, vous avez
des pointeurs ?
Ca serait interssant de savoir quelles operations tu veux faire sur ta
collection d'objets. Style ajouter/enlever un objet au debut/fin/milieu,
recherche, etc. avec un idee de la preponderance de chaqune.
Pour stoquer des donnes experimentales, j'ai une liste chainee
d'experiences, ou chaque experience contient deux tableaux dynamiques pour
les points experimentaux. (Deux tableaux: un pour la valeur experimentale
et qq autre trucs et un pour les coordonnes. Je ne peux pas tout mettre
dans un seul tableau parceque le nombre de coordonnes depends de
l'experience.) C'est une parti d'un progromme assez gros qui ne factorise
pas exatement dans un module. Si ca t'interesse je peux te l'envoyer en
prive. (trop gros pour ce ng).
Tobias.
J'aurais besoin de stoquer (en mémoire) une liste dynamique d'objets O de taille 8.
La solution "liste chainée" est couteuse, dans le sens ou l'overhead mémoire est de "sizeof(*O)" qui vaut vite 4
pour le membre O *next; ?
(sans compter que malloc il doit bien utiliser un peu de mémoire quelque part pour se souvenir qu'il a alloué ce bout de mémoire là).
C'est sur. En plus tu n'a aucun controle sur le placement en memoire de tes objets. En fonction du pattern selon lequel tu les accedes tu risque des pertes en performances.
J'avais donc pensé à une solution ou l'on alloue des tableaux, et on chaine les tableaux.
C'est une idee.
Je dois pas être le premier à penser à ça, vous avez des pointeurs ?
Ca serait interssant de savoir quelles operations tu veux faire sur ta collection d'objets. Style ajouter/enlever un objet au debut/fin/milieu, recherche, etc. avec un idee de la preponderance de chaqune.
Pour stoquer des donnes experimentales, j'ai une liste chainee d'experiences, ou chaque experience contient deux tableaux dynamiques pour les points experimentaux. (Deux tableaux: un pour la valeur experimentale et qq autre trucs et un pour les coordonnes. Je ne peux pas tout mettre dans un seul tableau parceque le nombre de coordonnes depends de l'experience.) C'est une parti d'un progromme assez gros qui ne factorise pas exatement dans un module. Si ca t'interesse je peux te l'envoyer en prive. (trop gros pour ce ng). Tobias.
| > A part ça, c'est quoi 'obstack' ?. | | Bon, OK, du gnu C... passons...
Non. Un truc de la GLIBC.
Bref, c'est pas standard et probablement bourré de gnuismes...
-- -ed- [remove YOURBRA before answering me] The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html <blank line> FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/
Marc Boyer
Gabriel Dos Reis wrote:
Marc Boyer writes:
| J'avais donc pensé à une solution ou l'on alloue des | tableaux, et on chaine les tableaux.
Tu veux parler du « pool allocator », §19.4.2, TC++PL3 ?
Plus ou moins. En fait, en préalable, je dois préciser que je suis pas sur d'avoir tout compris des objectifs du "Pool allocator". Ensuite, ça agirait comme un bête conteneur (ajout, supression, recherche), efficace de préférence. Mais en fait, une implentation simpliste, je veux bien faire, ce que je rechercherais, se sont des élements de discussion en terme de performance (taille des chunks fixe ou variable, trié ou pas, etc).
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
Gabriel Dos Reis wrote:
Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr> writes:
| J'avais donc pensé à une solution ou l'on alloue des
| tableaux, et on chaine les tableaux.
Tu veux parler du « pool allocator », §19.4.2, TC++PL3 ?
Plus ou moins. En fait, en préalable, je dois préciser
que je suis pas sur d'avoir tout compris des objectifs
du "Pool allocator".
Ensuite, ça agirait comme un bête conteneur (ajout,
supression, recherche), efficace de préférence.
Mais en fait, une implentation simpliste, je veux bien
faire, ce que je rechercherais, se sont des élements de
discussion en terme de performance (taille des chunks
fixe ou variable, trié ou pas, etc).
Marc Boyer
--
Lying for having sex or lying for making war? Trust US presidents :-(
| J'avais donc pensé à une solution ou l'on alloue des | tableaux, et on chaine les tableaux.
Tu veux parler du « pool allocator », §19.4.2, TC++PL3 ?
Plus ou moins. En fait, en préalable, je dois préciser que je suis pas sur d'avoir tout compris des objectifs du "Pool allocator". Ensuite, ça agirait comme un bête conteneur (ajout, supression, recherche), efficace de préférence. Mais en fait, une implentation simpliste, je veux bien faire, ce que je rechercherais, se sont des élements de discussion en terme de performance (taille des chunks fixe ou variable, trié ou pas, etc).
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
DINH Viêt Hoà
Emmanuel Delahaye writes:
| > A part ça, c'est quoi 'obstack' ?. | | Bon, OK, du gnu C... passons...
Non. Un truc de la GLIBC.
GLIBC = GNU libc donc, effectivement lié au GNU.
-- DINH V. Hoa,
"Quand tu es pressé, va lentement" -- ed
Emmanuel Delahaye <emdelYOURBRA@noos.fr> writes:
| > A part ça, c'est quoi 'obstack' ?.
|
| Bon, OK, du gnu C... passons...
| > A part ça, c'est quoi 'obstack' ?. | | Bon, OK, du gnu C... passons...
Non. Un truc de la GLIBC.
GLIBC = GNU libc donc, effectivement lié au GNU.
-- DINH V. Hoa,
"Quand tu es pressé, va lentement" -- ed
Marc Boyer
Je reprends la description de mon problème, qui ne donnais pas assez d'élements de réponse.
Sémantiquement parlant, c'est un conteneur associatif, et les fonctions les plus courantes sont: - connaissons nous la valeur associée à la clef "k" - insérer le couple (k,v) - supprimer le couple (k,v)
L'accès est appelé bien plus souvent que les deux autres (un à deux ordres de grandeur).
Pour que l'accès soit rapide, ce serait bien que ce soit trié, et donc que les insertions/suppressions soient pas trop couteuse.
J'avais pensé liste chainee parce que c'est l'existant, mais en décrivant le problème, je réalise que c'est absolument pas adapté.
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
Je reprends la description de mon problème, qui ne donnais
pas assez d'élements de réponse.
Sémantiquement parlant, c'est un conteneur associatif,
et les fonctions les plus courantes sont:
- connaissons nous la valeur associée à la clef "k"
- insérer le couple (k,v)
- supprimer le couple (k,v)
L'accès est appelé bien plus souvent que les deux autres
(un à deux ordres de grandeur).
Pour que l'accès soit rapide, ce serait bien que ce soit
trié, et donc que les insertions/suppressions soient pas
trop couteuse.
J'avais pensé liste chainee parce que c'est l'existant,
mais en décrivant le problème, je réalise que c'est absolument
pas adapté.
Marc Boyer
--
Lying for having sex or lying for making war? Trust US presidents :-(
Je reprends la description de mon problème, qui ne donnais pas assez d'élements de réponse.
Sémantiquement parlant, c'est un conteneur associatif, et les fonctions les plus courantes sont: - connaissons nous la valeur associée à la clef "k" - insérer le couple (k,v) - supprimer le couple (k,v)
L'accès est appelé bien plus souvent que les deux autres (un à deux ordres de grandeur).
Pour que l'accès soit rapide, ce serait bien que ce soit trié, et donc que les insertions/suppressions soient pas trop couteuse.
J'avais pensé liste chainee parce que c'est l'existant, mais en décrivant le problème, je réalise que c'est absolument pas adapté.
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
Emmanuel Delahaye
In 'fr.comp.lang.c', Marc Boyer wrote:
Je reprends la description de mon problème, qui ne donnais pas assez d'élements de réponse.
Sémantiquement parlant, c'est un conteneur associatif, et les fonctions les plus courantes sont: - connaissons nous la valeur associée à la clef "k" - insérer le couple (k,v) - supprimer le couple (k,v)
L'accès est appelé bien plus souvent que les deux autres (un à deux ordres de grandeur).
Pour que l'accès soit rapide, ce serait bien que ce soit trié, et donc que les insertions/suppressions soient pas trop couteuse.
J'avais pensé liste chainee parce que c'est l'existant, mais en décrivant le problème, je réalise que c'est absolument pas adapté.
Je confirme : tableau dynamique + realloc()
et j'ajoute memmove() + memcpy() pour les insertions.
Accès rapide par bsearch().
-- -ed- [remove YOURBRA before answering me] The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html <blank line> FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/
In 'fr.comp.lang.c', Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr> wrote:
Je reprends la description de mon problème, qui ne donnais
pas assez d'élements de réponse.
Sémantiquement parlant, c'est un conteneur associatif,
et les fonctions les plus courantes sont:
- connaissons nous la valeur associée à la clef "k"
- insérer le couple (k,v)
- supprimer le couple (k,v)
L'accès est appelé bien plus souvent que les deux autres
(un à deux ordres de grandeur).
Pour que l'accès soit rapide, ce serait bien que ce soit
trié, et donc que les insertions/suppressions soient pas
trop couteuse.
J'avais pensé liste chainee parce que c'est l'existant,
mais en décrivant le problème, je réalise que c'est absolument
pas adapté.
Je confirme : tableau dynamique + realloc()
et j'ajoute memmove() + memcpy() pour les insertions.
Accès rapide par bsearch().
--
-ed- emdelYOURBRA@noos.fr [remove YOURBRA before answering me]
The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html
<blank line>
FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/
Je reprends la description de mon problème, qui ne donnais pas assez d'élements de réponse.
Sémantiquement parlant, c'est un conteneur associatif, et les fonctions les plus courantes sont: - connaissons nous la valeur associée à la clef "k" - insérer le couple (k,v) - supprimer le couple (k,v)
L'accès est appelé bien plus souvent que les deux autres (un à deux ordres de grandeur).
Pour que l'accès soit rapide, ce serait bien que ce soit trié, et donc que les insertions/suppressions soient pas trop couteuse.
J'avais pensé liste chainee parce que c'est l'existant, mais en décrivant le problème, je réalise que c'est absolument pas adapté.
Je confirme : tableau dynamique + realloc()
et j'ajoute memmove() + memcpy() pour les insertions.
Accès rapide par bsearch().
-- -ed- [remove YOURBRA before answering me] The C-language FAQ: http://www.eskimo.com/~scs/C-faq/top.html <blank line> FAQ de f.c.l.c : http://www.isty-info.uvsq.fr/~rumeau/fclc/
