choix du structure des données

Le
programmation
Bonjour,
Je vais refaire une grande partie de mon travail car j'ai mal choisi
les structures des données car les accès fichiers sont plus coûteux.
Tout mon travail se base sur les fichiers même les résultats
intermédiaires. Le but de mon travail est de trouver une solution à
mon problème mais de plus minimiser le plus possible le temps
d'exécution.

Mais, lorsque j'ai testé le temps de l'exécution CPU concernant la
comparaison de deux fichiers selon les critères bien définis alors
j'ai remarqué que le temps est devenir très longue si nous avons des
fichiers avec des centaines lignes.

On va lire chaque ligne de fichier 1 et le compare avec tous les
lignes de fichier 2. C'est très couteux.

D'après vous :
- Avec quelles structures des données ces deux fichiers seront
remplacés ?

- En général,quelle est la structure des données la moins couteuse en
mémoire et donc temps CPU le plus inférieur possible ?

Je souhaite que vous m'aidez et je n'oublierai pas votre assistance.

Merci.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
nico
Le #20459661
programmation wrote:
Bonjour,
Je vais refaire une grande partie de mon travail car j'ai mal choisi
les structures des données car les accès fichiers sont plus coûteux.
Tout mon travail se base sur les fichiers même les résultats
intermédiaires. Le but de mon travail est de trouver une solution à
mon problème mais de plus minimiser le plus possible le temps
d'exécution.

Mais, lorsque j'ai testé le temps de l'exécution CPU concernant la
comparaison de deux fichiers selon les critères bien définis alors
j'ai remarqué que le temps est devenir très longue si nous avons des
fichiers avec des centaines lignes.

On va lire chaque ligne de fichier 1 et le compare avec tous les
lignes de fichier 2. C'est très couteux.



Toujours travailler en mémoire : tout charger au départ dans tableaux ou
listes et faire les comparaisons à partir de là.
programmation
Le #20461071
> Toujours travailler en mémoire : tout charger au départ dans tableaux ou
listes et faire les comparaisons à partir de là.



Bonjour,

Quels sont les avantages et les limites de chacune entre tableaux et
les listes ou bien il y a une plus rapide que l'autre ?

Mon problème:

J'ai un fichier bien défini X et N fichiers Y de même format.

A chaque fois je compare le fichier X avec un de N fichiers. Donc j'ai
N comparaisons.

le but de comparaison est chercher les lignes qui existent dans X et
qui n'existent pas dans Y

Le principe de comparaison entre les deux fichiers X et Y:
on lit ligne par ligne de fichier X et on parcoure tout le fichier Y
s'il n'existe pas cette ligne dans Y alors on affiche cette ligne
etc ...

Voici un pseudo code :

<code type="c">
for(i=1;i<=N;i++)
while(fgets(s,100,X))
while(fgets(s,100,Y[i]))
//chercher les lignes qui existent dans X et qui n'existent pas dans Y
</code>

On a ici le même traitement :
chercher les lignes qui existent dans X et qui n'existent pas dans Y

Que proposez vous ?

C'est quoi le multi-threading (n threads) et comment adapter ceci à
mon cas ?

Dans mon cas, c'est mieux d'utiliser un tableau ou liste chainée ?

Merci.
nico
Le #20461291
programmation wrote:



Dans mon cas, c'est mieux d'utiliser un tableau ou liste chainée ?




Les listes chainées, c'est lent à la recherche.
Tableaux et recherche dichotomique notamment
programmation
Le #20466871
> Les listes chainées, c'est lent à la recherche.
Tableaux et recherche dichotomique notamment



Si on a fichier qui contient deux champs et on ne sait pas en avance
le nombre des lignes de fichier alors C'est possible d'utiliser un
tableau. Si oui alors comment on fait ceci ?


Dans mon programme C, la fonction de comparaison est :
*rets = compare_files("f.txt", "f2.txt");


Je passe deux fichiers "f.txt" et "f2.txt" à la fonction
'compare_files'
la taille de "f.txt" est toujours plus grande que "f2.txt".
chaque ligne de deux fichiers contient une chaine de caractère.

Je cherche les lignes qui appartiennent à "f.txt" et non pas "f2.txt"
C'est une sorte de différence lignes de "f.txt" moins lignes de
"f2.txt"
à condition:
Une ligne de "f.txt" est identique à une ligne de "f2.txt"
si les deux lignes ont la même valeur et le même nombre des mots qui
forment les deux lignes quelque soit l'ordre des mots puisque l'ordre
des mots n'est pas important dans mon problème.
le plus important c'est : la même valeur et le même nombre

