Trier les lignes XML d'un fichier

Version imprimable

08/03/2011, 17h11
hellbilly

Trier les lignes XML d'un fichier
Bonjour,

J'ai un fichier avec sur chaque ligne le contenu d'un fichier XML.
Par exemple :
ligne 1 : <?xml version="1.0"><root><key>XXX</key>...</root>
ligne 2 : <?xml version="1.0"><root><key>XXX</key>...</root>

Et pour trier les lignes de ce fichier, j'extrait avec sed les 'XXX' de l'élément <key> que j'enregistre dans un fichier temporaire.
Puis je trie ce fichier temp que je parcours ligne par ligne pour trier mon fichier de départ avec des grep.
Cela donne :
Code:

1 2 3 4 5 6 7 sed 's/.*<key>$[0-9]*$<\/key>.*/\1/g' "$SRC_FILE" > "$KEY_FILE" > "$TMP_FILE" sort -u "$KEY_FILE" | while read KEY do grep "<key>${KEY}</key>" "$SRC_FILE" >> "$TMP_FILE" done
Ca marche bien pas de soucis par contre je cherche une solution plus optimisée pour mon cas mais je ne vois pas comment faire autrement. Une idée ?

Merci!
09/03/2011, 10h59
lennelei

si le début est toujours le même, tu peux peut-être utiliser ça :

Code:

sort -t'<' -k4,4 test.sort $SRC_FILE > $DST_FILE

?

(Edit) sinon, avec perl (plus précis) :

ignore la casse:

Code:

perl -e 'my $table={}; while (<>) {if (/<key>(\w+)<\/key>/) {$table{$1}=$_;}} ; foreach $k (sort {uc($a) cmp uc($b)} keys %table) {print "$table{$k}"; }' $SRC_FILE > $DST_FILE

sans ignorer la casse:

Code:

perl -e 'my $table={}; while (<>) {if (/<key>(\w+)<\/key>/) {$table{$1}=$_;}} ; foreach $k (sort keys %table) {print "$table{$k}"; }' $SRC_FILE > $DST_FILE
09/03/2011, 15h15
hellbilly

Merci pour ta réponse.

Le début peut varier, effectivement c'est dommage car avec juste sort j'aurais pu trier le fichier.

Pour le perl, je connais pas du tout ce langage, c'est une bonne occasion pour m'y mettre un peu :)
Je vais tester si niveau perf ta solution est plus intéressante.

Alors 2 remarques :

1) je viens de remarquer avec ton script que ta clé est uniquement numérique, donc tu devrais utiliser sort -n mais ce n'est pas très important :)

2) côté perf, ne t’inquiète pas : perl est très fort

Pour te donner un exemple, j'ai fait voulu faire un test.

Pour mon premier essai, je me suis dit que j'allais faire un truc léger : 500 000 lignes à trier... mais je me suis emballé car j'ai du arrêter ton script (marre d'attendre) au bout de 6 minutes et 15 000 lignes traitées :(

Donc le second essai : 50 000 lignes seulement.
1) création du fichier de test (je ne me suis pas pris la tête à changer le début, de toute façon, ça ne changerait rien au résultat ici) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
$ perl -e 'for ($i = 1; $i <= 50000; $i++) {print "<?xml version=\"1.0\"><root><key>".$i."</key>...</root>\n";}' | sort -R > test_big_sort.xml
$ head test_big_sort.xml
<?xml version="1.0"><root><key>27126</key>...</root>
<?xml version="1.0"><root><key>43933</key>...</root>
<?xml version="1.0"><root><key>46570</key>...</root>
<?xml version="1.0"><root><key>34619</key>...</root>
<?xml version="1.0"><root><key>5287</key>...</root>
<?xml version="1.0"><root><key>8077</key>...</root>
<?xml version="1.0"><root><key>25905</key>...</root>
<?xml version="1.0"><root><key>47909</key>...</root>
<?xml version="1.0"><root><key>45046</key>...</root>
<?xml version="1.0"><root><key>5979</key>...</root>

