Représenter un arbre sous forme de liste

Le
Olivier Miakinen
Bonjour,

Me voici avec un nouveau challenge. Cette fois, je n'ai besoin de le
faire fonctionner que sur une seule machine, alors cela peut aussi
bien être en perl qu'en awk, ou tout autre outil dont je pourrais
disposer.

Noter que s'il n'y a pas de solution simple avec les outils existants
je pourrai toujours écrire un programme en C (je sais le faire, c'est
juste que ça me prendra un peu plus de temps). Mais je fais confiance
à l'ingéniosité des lecteurs de ce groupe, je vous ai déjà vu me
proposer des solutions géniales.

J'ai un fichier qui ressemble à ceci (je coupe pas mal de lignes, c'est
juste pour un exemple) :
=
+-1 -
+-3 -
+-6 -
+-1 -
+-2 -
| +-1 -
| +-2 GENERATE oid interfaces
| | +-1 GENERATE attribute ifNumber
| | +-2 ignore table ifTable
| | +-1 GENERATE entry ifEntry
| | +-1 GENERATE attribute ifIndex (index)
| | +-2 GENERATE attribute ifDescr
| | +-3 GENERATE attribute ifType
| | +-4 GENERATE attribute ifMtu
| +-31 ignore module-identity ifMIB
| +-1 GENERATE oid ifMIBObjects
| | +-1 ignore table ifXTable
| | | +-1 GENERATE entry ifXEntry
| | | +-1 GENERATE attribute ifName
| | | +-2 GENERATE attribute ifInMulticastPkts
| | | +-3 GENERATE attribute ifInBroadcastPkts
| | | +-4 GENERATE attribute ifOutMulticastPkts
| | | +-5 GENERATE attribute ifOutBroadcastPkts
| | | +-6 ignore attribute ifHCInOctets (counter64)
| | | +-7 ignore attribute ifHCInUcastPkts (counter64)
| | +-2 ignore table ifStackTable
| +-2 ignore oid ifConformance
| +-1 ignore oid ifGroups
| | +-1 ignore object-group ifGeneralGroup
| | +-2 ignore object-group ifFixedLengthGroup
| +-2 ignore oid ifCompliances
| +-1 ignore module-compliance ifCompliance
| +-2 ignore module-compliance ifCompliance2
| +-3 ignore module-compliance ifCompliance3
+-6 -
+-3 -
+-1 -
+-1 -
+-5 -
+-3 GENERATE notification-type linkDown
+-4 GENERATE notification-type linkUp
=

On y voit un arbre où chaque n½ud est numéroté, le nombre de caractères
(espaces, "|", '+' ou '-') précédant chaque numéro valant deux fois la
profondeur de l'arbre. Après le numéro, on trouve des espaces, puis
soit un caractère '-', soit un mot-clé 'ignore' ou 'GENERATE' suivi
d'un type d'objet puis du nom de l'objet.

En gros, je ne m'intéresse qu'aux lignes avec GENERATE, mais pour
chacune de ces lignes je voudrais afficher la liste de tous les
nombres depuis la racine de l'arbre, comme ceci :
=
(1 3 6 1 2 1 2 ) GENERATE oid interfaces
(1 3 6 1 2 1 2 1 ) GENERATE attribute ifNumber
(1 3 6 1 2 1 2 2 1 ) GENERATE entry ifEntry
(1 3 6 1 2 1 2 2 1 1 ) GENERATE attribute ifIndex (index)
(1 3 6 1 2 1 2 2 1 2 ) GENERATE attribute ifDescr
(1 3 6 1 2 1 2 2 1 3 ) GENERATE attribute ifType
(1 3 6 1 2 1 2 2 1 4 ) GENERATE attribute ifMtu
(1 3 6 1 2 1 31 1 ) GENERATE oid ifMIBObjects
(1 3 6 1 2 1 31 1 1 1 ) GENERATE entry ifXEntry
(1 3 6 1 2 1 31 1 1 1 1 ) GENERATE attribute ifName
(1 3 6 1 2 1 31 1 1 1 2 ) GENERATE attribute ifInMulticastPkts
(1 3 6 1 2 1 31 1 1 1 3 ) GENERATE attribute ifInBroadcastPkts
(1 3 6 1 2 1 31 1 1 1 4 ) GENERATE attribute ifOutMulticastPkts
(1 3 6 1 2 1 31 1 1 1 5 ) GENERATE attribute ifOutBroadcastPkts
(1 3 6 1 6 3 1 1 5 3 ) GENERATE notification-type linkDown
(1 3 6 1 6 3 1 1 5 4 ) GENERATE notification-type linkUp
=

