Bonjour,
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Bonjour,
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Bonjour,
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Nicolas wrote:Bonjour,
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Nicolas wrote:
Bonjour,
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Nicolas wrote:Bonjour,
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Je ne sais pas ce qu'est un algo en zero-log-de-machin (je ne connais
pas les théories sur les algo) donc je vais probablement dire une
connerie (autant l'annoncer avant)...
Quand tu veux tronquer au début, tu incrémente ce pointeur. Quand tu en
ajouter, tu le décrémente.
C'est plutôt une bonne idée (c'est même la première que j'ai implémenté)
C'est d'ailleurs souvent ce que je fais pour mes tableau où j'ajoute ou
supprime à la fin, pour éviter de désalouer ce que j'aurais probablement
besoin de réallouer quelques instants plus tard (ce qui peut parfois
obliger à copier, si la place libérée a été récupérée par ailleurs)
Je ne sais pas ce qu'est un algo en zero-log-de-machin (je ne connais
pas les théories sur les algo) donc je vais probablement dire une
connerie (autant l'annoncer avant)...
Quand tu veux tronquer au début, tu incrémente ce pointeur. Quand tu en
ajouter, tu le décrémente.
C'est plutôt une bonne idée (c'est même la première que j'ai implémenté)
C'est d'ailleurs souvent ce que je fais pour mes tableau où j'ajoute ou
supprime à la fin, pour éviter de désalouer ce que j'aurais probablement
besoin de réallouer quelques instants plus tard (ce qui peut parfois
obliger à copier, si la place libérée a été récupérée par ailleurs)
Je ne sais pas ce qu'est un algo en zero-log-de-machin (je ne connais
pas les théories sur les algo) donc je vais probablement dire une
connerie (autant l'annoncer avant)...
Quand tu veux tronquer au début, tu incrémente ce pointeur. Quand tu en
ajouter, tu le décrémente.
C'est plutôt une bonne idée (c'est même la première que j'ai implémenté)
C'est d'ailleurs souvent ce que je fais pour mes tableau où j'ajoute ou
supprime à la fin, pour éviter de désalouer ce que j'aurais probablement
besoin de réallouer quelques instants plus tard (ce qui peut parfois
obliger à copier, si la place libérée a été récupérée par ailleurs)
Tu n'as qu'à utiliser deux tableaux : l'un du milieu à la fin,
l'autre du milieu au début...
Tu n'as qu'à utiliser deux tableaux : l'un du milieu à la fin,
l'autre du milieu au début...
Tu n'as qu'à utiliser deux tableaux : l'un du milieu à la fin,
l'autre du milieu au début...
Marc Boyer wrote:Nicolas wrote:Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Ouais, c'est ça.Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
J'avais pensé à un tableau indexé à l'envers (la case 0 se trouvant à
la fin du tableau) mais j'ai toujours le même problème lors du
redimensionnement du tableau dans l'autre sens!
Marc Boyer wrote:
Nicolas wrote:
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Ouais, c'est ça.
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
J'avais pensé à un tableau indexé à l'envers (la case 0 se trouvant à
la fin du tableau) mais j'ai toujours le même problème lors du
redimensionnement du tableau dans l'autre sens!
Marc Boyer wrote:Nicolas wrote:Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Ouais, c'est ça.Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
J'avais pensé à un tableau indexé à l'envers (la case 0 se trouvant à
la fin du tableau) mais j'ai toujours le même problème lors du
redimensionnement du tableau dans l'autre sens!
Nicolas wrote:Marc Boyer wrote:Nicolas wrote:Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Ouais, c'est ça.Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Hum. Un buffer circulaire de taille fixe offre les opération
d'accès en O(1), et ajout/suppression en tête et queue en O(1).
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
C'est un multi-ensemble ?
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
Donc, le tableau d'inverse, tu le parcours toujours, tu ne fais
pas d'accès direct ou dichotomique. Donc, ce tableau d'inverse
peut être une liste.
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
?
J'avais pensé à un tableau indexé à l'envers (la case 0 se trouvant à
la fin du tableau) mais j'ai toujours le même problème lors du
redimensionnement du tableau dans l'autre sens!
Par symétrie, on inverse les avantages et les inconvénients ;-)
Oui, je m'en suis rendu compte... ;-)
Nicolas wrote:
Marc Boyer wrote:
Nicolas wrote:
Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Ouais, c'est ça.
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Hum. Un buffer circulaire de taille fixe offre les opération
d'accès en O(1), et ajout/suppression en tête et queue en O(1).
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
C'est un multi-ensemble ?
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
Donc, le tableau d'inverse, tu le parcours toujours, tu ne fais
pas d'accès direct ou dichotomique. Donc, ce tableau d'inverse
peut être une liste.
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
?
J'avais pensé à un tableau indexé à l'envers (la case 0 se trouvant à
la fin du tableau) mais j'ai toujours le même problème lors du
redimensionnement du tableau dans l'autre sens!
Par symétrie, on inverse les avantages et les inconvénients ;-)
Oui, je m'en suis rendu compte... ;-)
Nicolas wrote:Marc Boyer wrote:Nicolas wrote:Je développe actuellement une librairie pour manipuler des tas.
Pour profiter pleinement des algorithmes déjà découvert en O(log(n)),
j'ai besoin d'un tableau d'inverses (tableau qui stocke le rang de
l'element du tas) pour avoir un accès direct à la mémoire sans parcourir
tout le tas.
Mon problème réside dans l'allocation de ce tableau car il est parfois
tronqué par le début. En effet, realloc permet de rappetisser ou
d'agrandir le tableau par la fin de celui-ci. Mais je voudrais le faire
aussi par le début.
Ex:
1 | 3 | 9 | 6 | 7
insertion par le debut: 55
55 | 1 | 3 | 9 | 6 | 7
Je pourrais bien évidemment realloquer le tableau et recopié toutes les
valeurs mais je perdrais l'avantage des algorithmes en O(log(N))
Globalement, tu veux une file ou tu peux insérer/ajouter aux deux
bouts mais pas au milieu, c'est ça ?
Ouais, c'est ça.Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Hum. Un buffer circulaire de taille fixe offre les opération
d'accès en O(1), et ajout/suppression en tête et queue en O(1).
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
C'est un multi-ensemble ?
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
Donc, le tableau d'inverse, tu le parcours toujours, tu ne fais
pas d'accès direct ou dichotomique. Donc, ce tableau d'inverse
peut être une liste.
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
?
J'avais pensé à un tableau indexé à l'envers (la case 0 se trouvant à
la fin du tableau) mais j'ai toujours le même problème lors du
redimensionnement du tableau dans l'autre sens!
Par symétrie, on inverse les avantages et les inconvénients ;-)
Oui, je m'en suis rendu compte... ;-)
cedric wrote:Tu n'as qu'à utiliser deux tableaux : l'un du milieu à la fin,
l'autre du milieu au début...
Effectivement... Pourquoi n'y ai je pas pensé plus tôt?!
Merci, c'est une super idée!
@+
Nico
cedric wrote:
Tu n'as qu'à utiliser deux tableaux : l'un du milieu à la fin,
l'autre du milieu au début...
Effectivement... Pourquoi n'y ai je pas pensé plus tôt?!
Merci, c'est une super idée!
@+
Nico
cedric wrote:Tu n'as qu'à utiliser deux tableaux : l'un du milieu à la fin,
l'autre du milieu au début...
Effectivement... Pourquoi n'y ai je pas pensé plus tôt?!
Merci, c'est une super idée!
@+
Nico
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Hum. Un buffer circulaire de taille fixe offre les opération
d'accès en O(1), et ajout/suppression en tête et queue en O(1).
Heu... Certe, mais la recherche d'un élément précis se fait en O(n)...
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
C'est un multi-ensemble ?
Oui
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
Donc, le tableau d'inverse, tu le parcours toujours, tu ne fais
pas d'accès direct ou dichotomique. Donc, ce tableau d'inverse
peut être une liste.
Faux!
En fait, je traite des dates (c'est une simulation à évenements
discrets). Mon tas est donc composé d'évenements. Mon tableau d'inverse,
lui, d'indice de date... Il est composé de (date_max - date_min) cases.
Donc, j'ai un accès direct car il me suffit de vérifier que
inv[date_inserée] existe et ainsi j'ai le rang dans le tas!
(je vais quand même aller jeter un oeil du coté des tables de
hachage...)
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
?
??
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Hum. Un buffer circulaire de taille fixe offre les opération
d'accès en O(1), et ajout/suppression en tête et queue en O(1).
Heu... Certe, mais la recherche d'un élément précis se fait en O(n)...
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
C'est un multi-ensemble ?
Oui
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
Donc, le tableau d'inverse, tu le parcours toujours, tu ne fais
pas d'accès direct ou dichotomique. Donc, ce tableau d'inverse
peut être une liste.
Faux!
En fait, je traite des dates (c'est une simulation à évenements
discrets). Mon tas est donc composé d'évenements. Mon tableau d'inverse,
lui, d'indice de date... Il est composé de (date_max - date_min) cases.
Donc, j'ai un accès direct car il me suffit de vérifier que
inv[date_inserée] existe et ainsi j'ai le rang dans le tas!
(je vais quand même aller jeter un oeil du coté des tables de
hachage...)
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
?
??
Avec un buffer circulaire, tu peux faire ça, mais quand on augmentera la
capacité, on sera en O(n).
J y avais bien pensé mais ca ne se gère pas avec une structure de donnée
en tableau et du coup, je perd le O(log(n))!
Hum. Un buffer circulaire de taille fixe offre les opération
d'accès en O(1), et ajout/suppression en tête et queue en O(1).
Heu... Certe, mais la recherche d'un élément précis se fait en O(n)...
Mais ton conteneur là, as-tu besoin de faire des accès par un indice ?
Si la réponse est non, pourquoi pas une simple liste chainée ?
Comme c'est un tas, j'insère toujours en O(log(n)). Par contre,
le problème est l'insertion d'un élément qui éxiste déjà.
C'est un multi-ensemble ?
Oui
Je pourrais gérer le tas pour inserer l'element a la suite mais
je serais alors en O(log(n)) ou n est le nombre d'éléments...
Je serais plus interressé par un algo en O(log(n)) où n est le nombre de
dates distinctes - d'où le tableau d'inverse pour connaître en 1 passe
le rang dans le tas de cette date.
Donc, le tableau d'inverse, tu le parcours toujours, tu ne fais
pas d'accès direct ou dichotomique. Donc, ce tableau d'inverse
peut être une liste.
Faux!
En fait, je traite des dates (c'est une simulation à évenements
discrets). Mon tas est donc composé d'évenements. Mon tableau d'inverse,
lui, d'indice de date... Il est composé de (date_max - date_min) cases.
Donc, j'ai un accès direct car il me suffit de vérifier que
inv[date_inserée] existe et ainsi j'ai le rang dans le tas!
(je vais quand même aller jeter un oeil du coté des tables de
hachage...)
La liste chainée ne convient donc pas car je ne suis plus en 1 passe
mais en n passes! De nouveau, je perd le O(log(n))...
?
??
Mais comme je l'ai dit dans un autre post, plus haut, je vais essayer de
me diriger vers les tables de hachage. Qu'en pensez vous?
Mais comme je l'ai dit dans un autre post, plus haut, je vais essayer de
me diriger vers les tables de hachage. Qu'en pensez vous?
Mais comme je l'ai dit dans un autre post, plus haut, je vais essayer de
me diriger vers les tables de hachage. Qu'en pensez vous?