Représenter un arbre sous forme de liste

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);

Bonjour,

* Olivier Miakinen <om+news@miakinen.net> in fr.comp.os.unix:

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

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

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

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

* Stephane Chazelas <stephane.chazelas@gmail.com> in fr.comp.os.unix:

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

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

Olivier Miakinen <om+news@miakinen.net> écrivait :

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é

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%nospam@laposte.net.invalid
supprimer "%nospam% et ".invalid" pour me repondre.

* Cyrille Lefevre <cyrille.lefevre-news%nospam@laposte.net.invalid>
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