Comme je le disais, en C je sais récupérer le nombre de caractères
d'indentation grâce à sscanf et « %* », et du coup construire petit
à petit la liste des entiers :
sscanf(line, "%*[ |+-]%n%u %s", &indent, &subid, genstatus);

Mais en shell (ou awk, perl, etc.) ?

Cordialement,
--
Olivier Miakinen
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
Olivier Miakinen
Le #24425551
Le 24/04/2012 11:17, j'écrivais :

Comme je le disais, en C je sais récupérer le nombre de caractères
d'indentation grâce à sscanf et « %* »,



Je voulais dire avec %n bien sûr. L'* c'est pour ne pas tenir compte
du contenu.

et du coup construire petit
à petit la liste des entiers :
sscanf(line, "%*[ |+-]%n%u %s", &indent, &subid, genstatus);
Damien Wyart
Le #24425771
Bonjour,

* Olivier Miakinen
[...]
Comme je le disais, en C je sais récupérer le nombre de caractères
d'indentation grâce à sscanf et « %* », et du coup construire petit
à petit la liste des entiers :
sscanf(line, "%*[ |+-]%n%u %s", &indent, &subid, genstatus);

Mais en shell (ou awk, perl, etc.) ?



Voici une proposition en Python, en espérant que ça sera disponible sur
les machines concernées :

import re

stored_indent = 0
numbers = []

data_file = open("data", "r")

for line in data_file:
match = re.search('[0-9]+', line)
current_number = int(match.group())
current_indent = match.start() / 2
for _ in range(stored_indent - current_indent + 1):
numbers.pop()
numbers.append(current_number)
stored_indent = current_indent
pos = line.find('GENERATE')
if (pos != -1):
res_line = '('
for n in numbers:
res_line = res_line + str(n) + ' '
res_line = res_line + ') ' + line[pos:]
print res_line,

data_file.close()


Je pense que l'algorithme est bon, mais je n'avais qu'un jeu de test
pour le mettre à l'épreuve ;-) J'ai adopté le formatage de votre message
initial pour la sortie, mais cela peut être ajusté facilement.

On pourrait faire équivalent en Perl mais je suis moins à l'aise ; dans
les deux cas, je pense que l'on a un bon compromis entre des outils Unix
traditionnels et du C, en termes de lisibilité et de concision.

--
DW
Olivier Miakinen
Le #24425981
Bonjour,

Le 24/04/2012 12:47, Damien Wyart a écrit :

Voici une proposition en Python, en espérant que ça sera disponible sur
les machines concernées :



Il n'y a pas Python sur le Sun où sont les fichiers, mais je les
ai copiés sur un Windows avec Cygwin, où Python est déjà installé
(probablement par défaut, car je ne vois pas qui aurait pu
l'installer sinon).

[...]

Je pense que l'algorithme est bon, mais je n'avais qu'un jeu de test
pour le mettre à l'épreuve ;-) J'ai adopté le formatage de votre message
initial pour la sortie, mais cela peut être ajusté facilement.



Je viens de tester sur un autre fichier, que j'ai renommé "data" pour le
test. Tout semble fonctionner à merveille, et le formatage est parfait
pour ce que je veux en faire.

On pourrait faire équivalent en Perl mais je suis moins à l'aise ; dans
les deux cas, je pense que l'on a un bon compromis entre des outils Unix
traditionnels et du C, en termes de lisibilité et de concision.



Je ne connais pratiquement pas le Perl, mais encore moins le Python, et
du coup cela me donne l'occasion de m'y mettre. Et je suis d'accord que
c'est un bon compromis (de même que awk, que j'utilise généralement pour
ce genre de choses).