Sinon c'est à dire les deux lignes n'ont pas la même valeur et le mêm e
nombre des mots alors dans ce cas les deux lignes sont différentes.

par exemple:
"nom prenom age" = "nom age prenom"


Sachant que chaque ligne du deux fichiers "f.txt" et "f2.txt" est
composé d'un seul champ (une chaine de caractères)

Soit le premier fichier fichier "f.txt":
nom prenom
nom age
prenom age
prenom emploi
nom prenom age
nom emploi
age emploi
prenom age emploi
nom age emploi
nom prenom emploi
nom prenom age emploi


Soit le deuxième fichier "f2.txt":
nom
prenom
age
emploi
age nom
nom age prenom
nom emploi
age emploi
prenom age emploi
nom prenom emploi

On applique le principe de comparaison alors on obtient ce résultat
intermédiaire:
nom prenom
nom age emploi
nom prenom age emploi

Puis, on garde de ce résultat que les chaines qui ne contiennent pas
autre chaine de ce résultat.
ici, on ne garde pas la chaine "nom prenom age emploi" car elle
contienne la chaine "nom prenom"

Le résultat final souhaité obtenu est :
nom prenom
nom age emploi

Que proposez vous ?

Merci.
nico
Le #20467871
programmation wrote:
Les listes chainées, c'est lent à la recherche.
Tableaux et recherche dichotomique notamment



Si on a fichier qui contient deux champs et on ne sait pas en avance
le nombre des lignes de fichier alors C'est possible d'utiliser un
tableau. Si oui alors comment on fait ceci ?



malloc(), c'est la base du C.
TSalm
Le #20468131
Le Sun, 01 Nov 2009 20:59:34 +0100, nico
programmation wrote:
Les listes chainées, c'est lent à la recherche.
Tableaux et recherche dichotomique notamment


Si on a fichier qui contient deux champs et on ne sait pas en avance
le nombre des lignes de fichier alors C'est possible d'utiliser un
tableau. Si oui alors comment on fait ceci ?



malloc(), c'est la base du C.



Ne faudrait-il pas mieux utiliser un vector ?
TSalm
Le #20468121
Le Sun, 01 Nov 2009 21:40:08 +0100, TSalm
Le Sun, 01 Nov 2009 20:59:34 +0100, nico
programmation wrote:
Les listes chainées, c'est lent à la recherche.
Tableaux et recherche dichotomique notamment


Si on a fichier qui contient deux champs et on ne sait pas en avance
le nombre des lignes de fichier alors C'est possible d'utiliser un
tableau. Si oui alors comment on fait ceci ?



malloc(), c'est la base du C.



Ne faudrait-il pas mieux utiliser un vector ?



oups, pardon, c'est du C...
programmation
Le #20480641
Je n'arrive pas à trouver le bon chois entre liste chainée et tableau
surtout je n'intéresse a
Que proposez vous ?
nico
Le #20482591
programmation wrote:
Je n'arrive pas à trouver le bon chois entre liste chainée et tableau
surtout je n'intéresse a
Que proposez vous ?



Comme j'ai dit, une recherche dans liste chainée est beaucoup plus lente
que recherche dicho dans un tableau.
Bertrand Lenoir-Welter
Le #20483171
> Je n'arrive pas à trouver le bon chois entre liste chainée et tableau
surtout je n'intéresse a



à ?


Que proposez vous ?



Je propose un tableau lorsque le nombre d'éléments est constant ou varie
peu ou que vous êtes absolument sûr qu'il ne dépassera jamais au grand
jamais la taille allouée, et plutôt la liste chaînée quand vous ne savez
pas à l'avance combien d'éléments seront stockés dedans.

Pour les performances, à moins de faire sans cesse des recherches sur un
élément, vous ne verrez pas trop la différence. Personnellement, j'ai un
gros faible pour les listes chaînées qui ont une souplesse que rien
n'égale, mais si vous débutez, vous allez forcément avoir des bugs à
l'exécution. Il y a des réflexes qui s'acquièrent peu à peu (contruction
de la liste avec cas du tout premier élément, insertion d'un élément,
suppression d'un élément en recollant le chaînage, suppression de la
liste, mise et remise à NULL du pointeur de liste et du pointeur final,
etc.). Il faut pratiquer avant que tout ça se rode.
Publicité
Poster une réponse
Anonyme