Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
Désolé si je me suis mal expliqué!
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
2) ça se redimensionne pas bien si je me souviens bien
J'ai laissé tomber, trop peu d'avantages comme tu l'as dit...
Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
Désolé si je me suis mal expliqué!
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
2) ça se redimensionne pas bien si je me souviens bien
J'ai laissé tomber, trop peu d'avantages comme tu l'as dit...
Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
Désolé si je me suis mal expliqué!
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
2) ça se redimensionne pas bien si je me souviens bien
J'ai laissé tomber, trop peu d'avantages comme tu l'as dit...
Marc Boyer wrote:Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
[...]
Est-ce plus clair ainsi?
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
2) ça se redimensionne pas bien si je me souviens bien
J'ai laissé tomber, trop peu d'avantages comme tu l'as dit...
Marc Boyer wrote:
Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
[...]
Est-ce plus clair ainsi?
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
2) ça se redimensionne pas bien si je me souviens bien
J'ai laissé tomber, trop peu d'avantages comme tu l'as dit...
Marc Boyer wrote:Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
[...]
Est-ce plus clair ainsi?
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
2) ça se redimensionne pas bien si je me souviens bien
J'ai laissé tomber, trop peu d'avantages comme tu l'as dit...
Marc Boyer wrote:Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
Désolé si je me suis mal expliqué!
Je reprends point par point.
Tout d'abord, c'est un simulateur à évenements discrets.
Comme dans tout simulateur, on traite des évenements qui vont en
engendrer d'autres (c'est un écheancier).
On a donc besoin de traiter une liste d'évenements toujours triés par
ordre croissant.
J'avais au départ fait une liste chainée simple, ainsi, l'insertion se
faisait en O(n) et l'extraction en 1 (On prend toujours la tête de la
liste qui est l'évenement de plus petite date).
Je me suis ensuite souvenu, qu'une structure de donnée en tas (arbre
binaire dont tous les noeuds ont leurs deux fils supérieurs ou égals)
permettait d'insérer des éléments dans une liste de manière triés en
O(log(n)).
Le problème c'est que mon simulateur peut génèrer plusieurs évenements
à une date T identique. Mon insertion est alors en O(log(n)) ou n est
le nombre de dates. Je me suis alors dit qu'il serait plus performant
d'avoir un algo en O(log(n)) ou n est le nombre de dates distinctes.
Pour ce faire, il faut connaître l'emplacement dans le tas des dates
déjà insérées, d'où l'idée de faire un tableau d'inverse, c'est-à-dire
un tableau où les "numéros des cases" sont des dates et ou le contenu
des cases est un rang dans le tableau du tas. Ainsi si j'insere un
evenement e, je pourrais vérifier si il a déjà été inséré dans le tas
en faisant inverse[e->date].
Le tableau d'inverse doit donc être de taille date_max (la plus grande
date que contient le tas).
Exemple:
-------
soit le tas:
-------------------------
T= | 3 | 5 | 4 | 6 | 7 | 9 |
-------------------------
L'arbre correspondant:
3
5 4
6 7 9
Et le tableau d'inverses:
---------------------------------------------
inverse= | -1 | -1 | -1 | 0 | 2 | 1 | 3 | 4 | -1 | 5 |
---------------------------------------------
où -1 correspond à une date absente du tas.
Donc si je veux insérer un évenement e de date 5, je peux connaître
son rang dans le tas (tableau T) en faisant inverse[e->date] et
j'obtiens 1. Si j'obtient -1, je l'insère normalement en mettant à jour
le tableau d'inverses.
Jusque là, tout est simple, pour une date énorme, le tableau d'inverses
est gigantesque! Pour le minimiser, on peut allouer que
date_max-date_min cases et y accéder en faisant :
inverse[e->date-date_min]
Le problème est alors que lors d'une extraction de la racine (je prends
toujours la date la plus petite), je dois realloc le tableau d'inverse
pour supprimer cette racine qui est partie. C'est-à-dire que je dois
enlever la première case mais le realloc ne permet pas cela. Il permet
seulement de tronquer sur la fin du tableau (et surtout de libérer
l'espace mémoire ne servant plus).
Est-ce plus clair ainsi?
Marc Boyer wrote:
Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
Désolé si je me suis mal expliqué!
Je reprends point par point.
Tout d'abord, c'est un simulateur à évenements discrets.
Comme dans tout simulateur, on traite des évenements qui vont en
engendrer d'autres (c'est un écheancier).
On a donc besoin de traiter une liste d'évenements toujours triés par
ordre croissant.
J'avais au départ fait une liste chainée simple, ainsi, l'insertion se
faisait en O(n) et l'extraction en 1 (On prend toujours la tête de la
liste qui est l'évenement de plus petite date).
Je me suis ensuite souvenu, qu'une structure de donnée en tas (arbre
binaire dont tous les noeuds ont leurs deux fils supérieurs ou égals)
permettait d'insérer des éléments dans une liste de manière triés en
O(log(n)).
Le problème c'est que mon simulateur peut génèrer plusieurs évenements
à une date T identique. Mon insertion est alors en O(log(n)) ou n est
le nombre de dates. Je me suis alors dit qu'il serait plus performant
d'avoir un algo en O(log(n)) ou n est le nombre de dates distinctes.
Pour ce faire, il faut connaître l'emplacement dans le tas des dates
déjà insérées, d'où l'idée de faire un tableau d'inverse, c'est-à-dire
un tableau où les "numéros des cases" sont des dates et ou le contenu
des cases est un rang dans le tableau du tas. Ainsi si j'insere un
evenement e, je pourrais vérifier si il a déjà été inséré dans le tas
en faisant inverse[e->date].
Le tableau d'inverse doit donc être de taille date_max (la plus grande
date que contient le tas).
Exemple:
-------
soit le tas:
-------------------------
T= | 3 | 5 | 4 | 6 | 7 | 9 |
-------------------------
L'arbre correspondant:
3
5 4
6 7 9
Et le tableau d'inverses:
---------------------------------------------
inverse= | -1 | -1 | -1 | 0 | 2 | 1 | 3 | 4 | -1 | 5 |
---------------------------------------------
où -1 correspond à une date absente du tas.
Donc si je veux insérer un évenement e de date 5, je peux connaître
son rang dans le tas (tableau T) en faisant inverse[e->date] et
j'obtiens 1. Si j'obtient -1, je l'insère normalement en mettant à jour
le tableau d'inverses.
Jusque là, tout est simple, pour une date énorme, le tableau d'inverses
est gigantesque! Pour le minimiser, on peut allouer que
date_max-date_min cases et y accéder en faisant :
inverse[e->date-date_min]
Le problème est alors que lors d'une extraction de la racine (je prends
toujours la date la plus petite), je dois realloc le tableau d'inverse
pour supprimer cette racine qui est partie. C'est-à-dire que je dois
enlever la première case mais le realloc ne permet pas cela. Il permet
seulement de tronquer sur la fin du tableau (et surtout de libérer
l'espace mémoire ne servant plus).
Est-ce plus clair ainsi?
Marc Boyer wrote:Que tant que tu nous auras pas expliqué précisement tes
besoins et seulement des sous-parties (j'ai toujours pas
compris précisément le principe des indices inverses), on
aura du mal à trouver une solution optimale.
Désolé si je me suis mal expliqué!
Je reprends point par point.
Tout d'abord, c'est un simulateur à évenements discrets.
Comme dans tout simulateur, on traite des évenements qui vont en
engendrer d'autres (c'est un écheancier).
On a donc besoin de traiter une liste d'évenements toujours triés par
ordre croissant.
J'avais au départ fait une liste chainée simple, ainsi, l'insertion se
faisait en O(n) et l'extraction en 1 (On prend toujours la tête de la
liste qui est l'évenement de plus petite date).
Je me suis ensuite souvenu, qu'une structure de donnée en tas (arbre
binaire dont tous les noeuds ont leurs deux fils supérieurs ou égals)
permettait d'insérer des éléments dans une liste de manière triés en
O(log(n)).
Le problème c'est que mon simulateur peut génèrer plusieurs évenements
à une date T identique. Mon insertion est alors en O(log(n)) ou n est
le nombre de dates. Je me suis alors dit qu'il serait plus performant
d'avoir un algo en O(log(n)) ou n est le nombre de dates distinctes.
Pour ce faire, il faut connaître l'emplacement dans le tas des dates
déjà insérées, d'où l'idée de faire un tableau d'inverse, c'est-à-dire
un tableau où les "numéros des cases" sont des dates et ou le contenu
des cases est un rang dans le tableau du tas. Ainsi si j'insere un
evenement e, je pourrais vérifier si il a déjà été inséré dans le tas
en faisant inverse[e->date].
Le tableau d'inverse doit donc être de taille date_max (la plus grande
date que contient le tas).
Exemple:
-------
soit le tas:
-------------------------
T= | 3 | 5 | 4 | 6 | 7 | 9 |
-------------------------
L'arbre correspondant:
3
5 4
6 7 9
Et le tableau d'inverses:
---------------------------------------------
inverse= | -1 | -1 | -1 | 0 | 2 | 1 | 3 | 4 | -1 | 5 |
---------------------------------------------
où -1 correspond à une date absente du tas.
Donc si je veux insérer un évenement e de date 5, je peux connaître
son rang dans le tas (tableau T) en faisant inverse[e->date] et
j'obtiens 1. Si j'obtient -1, je l'insère normalement en mettant à jour
le tableau d'inverses.
Jusque là, tout est simple, pour une date énorme, le tableau d'inverses
est gigantesque! Pour le minimiser, on peut allouer que
date_max-date_min cases et y accéder en faisant :
inverse[e->date-date_min]
Le problème est alors que lors d'une extraction de la racine (je prends
toujours la date la plus petite), je dois realloc le tableau d'inverse
pour supprimer cette racine qui est partie. C'est-à-dire que je dois
enlever la première case mais le realloc ne permet pas cela. Il permet
seulement de tronquer sur la fin du tableau (et surtout de libérer
l'espace mémoire ne servant plus).
Est-ce plus clair ainsi?
Nicolas writes:Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
De toute maniere l'ordre est maintenu pas un tas.
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Nicolas <jac_dot_otin_@_freesbee_dot_fr> writes:
Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
De toute maniere l'ordre est maintenu pas un tas.
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Nicolas writes:Rapidement, une table de hashage, ça a plusieurs inconvénients:
1) tu perds l'ordre, donc, dans un simu à événement discrets,
tu ne peux pas connaitre sans parcours total la prochaine
date à lequelle un év. va se produire
De toute maniere l'ordre est maintenu pas un tas.
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Marc Boyer writes:2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Deux techniques que j'ai utilisee:
- lors de reallocation, on rehache tout
- apres agrandissement, on garde deux tables temporairement
- lors d'une recherche, on cherche dans la nouvelle puis dans
l'ancienne si on ne l'a pas trouve et on le deplace dans la
nouvelle si necessaire.
- lors d'un ajout, on deplace un element de l'ancienne vers la
nouvelle. Le facteur d'agrandissement est choisi de sorte
qu'on soit sur d'avoir tout deplace avant d'avoir a agrandir
(je l'ai utilise dans des appli interactives ou le rehachage de
tout apres agrandissement pouvait avoir un delai visible par
l'utilisateur)
Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Deux techniques que j'ai utilisee:
- lors de reallocation, on rehache tout
- apres agrandissement, on garde deux tables temporairement
- lors d'une recherche, on cherche dans la nouvelle puis dans
l'ancienne si on ne l'a pas trouve et on le deplace dans la
nouvelle si necessaire.
- lors d'un ajout, on deplace un element de l'ancienne vers la
nouvelle. Le facteur d'agrandissement est choisi de sorte
qu'on soit sur d'avoir tout deplace avant d'avoir a agrandir
(je l'ai utilise dans des appli interactives ou le rehachage de
tout apres agrandissement pouvait avoir un delai visible par
l'utilisateur)
Marc Boyer writes:2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Deux techniques que j'ai utilisee:
- lors de reallocation, on rehache tout
- apres agrandissement, on garde deux tables temporairement
- lors d'une recherche, on cherche dans la nouvelle puis dans
l'ancienne si on ne l'a pas trouve et on le deplace dans la
nouvelle si necessaire.
- lors d'un ajout, on deplace un element de l'ancienne vers la
nouvelle. Le facteur d'agrandissement est choisi de sorte
qu'on soit sur d'avoir tout deplace avant d'avoir a agrandir
(je l'ai utilise dans des appli interactives ou le rehachage de
tout apres agrandissement pouvait avoir un delai visible par
l'utilisateur)
In article , Jean-Marc Bourguet wrote:Marc Boyer writes:2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Deux techniques que j'ai utilisee:
- lors de reallocation, on rehache tout
Donc en O(n)
In article <pxboefsxgrq.fsf@news.bourguet.org>, Jean-Marc Bourguet wrote:
Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Deux techniques que j'ai utilisee:
- lors de reallocation, on rehache tout
Donc en O(n)
In article , Jean-Marc Bourguet wrote:Marc Boyer writes:2) ça se redimensionne pas bien si je me souviens bien
Ah bon, toutes mes tables de hachages sont auto-redimentionnables.
Comment tu gères ça ?
Deux techniques que j'ai utilisee:
- lors de reallocation, on rehache tout
Donc en O(n)
Marc Boyer writes:
Donc avec des reallocations fait pour des tailles en progression
geometrique, le cout des reallocations est de O(N) ou N est la taille
finale. Donc le cout amorti d'une insertion est de O(1). Que veux-tu
de mieux?
Marc Boyer <Marc.Boyer@enseeiht.yahoo.fr.invalid> writes:
Donc avec des reallocations fait pour des tailles en progression
geometrique, le cout des reallocations est de O(N) ou N est la taille
finale. Donc le cout amorti d'une insertion est de O(1). Que veux-tu
de mieux?
Marc Boyer writes:
Donc avec des reallocations fait pour des tailles en progression
geometrique, le cout des reallocations est de O(N) ou N est la taille
finale. Donc le cout amorti d'une insertion est de O(1). Que veux-tu
de mieux?