Cordialement,
--
Olivier Miakinen
Stephane Chazelas
Le #24425971
2012-04-24 11:17:21 +0200, Olivier Miakinen:
[...]
J'ai un fichier qui ressemble à ceci (je coupe pas mal de lignes, c'est
juste pour un exemple) :
======================================================================== > +-1 -
+-3 -
+-6 -
+-1 -
+-2 -
| +-1 -
| +-2 GENERATE oid interfaces
| | +-1 GENERATE attribute ifNumber
| | +-2 ignore table ifTable
| | +-1 GENERATE entry ifEntry
| | +-1 GENERATE attribute ifIndex (index)


[...]
nombres depuis la racine de l'arbre, comme ceci :
======================================================================== > (1 3 6 1 2 1 2 ) GENERATE oid interfaces
(1 3 6 1 2 1 2 1 ) GENERATE attribute ifNumber
(1 3 6 1 2 1 2 2 1 ) GENERATE entry ifEntry
(1 3 6 1 2 1 2 2 1 1 ) GENERATE attribute ifIndex (index)


[...]

perl -lne 'if (/(.*?)(d+)s+((S+).*)/) {$n=length($1)/2;
$a[$n]=$2; print "(@a[1..$n]) $3" if $4 eq "GENERATE"}'

--
Stephane
Olivier Miakinen
Le #24426061
Le 24/04/2012 14:26, Stephane Chazelas a écrit :

perl -lne 'if (/(.*?)(d+)s+((S+).*)/) {$n=length($1)/2;
$a[$n]=$2; print "(@a[1..$n]) $3" if $4 eq "GENERATE"}'



« length($1)/2 », tout simplement... C'est drôle comme ça paraît
évident après que tu l'as écrit !

Quoi qu'il en soit, je l'ai testé, et en rajoutant deux espaces
dans le print (c.-à-d. "(@a[1..$n] ) $3") ça donne à l'octet
près le même résultat que le script Python de Damien.

Encore merci à tous les deux !

--
Olivier Miakinen
Damien Wyart
Le #24426051
* Stephane Chazelas
perl -lne 'if (/(.*?)(d+)s+((S+).*)/) {$n=length($1)/2;
$a[$n]=$2; print "(@a[1..$n]) $3" if $4 eq "GENERATE"}'



Très joli !

--
DW
Olivier Miakinen
Le #24427381
Le 24/04/2012 14:41, Damien Wyart répondait à Stephane Chazelas :

perl -lne 'if (/(.*?)(d+)s+((S+).*)/) {$n=length($1)/2;
$a[$n]=$2; print "(@a[1..$n]) $3" if $4 eq "GENERATE"}'



Très joli !



N'est-ce pas ? Ça donnerait presque envie d'inventer des problèmes
farfelus, sans besoin réel, rien que pour le plaisir de voir Stéphane
y apporter une solution en une ligne !

Rassurez-vous, ça n'a encore jamais été mon cas, et je crois que je
n'oserais pas le faire...

Cordialement,
--
Olivier Miakinen
Erwan David
Le #24427371
Olivier Miakinen
Le 24/04/2012 14:41, Damien Wyart répondait à Stephane Chazelas :

perl -lne 'if (/(.*?)(d+)s+((S+).*)/) {$n=length($1)/2;
$a[$n]=$2; print "(@a[1..$n]) $3" if $4 eq "GENERATE"}'



Très joli !



N'est-ce pas ? Ça donnerait presque envie d'inventer des problèmes
farfelus, sans besoin réel, rien que pour le plaisir de voir Stéphane
y apporter une solution en une ligne !

Rassurez-vous, ça n'a encore jamais été mon cas, et je crois que je
n'oserais pas le faire...



Pour les amateurs, les résultats du dernier IOCCC sont parus... Y'a des
jolis programmes.

--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé
Cyrille Lefevre
Le #24427931
Le 24/04/2012 14:26, Stephane Chazelas a écrit :
2012-04-24 11:17:21 +0200, Olivier Miakinen:
[...]
J'ai un fichier qui ressemble à ceci (je coupe pas mal de lignes, c' est
juste pour un exemple) :
======================== ========================= ========================
+-1 -
+-3 -
+-6 -
+-1 -
+-2 -
| +-1 -
| +-2 GENERATE oid interfaces
| | +-1 GENERATE attribute ifNumber
| | +-2 ignore table ifTable
| | +-1 GENERATE entry ifEntry
| | +-1 GENERATE attribute ifIndex (index)


