Discussion :

[siempre]

Bonjour,
J'ai une demande et j'ai besoin de vos aides. En réalité, J'ai fichier XML "input.xml" de taille volumineux. Pour lire ce fichier, j'ai utilisé la fonction 'lire_fichier(nom de fichier)'.
Dans mon cas, je dois décomposer ce fichier xml en plusieurs fichiers XML selon des critères bien définis.
Supposons que N est le nombre de ces fichiers décomposés.

Je vais faire le même traitement X pour chacun de ces N fichiers

Voici une partie de code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
for(i=1;i <= N;i++)
{
 
 sprintf(tmp,"input%d",i);
 lire_fichier(tmp);
 //le même traitement  X
..........
............
}

J'ai testé ce code sur ma machine alors ceci prendre beaucoup de temps.

Mon but est d'avoir le temps d'exécution le moins possible.

Est ce que c'est possible d'avoir un temps plus longue si on a travaille sur les N fichiers au lieu de travailler sur un seul fichier ou bien ceci dépend d'autres facteurs?

Dans mon cas, est ce que le mécanisme de parallélisme est possible ? c'est à dire on exécute chaque traitement sur une machine portant un fichier et donc on va utiliser N machines ?
C'est à dire on lance le traitement en même temps. Mais, ceci garantie que on va obtenir le résultat en un temps le moins possible ?

Que proposez vous ?

Merci.

[Mac LAK]

J'ai testé ce code sur ma machine alors ceci prendre beaucoup de temps.

Mon but est d'avoir le temps d'exécution le moins possible.

Au cas où : pense quand même à vérifier que des outils XML adaptés (XSL, librairies-parser, génération de code, etc.) ne te simplifieraient pas la vie, dans le cas où tu n'aurais que l'obligation de résultat et non pas l'obligation de moyens.

Est ce que c'est possible d'avoir un temps plus longue si on a travaille sur les N fichiers au lieu de travailler sur un seul fichier ou bien ceci dépend d'autres facteurs?

Cela dépend d'autres facteurs : typiquement, le disque dur est une ressource critique (=accessible par un seul élément à la fois), donc avoir 10 threads qui tapent dedans allègrement est plus pénalisant qu'autre chose en général : tu perds beaucoup de temps via le temps d'accès du disque...
Dans ton cas, il faudrait un thread lisant les fichiers, mis en cache en mémoire, et distribuant ensuite le boulot à des threads qui n'auraient alors plus besoin d'accéder au disque dur. Ils pourraient alors bénéficier correctement des cœurs multiples disponibles.

Dans mon cas, est ce que le mécanisme de parallélisme est possible ? c'est à dire on exécute chaque traitement sur une machine portant un fichier et donc on va utiliser N machines ?

Tu peux découper ça avec un traitement par cœur de CPU, même. Le transfert sur une machine distante (clustering) ne peut être une solution intéressante QUE si l'on vérifie auparavant que le temps de transfert par le réseau n'est pas pénalisant par rapport au temps de traitement de chaque fichier. Plus ton fichier est petit et plus le traitement est long, et plus le clustering devient intéressant.

C'est à dire on lance le traitement en même temps. Mais, ceci garantie que on va obtenir le résultat en un temps le moins possible ?

