Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
adebaene
"tche" wrote in message news:<bq107s$fu2$...
Bonjour,
J'ai un fichier texte contenant des evenements : date debut date fin et autres info.
Je dois trier ces evenements nettoyer les fichiers de evenements echus. Selectionner ceux ayant eu lieu pendant une plage temporelle etc...
J'hésite entre mettre le fichier dans un arbre binaire de recherche ou dans une liste chainée afin d'effectuer ces opérations
Si quelqu' connait un document sur les avantages de l'une et de l'autre méthode ...
J'aurais tendance à dire une hashtable (ou une table de map basée sur un arbre binaire en sous-main) avec le timestamp de l'événement. En C++, std::map (ou peut être std::multimap) me semble bien adapté.
Arnaud
"tche" <tche@n.com> wrote in message news:<bq107s$fu2$1@news-reader5.wanadoo.fr>...
Bonjour,
J'ai un fichier texte contenant des evenements : date debut date fin et
autres info.
Je dois trier ces evenements nettoyer les fichiers de evenements echus.
Selectionner ceux ayant eu lieu pendant une plage temporelle etc...
J'hésite entre mettre le fichier dans un arbre binaire de recherche ou dans
une liste chainée afin d'effectuer ces opérations
Si quelqu' connait un document sur les avantages de l'une et de l'autre
méthode ...
J'aurais tendance à dire une hashtable (ou une table de map basée sur
un arbre binaire en sous-main) avec le timestamp de l'événement. En
C++, std::map (ou peut être std::multimap) me semble bien adapté.
J'ai un fichier texte contenant des evenements : date debut date fin et autres info.
Je dois trier ces evenements nettoyer les fichiers de evenements echus. Selectionner ceux ayant eu lieu pendant une plage temporelle etc...
J'hésite entre mettre le fichier dans un arbre binaire de recherche ou dans une liste chainée afin d'effectuer ces opérations
Si quelqu' connait un document sur les avantages de l'une et de l'autre méthode ...
J'aurais tendance à dire une hashtable (ou une table de map basée sur un arbre binaire en sous-main) avec le timestamp de l'événement. En C++, std::map (ou peut être std::multimap) me semble bien adapté.
Arnaud
Cyrille \cns\ Szymanski
>> Je dois trier ces evenements nettoyer les fichiers de evenements echus. Selectionner ceux ayant eu lieu pendant une plage temporelle etc...
J'hésite entre mettre le fichier dans un arbre binaire de recherche ou dans une liste chainée afin d'effectuer ces opérations
J'aurais tendance à dire une hashtable (ou une table de map basée sur un arbre binaire en sous-main) avec le timestamp de l'événement. En C++, std::map (ou peut être std::multimap) me semble bien adapté.
Tout d'abord le plus simple : si le nombre d'éléments à traiter est relativement petit (ce n'est pas le fichier de la sécu quoi), il n'est peut-être pas nécessaire de déployer l'artillerie lourde et un quicksort + recherche dichotomique dans un tableau fera l'affaire.
Liste chaînée : non, se ne vois pas l'intérêt dans ce cas.
La réponse générale à ce type de question est la hashtable mais elle n'est pas forcément la meilleure.
Si tes événements ne sont indexés que par leur date, c'est à dire un seul critère qui est totalement ordonné, alors l'arbre fera l'affaire. Cependant un arbre efficace est assez difficile et lourd à implémenter. La table de hashage convient tout à fait et a l'avantage d'avoir un temps d'accès en o(1).
Un des avantages de l'arbre (ou même du tableau) par rapport à la hashtable est la possibilité de le parcourir. Avec une hashtable pour sélectionner tous les éléments entre 2 dates, tu dois soit parcourir tous les éléments, soit parcourir toutes les dates. Alors le temps d'accès en o(1) devient un o(n).
Par contre avec un arbre ou un tableau, il suffit de rechercher l'élément le plus vieux de la plage de dates et de parcourir l'arbre (type GRD par exemple) jusqu'à l'événement le plus jeune. Et on ne passe que par des événement de la plage.
>> Je dois trier ces evenements nettoyer les fichiers de evenements
echus. Selectionner ceux ayant eu lieu pendant une plage temporelle
etc...
J'hésite entre mettre le fichier dans un arbre binaire de recherche
ou dans une liste chainée afin d'effectuer ces opérations
J'aurais tendance à dire une hashtable (ou une table de map basée sur
un arbre binaire en sous-main) avec le timestamp de l'événement. En
C++, std::map (ou peut être std::multimap) me semble bien adapté.
Tout d'abord le plus simple : si le nombre d'éléments à traiter est
relativement petit (ce n'est pas le fichier de la sécu quoi), il n'est
peut-être pas nécessaire de déployer l'artillerie lourde et un quicksort
+ recherche dichotomique dans un tableau fera l'affaire.
Liste chaînée : non, se ne vois pas l'intérêt dans ce cas.
La réponse générale à ce type de question est la hashtable mais elle
n'est pas forcément la meilleure.
Si tes événements ne sont indexés que par leur date, c'est à dire un seul
critère qui est totalement ordonné, alors l'arbre fera l'affaire.
Cependant un arbre efficace est assez difficile et lourd à implémenter.
La table de hashage convient tout à fait et a l'avantage d'avoir un temps
d'accès en o(1).
Un des avantages de l'arbre (ou même du tableau) par rapport à la
hashtable est la possibilité de le parcourir. Avec une hashtable pour
sélectionner tous les éléments entre 2 dates, tu dois soit parcourir tous
les éléments, soit parcourir toutes les dates. Alors le temps d'accès en
o(1) devient un o(n).
Par contre avec un arbre ou un tableau, il suffit de rechercher l'élément
le plus vieux de la plage de dates et de parcourir l'arbre (type GRD par
exemple) jusqu'à l'événement le plus jeune. Et on ne passe que par des
événement de la plage.
>> Je dois trier ces evenements nettoyer les fichiers de evenements echus. Selectionner ceux ayant eu lieu pendant une plage temporelle etc...
J'hésite entre mettre le fichier dans un arbre binaire de recherche ou dans une liste chainée afin d'effectuer ces opérations
J'aurais tendance à dire une hashtable (ou une table de map basée sur un arbre binaire en sous-main) avec le timestamp de l'événement. En C++, std::map (ou peut être std::multimap) me semble bien adapté.
Tout d'abord le plus simple : si le nombre d'éléments à traiter est relativement petit (ce n'est pas le fichier de la sécu quoi), il n'est peut-être pas nécessaire de déployer l'artillerie lourde et un quicksort + recherche dichotomique dans un tableau fera l'affaire.
Liste chaînée : non, se ne vois pas l'intérêt dans ce cas.
La réponse générale à ce type de question est la hashtable mais elle n'est pas forcément la meilleure.
Si tes événements ne sont indexés que par leur date, c'est à dire un seul critère qui est totalement ordonné, alors l'arbre fera l'affaire. Cependant un arbre efficace est assez difficile et lourd à implémenter. La table de hashage convient tout à fait et a l'avantage d'avoir un temps d'accès en o(1).
Un des avantages de l'arbre (ou même du tableau) par rapport à la hashtable est la possibilité de le parcourir. Avec une hashtable pour sélectionner tous les éléments entre 2 dates, tu dois soit parcourir tous les éléments, soit parcourir toutes les dates. Alors le temps d'accès en o(1) devient un o(n).
Par contre avec un arbre ou un tableau, il suffit de rechercher l'élément le plus vieux de la plage de dates et de parcourir l'arbre (type GRD par exemple) jusqu'à l'événement le plus jeune. Et on ne passe que par des événement de la plage.