[...]
nombres depuis la racine de l'arbre, comme ceci :
======================== ========================= ========================
(1 3 6 1 2 1 2 ) GENERATE oid interfaces
(1 3 6 1 2 1 2 1 ) GENERATE attribute ifNumber
(1 3 6 1 2 1 2 2 1 ) GENERATE entry ifEntry
(1 3 6 1 2 1 2 2 1 1 ) GENERATE attribute ifIndex (index)


[...]

perl -lne 'if (/(.*?)(d+)s+((S+).*)/) {$n=length($1)/2;
$a[$n]=$2; print "(@a[1..$n]) $3" if $4 eq "GENERATE"}'



Bonjour,

la même en awk '
match($0, /[0-9]+/) {
n = (RSTART-1) / 2
a[n] = substr($0, RSTART, RLENGTH)
}
/GENERATE/ {
r = ""; s = "("
for (i = 1; i <= n; i++) {
r = r s a[i]
s = " "
}
r = r " )"
print r substr($0, RSTART + RLENGTH + 1)
}
'

bon, sur ce coup là, j'ai tout simplement passé le code perl au compi lo
perl2awk %^)

c'est quand même plus simple que du python ou du perl, et plus portable
surtout ;^p

voyons les perf...

v2$ wc snmp.txt*
41 201 1803 snmp.txt
41000 201000 1803000 snmp.txt2
410000 2010000 18030000 snmp.txt3
451041 2211201 19834803 total

v2$ time ./snmp.pl snmp.txt3 > /dev/null

real 0m2.879s
user 0m2.729s
sys 0m0.124s

v2$ time ./snmp.py snmp.txt3 > /dev/null

real 0m5.031s
user 0m4.741s
sys 0m0.249s

v2$ awk --version
GNU Awk 4.0.0

v2$ time ./snmp.awk snmp.txt3 > /dev/null

real 0m6.001s
user 0m5.881s
sys 0m0.093s

v2$ nawk --version
awk version 20070501

v2$ time nawk -f ./snmp.awk snmp.txt2 > /dev/null

real 0m5.213s
user 0m5.101s
sys 0m0.093s

à multiplier par 10 => ~50 sec

allez, pour le fun, la version ksh93 :