2) Avec ton script (modifié pour trier sur du numérique):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ cat sort.sh
#!/bin/sh
sed 's/.*<key>\([0-9]*\)<\/key>.*/\1/g' $1 > $1.key
 
> $1_sh.out
sort -un $1.key | while read KEY
do
    grep "<key>$KEY</key>" $1 >> $1_sh.out
done
$ time ./sort.sh test_big_sort.xml
 
real    2m39.583s
user    2m5.628s
sys     0m8.021s

3) Avec perl (modifié également pour comparer du numérique) :

Code:

1
2
3
4
5
$ time perl -e 'while (<>) {if (/<key>(\w+)<\/key>/) {$table{$1}=$_;}} ; foreach $k (sort {$a <=> $b} keys %table) {print "$table{$k}"; }' test_big_sort.xml > test_big_sort.xml_perl.out
 
real    0m0.262s
user    0m0.244s
sys     0m0.016s

4) Comparaison/contrôles :

Code:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
$ diff test_big_sort.xml_*.out
$ wc test_big_sort.xml_*.out
  50000  100000 2638894 test_big_sort.xml_perl.out
  50000  100000 2638894 test_big_sort.xml_sh.out
 100000  200000 5277788 total
$ head test_big_sort.xml_*.out
==> test_big_sort.xml_perl.out <==
<?xml version="1.0"><root><key>1</key>...</root>
<?xml version="1.0"><root><key>2</key>...</root>
<?xml version="1.0"><root><key>3</key>...</root>
<?xml version="1.0"><root><key>4</key>...</root>
<?xml version="1.0"><root><key>5</key>...</root>
<?xml version="1.0"><root><key>6</key>...</root>
<?xml version="1.0"><root><key>7</key>...</root>
<?xml version="1.0"><root><key>8</key>...</root>
<?xml version="1.0"><root><key>9</key>...</root>
<?xml version="1.0"><root><key>10</key>...</root>
 
==> test_big_sort.xml_sh.out <==
<?xml version="1.0"><root><key>1</key>...</root>
<?xml version="1.0"><root><key>2</key>...</root>
<?xml version="1.0"><root><key>3</key>...</root>
<?xml version="1.0"><root><key>4</key>...</root>
<?xml version="1.0"><root><key>5</key>...</root>
<?xml version="1.0"><root><key>6</key>...</root>
<?xml version="1.0"><root><key>7</key>...</root>
<?xml version="1.0"><root><key>8</key>...</root>
<?xml version="1.0"><root><key>9</key>...</root>
<?xml version="1.0"><root><key>10</key>...</root>
$ tail test_big_sort.xml_*.out
==> test_big_sort.xml_perl.out <==
<?xml version="1.0"><root><key>49991</key>...</root>
<?xml version="1.0"><root><key>49992</key>...</root>
<?xml version="1.0"><root><key>49993</key>...</root>
<?xml version="1.0"><root><key>49994</key>...</root>
<?xml version="1.0"><root><key>49995</key>...</root>
<?xml version="1.0"><root><key>49996</key>...</root>
<?xml version="1.0"><root><key>49997</key>...</root>
<?xml version="1.0"><root><key>49998</key>...</root>
<?xml version="1.0"><root><key>49999</key>...</root>
<?xml version="1.0"><root><key>50000</key>...</root>
 
==> test_big_sort.xml_sh.out <==
<?xml version="1.0"><root><key>49991</key>...</root>
<?xml version="1.0"><root><key>49992</key>...</root>
<?xml version="1.0"><root><key>49993</key>...</root>
<?xml version="1.0"><root><key>49994</key>...</root>
<?xml version="1.0"><root><key>49995</key>...</root>
<?xml version="1.0"><root><key>49996</key>...</root>
<?xml version="1.0"><root><key>49997</key>...</root>
<?xml version="1.0"><root><key>49998</key>...</root>
<?xml version="1.0"><root><key>49999</key>...</root>
<?xml version="1.0"><root><key>50000</key>...</root>