Tout dépend de ce que tu mesures : le temps réel physique (on commence le boulot à 13h00 et on le finit à 13h10, donc 10 minutes) ou le temps CPU consommé (si tu parallélises sur 20 unités d'exécution, tes 10 minutes "réelles" deviennent 10 x 20 = 200 minutes...).

Paralléliser coûte en général plus cher en temps CPU qu'un traitement parallèle, mais permet de gagner du temps "réel". Tout dépend ensuite de ce qui est le plus coûteux pour toi...

[siempre]

Ce qui est important pour moi est le temps CPU.

[Mac LAK]

Heu... As-tu bien compris ce qu'était le temps CPU, et ne confonds-tu pas avec le temps physique "réel" ?

Si oui, tu cherches à le maximiser (= saturer la machine), ou à le réduire ?

[siempre]

As-tu bien compris ce qu'était le temps CPU, et ne confonds-tu pas avec le temps physique "réel" ?

non.

tu cherches à le maximiser (= saturer la machine), ou à le réduire ?

à le réduire.

[Mac LAK]

Alors aucun intérêt à paralléliser, vu que ça va augmenter le temps CPU utilisé.

Si tu veux réduire le temps CPU (= la charge de la machine), on passe par des processus peu prioritaires et des traitements les moins lourds/intrusifs possibles : cela veut dire virer l'affichage, virer les tests "inutiles", présupposer la bonne forme des entrées et bosser en laissant du temps aux autres processus (ex : des "sleeps" placés judicieusement, passer toutes les I/O en asynchrone, etc.).


C'est pour ça que je te demandais si tu ne confondais pas les deux... Réduire le temps CPU utilisé n'a en général de sens que sur une machine intensivement partagée sur laquelle le temps CPU est "cher" (serveur d'applications par exemple), et n'a que rarement de sens / but sur des machines "personnelles".

[siempre]

Bonjour,

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
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

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?

Moi je mesure le temps d'exécution de comparaison entre deux fichiers.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
debut = clock();
//comparaison entre deux fichiers
fin = clock();
 
printf(stderr, "temps : %f\n", (double)(fin-debut) / (double) CLOCKS_PER_SEC);

lorsque je lance une comparaison entre deux fichiers alors on a un temps t très longue par exemples t = milliers des secondes ou bien la machine se plante.
par exemple X et Y contiennent des centaines des lignes.


Merci.

[Mac LAK]

Moi je mesure le temps d'exécution de comparaison entre deux fichiers.

Ce que tu mesures, c'est le temps physique réel... Le temps que tu vois TOI, et non pas le temps machine (qui peut se résumer en "nombre total de cycles CPU utilisés sur toutes les unités d'exécution possibles").
Je savais bien que tu confondais...

lorsque je lance une comparaison entre deux fichiers alors on a un temps t très longue par exemples t = milliers des secondes ou bien la machine se plante.
par exemple X et Y contiennent des centaines des lignes.

Si elle se plante, t'as une erreur dans tes algos, tout simplement.
Sinon, effectivement, la parallélisation est une bonne option, il faut commencer par mettre en mémoire (= en cache) le fichier d'origine X, et lancer un thread par coeur sur la comparaison avec les autres fichiers (un thread se chargeant de la répartition). Les données du fichier X doivent bien sûr être considérées comme étant en lecture seule.

Ensuite, chaque thread de travail va lire le fichier qu'il doit comparer, effectuer ladite comparaison, puis retourner un résultat.
Le thread de répartition, lui, peut être le thread principal. Il va faire la liste des fichiers à comparer pour commencer, charger le fichier de référence X, puis créer (et alimenter !) les threads de calcul tout en récupérant / concaténant les résultats.

[siempre]

et non pas le temps machine (qui peut se résumer en "nombre total de cycles CPU utilisés sur toutes les unités d'exécution possibles").

Donc, comment on mesure le temps CPU ? il y a des fonctions prédéfinis en C permettant de mesurer ce temps ?

Si elle se plante, t'as une erreur dans tes algos, tout simplement.

Je voulais dire que le résultat apparait sur écran après un certain temps.

Sinon, effectivement, la parallélisation est une bonne option, il faut commencer par mettre en mémoire (= en cache) le fichier d'origine X, et lancer un thread par coeur sur la comparaison avec les autres fichiers (un thread se chargeant de la répartition). Les données du fichier X doivent bien sûr être considérées comme étant en lecture seule.

Ensuite, chaque thread de travail va lire le fichier qu'il doit comparer, effectuer ladite comparaison, puis retourner un résultat.
Le thread de répartition, lui, peut être le thread principal. Il va faire la liste des fichiers à comparer pour commencer, charger le fichier de référence X, puis créer (et alimenter !) les threads de calcul tout en récupérant / concaténant les résultats.

Je vous demande c'est possible de m'expliquer encore votre idée et c'est possible un pseudo code ou code de votre solution ?


Merci.

[Sve@r]

Bonjour,

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 ...

Ca c'est l'algo du débutant ou de celui qui n'a rien d'autre.

En revanche, si tes 2 fichiers sont triés tous deux sur le même critère, alors tu peux réduire tes temps de recherche de façon exponentielle en utilisant l'appareillage.
Le principe est de lire alternativement l'un ou l'autre des deux fichiers en se basant sur leur tri. Si l'info du fichier 1 est plus petite que l'info du fichier 2, alors on continue à lire le fichier 1. Si l'info devient tout d'un coup plus grande, alors on sait que l'info du fichier 2 n'est pas dans le fichier 1 sinon on aurait eu une égalité. Et on se met alors à lire le fichier 2 jusqu'à ce qu'on dépasse l'info du fichier 1. On rebascule alors sur le fichier 1 et ainsi de suite

Algo:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ouvrir fichier 1
ouvrir fichier 2
flag1=vrai
flag2=vrai
tant que not eof fichier 1 ou not eof fichier 2
faire
    si flag1 
    alors
       lire fichier 1
       flag1=faux
   fin si
 
    si flag2
    alors
       lire fichier 2
       flag2=faux
   fin si
 
   si info fichier1 = info fichier2
   alors
         info commune
   fin si
 
   si info fichier1 <= info fichier2
   alors
        flag1=vrai
   fin si
 
   si info fichier2 <= info fichier1
   alors
        flag2=vrai
   fin si
fin faire
 
fermer fichiers

Faut affiner un peu le truc (ne pas lire un fichier dont l'eof aura été atteint) mais l'idée est là. Et cet algo peut très bien être étendu sur 3, 4, 50 fichiers lus en parallèles. Normalement il est enseigné dans les débuts des études d'informatique...