# version pattern de base
#!/opt/ast/bin/ksh
integer n
typeset -a a
while IFS= read -r; do
b=${REPLY%%+([0-9]) @(*)}
(( n = ${#b} >> 1 ))
a[n]=${.sh.match[1]}
r=${.sh.match[2]}
[[ $r == *GENERATE* ]] &&
print -r "(${a[@]:1:$n} ) $r"
done < $1

v2$ time ./snmp.ksh snmp.txt2 > /dev/null

real 0m2.144s
user 0m2.090s
sys 0m0.047s

# version pattern façon regexp => c la kata !
#!/opt/ast/bin/ksh
integer n
typeset -a a
while IFS= read -r; do
b=${REPLY%%+([0-9])+( )@(+([! ])*)}
(( n = ${#b} >> 1 ))
a[n]=${.sh.match[1]}
[[ ${.sh.match[4]} == 'GENERATE' ]] &&
print -r "(${a[@]:1:$n} ) ${.sh.match[3]}"
done < $1

v2$ time ./snmp.ksh2 snmp.txt2 >/dev/null

real 0m2.808s
user 0m2.730s
sys 0m0.077s

# version regexp => pareil
#!/opt/ast/bin/ksh
integer n
typeset -a a
while IFS= read -r; do
[[ $REPLY == ~(E)(.*?)([0-9]+)' '+(([^ ]+).*) ]]
(( n = ${#.sh.match[1]} >> 1 ))
a[n]=${.sh.match[2]}
[[ ${.sh.match[4]} == 'GENERATE' ]] &&
print -r "(${a[@]:1:$n} ) ${.sh.match[3]}"
done < $1

v2$ time ./snmp.ksh3 snmp.txt2 > /dev/null

real 0m2.169s
user 0m2.090s
sys 0m0.078s

à multiplier par 10 => ~20 sec

c'est même faisable en ksh88...

#!/usr/local/bin/ksh88
integer n i
while IFS= read -r; do
r=${REPLY%%+([0-9])+( )@(*)}
(( n = ${#r} >> 1 ))
r=${REPLY#$r}
a[n]=${r%% *}
r=${r#+([0-9]) }
if [[ $r == *GENERATE* ]]; then
s= i=0 p=
while (( ( i += 1 ) <= n )); do
s=$s$p${a[i]}
p=' '
done
print -r "($s )$r"
fi
done < $1

v2$ time snmp.ksh88 snmp.txt2 > /dev/null

real 0m6.215s
user 0m6.084s
sys 0m0.139s

j'ai trouvé pire, mais ça, on le savait déjà...
que bash avait des IOs pourries.

tout d'abord, mir-ksh (aka pd-ksh)

v2$ mksh -c 'echo $KSH_VERSION'
@(#)MIRBSD KSH R40 2011/11/22

v2$ time mksh snmp.ksh snmp.txt2 > /dev/null

real 0m23.637s
user 0m9.344s
sys 0m14.195s

à multiplier par 10 => ~240 sec

puis bash :

# version pattern
#!/usr/bin/bash
shopt -s extglob
typeset -i n i
while IFS= read -r; do
r=${REPLY%%+([0-9])+( )@(*)}
(( n = ${#r} >> 1 ))
r=${REPLY#$r}
a[n]=${r%% *}
r=${r#+([0-9]) }
if [[ $r == *GENERATE* ]]; then
s= i=0 p=
while (( ( i += 1 ) <= n )); do
s=$s$p${a[i]}
p=' '
done
echo -E "($s )$r"
fi
done < $1

v2$ bash --version
GNU bash, version 4.1.10(4)-release (i686-pc-cygwin)

v2$ time snmp.bash snmp.txt2 > /dev/null

real 0m39.074s
user 0m24.648s
sys 0m14.288s

à multiplier par 10 => ~390 sec

# version regexp
#!/usr/bin/bash
typeset -i n
typeset -a a
while IFS= read -r; do
[[ $REPLY =~ (.*)([0-9]+)' '+(([^ ]+).*) ]]
(( n = ${#BASH_REMATCH[1]} >> 1 ))
a[n]=${BASH_REMATCH[2]}
[[ ${BASH_REMATCH[4]} == 'GENERATE' ]] &&
echo -E "(${a[@]:1:$n} ) ${BASH_REMATCH[3]}"
done < $1

v2$ time ./snmp.bash2 snmp.txt2 > /dev/null

real 0m52.912s
user 0m32.604s
sys 0m18.673s

à multiplier par 10 => ~520 sec

qui dit mieux...

conclusion :

le pire étant le couple ksh/onetrueawk, bash est hors concour,
perl est 17 fois plus rapide, python 10 fois plus, gawk 8 fois plus,
le ksh93 ne l'est que 2 fois plus environ, mksh est 5 fois plus lent et
bash est 8 à 10 fois plus lent que les plus lent de référence !

Cordialement,

Cyrille Lefevre.
--
mailto:Cyrille.Lefevre-news%
supprimer "%nospam% et ".invalid" pour me repondre.
Damien Wyart
Le #24428011
* Cyrille Lefevre in fr.comp.os.unix:
le pire étant le couple ksh/onetrueawk, bash est hors concour, perl
est 17 fois plus rapide, python 10 fois plus, gawk 8 fois plus, le
ksh93 ne l'est que 2 fois plus environ, mksh est 5 fois plus lent et
bash est 8 à 10 fois plus lent que les plus lent de référence !



Amusant et ça colle assez bien avec différentes comparaisons que l'on
peut trouver sur Internet.

Ceci dit, je ne suis pas sûr que l'on puisse comparer les versions Perl
et Python de ce fil car pour cette dernière, je fais évoluer la liste
des nombres dynamiquement dans les deux sens (augmentation et réduction)
tandis qu'en Perl, elle ne fait qu'augmenter (avec des écrasements
d'éléments) et elle est lue partiellement. Il aurait donc été plus juste
de traduire la version Perl en Python pour réellement les comparer. Même
si la différence d'écart doit être faible...

--
DW
Publicité
Poster une réponse
Anonyme