Pour info, pour les 500 000 lignes, perl traite le tout en moins de 4 secondes ;)

Et il y aurait peut-être moyen d'améliorer si ce ne sont que des chiffres (en utilisant un tableau par ex.)

Pour la forme (utilisation d'un tableau):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ time perl -e 'while (<>) {if (/<key>(\w+)<\/key>/) {$table[$1]=$_;}} ; foreach (@table) {print}' test_big_sort.xml > test_big_sort.xml_perl2.out
 
real    0m0.150s
user    0m0.128s
sys     0m0.020s
$ head test_big_sort.xml_perl2.out
<?xml version="1.0"><root><key>1</key>...</root>
<?xml version="1.0"><root><key>2</key>...</root>
<?xml version="1.0"><root><key>3</key>...</root>
<?xml version="1.0"><root><key>4</key>...</root>
<?xml version="1.0"><root><key>5</key>...</root>
<?xml version="1.0"><root><key>6</key>...</root>
<?xml version="1.0"><root><key>7</key>...</root>
<?xml version="1.0"><root><key>8</key>...</root>
<?xml version="1.0"><root><key>9</key>...</root>
<?xml version="1.0"><root><key>10</key>...</root>
$ diff test_big_sort.xml_perl*.out
$ wc -l test_big_sort.xml_perl*.out
  50000 test_big_sort.xml_perl2.out
  50000 test_big_sort.xml_perl.out
 100000 total

09/03/2011, 17h00
lennelei

Et comme je suis bon prince, j'explique le programme si tu ne connais pas perl ;)

Code:

while (<>) {if (/<key>(\w+)<\/key>/) {$table{$1}=$_;}} ; foreach $k (sort {$a <=> $b} keys %table) {print "$table{$k}"; }

Code:

while (<>) {...}

Boucle sur STDIN (le fichier passé en paramètre), à chaque boucle, lit une ligne (stockée dans une variable spéciale $_)

Code:

if (/<key>(\w+)<\/key>/) {$table{$1}=$_;}

Si la ligne ($_) correspond au motif /<key>(\w+)<\/key>/ alors mémorise ce qui est entre parenthèses (\w+) dans la variable $1 c'est à dire un ou plusieurs caractères alphanumériques ou underscore compris entre <key> et </key> (on pourrait remplacer par \w+ par \d+ vu que tu n'as que des chiffres) puis ajoute dans la table de hash table un couple clé/valeur avec pour clé $1 et pour valeur la ligne entière ($_).

Code:

foreach $k (sort {$a <=> $b} keys %table) {...}

Une fois que tout le fichier a été parcouru, boucle sur l'ensemble des clés de la table de hash table (keys %table retourne un tableau des clés de %table) triées numériquement (sort {$a <=> $b} : sort trie, et {$a <=> $b} permet d'indiquer l'algorithme de tri à utiliser, ici, une comparaison numérique... par défaut, c'est à dire sort seul, ça serait du caractère). $k stocke la valeur de la clé.

Code:

print "$table{$k}";

Affiche simplement la valeur correspondant à la clé $k, c'est à dire la ligne complète telle qu'elle avait été stockée au dessus...

Exercice: analyser le programme utilisant un tableau ;)
09/03/2011, 17h52
hellbilly
waaouuu merci pour toutes ces explications et d'avoir pris la peine de faire un test :ccool:

de mon côté, je n'ai testé que sur un fichier (100 Mo / 10000 lignes) pour le moment :
Résultat avec le script initial
Code:

1 2 3 real 20m56.340s user 14m9.153s sys 5m53.882s
et en perl :
Code:

1 2 3 real 0m1.019s user 0m0.596s sys 0m0.392s
en pratique les fichiers font entre 2 et 10 Mo mais les gains vont être quand même importants.

Je sais ce qu'il me reste à faire! :D