La voix du secrétaire (Jean)
Présents à la réunion, en fonction de la l'ordre d'arrivée :
Comme on peut le voir, la quasi totalité des participants venaient de Linkfluence. Et en plus, Nils a tenté (en vain) d'inciter d'autres collègues à venir à la réunion pour mieux marquer la présence de Linkfluence.
Nous avons parlé de Perl, informatique et points divers.
my @resultat = sort { length($b) <=> length($a) } @chaines_a_trier;est mauvaise, il faut répondre avec une transformée Schwartzienne l'intérêt étant qu'ainsi, le calcul de la longueur d'une chaîne est effectué une seule fois pour chaque chaîne, au lieu d'être effectué chaque fois que la chaîne est comparée à une autre. En fait, je pense qu'une solution meilleure consiste à effectuer un tri par distribution. Là aussi, le calcul de la longueur de la chaîne est effectué une seule fois pour chaque chaîne. Et en plus, le tri par distribution est en O(n) et non pas en O(n.log(n)). J'ai donc fait un benchmark entre les différentes méthodes :
#!/usr/bin/perl # # Sorting strings by decreasing length # use strict; use warnings; use Benchmark qw(:all); use Getopt::Long; my ($length, $number, $iterations) = (100, 5000, 5_000); GetOptions ('length=i' => \$length, 'number=i' => \$number, 'iterations=i' => \$iterations) or die "Problem with the options"; my @data; for (1..$number) { push @data, 'x' x rand $length; } print "$iterations iterations sorting $number lines with max length $length\n"; cmpthese($iterations, { distrib1 => sub { distrib1_sort(@data) }, distrib2 => sub { distrib2_sort(@data) }, builtin => sub { built_in_sort(@data) }, Schwartz => sub { schwartzian (@data) }, } ); sub distrib1_sort { my @list_by_length = (); my @result = (); for (@_) { push @{$list_by_length[length $_]}, $_; } # use grep to remove empty slots from the list of lists foreach my $list_ref (reverse grep { $_ } @list_by_length) { push @result, @$list_ref; } return @result; } sub distrib2_sort { my @list_by_length = (); my @result = (); for (@_) { push @{$list_by_length[length $_]}, $_; } # use grep to remove empty slots from the list of lists foreach my $list_ref (reverse grep { $_ } @list_by_length) { while (@$list_ref) { push @result, shift @$list_ref; } } return @result; } sub schwartzian { return map { $_->[0] } sort { $b->[1] <=> $a->[1] } map { [ $_, length $_ ] } @_; } sub built_in_sort { return sort { length($b) <=> length($a) } @_; } exit(0);
5000 iterations sorting 5000 lines with max length 100
(warning: too few iterations for a reliable count)
Rate Schwartz distrib2 distrib1 builtin
Schwartz 18.3/s -- -75% -77% -100%
distrib2 72.6/s 296% -- -7% -100%
distrib1 78.0/s 326% 7% -- -100%
builtin 26316/s 143426% 36147% 33621% --
Curieusement, la méthode élémentaire sans transformée schwartzienne
est nettement plus rapide que les deux autres, de plusieurs ordres
de grandeur. Et comme je m'y attendais, le tri par distribution
est plus rapide que le tri normal avec transformée schwartzienne,
pour peu que le nombre d'enregistrements dépasse un seuil relativement
faible, peut-être dans les 100 enregistrements.
Nils explique qu'il n'est pas supris de voir les résultats du
tri élémentaire. Le calcul de la longueur d'une chaîne est très
rapide, car cette longueur est stockée dans les attributs
de la variable. Donc, il ne faut pas s'étonner que
length($x) pour une variable contenant une chaîne
de caractères soit plus rapide que $x->[1]
pour une variable contenant une référence de tableau.
Nils trouve de plus que la transformée schwartzienne n'est
pas lisible. Je trouve que si, une fois que l'on connaît
les constructions idiomatiques de Perl, la transformée schwartzienne
est lisible. Lorsque je vois un map sort map,
je reconnais tout de suite une transformée schwartzienne.
Il ne faut pas oublier, ajoute Nils, qu'un algorithme
en O(n2) peut se révéler plus rapide qu'un algorithme
en O(n.log(n)), si le nombre réel d'enregistrements n'est pas
trop grand et si les itérations de l'algorithme quadratique
sont simples tandis que celles de l'algorithme O(n.log(n))
sont compliquées.
for 1, 3, 5 ... * { say $_ }imprimera la suite des entiers impairs, tandis que
for 1, 2, 4 ... * { say $_ }imprimera la suite des puissances de 2. Nils a lu un livre sur les algorithmes génétiques, qui permettent d'extrapoler de telles suites. À ce propos, je propose une suite de nombres qui, je pense, ne peut pas être étendue par l'opérateur whatever de Perl 6. Que doit donner le script suivant ?
for 4, 1e12, 5, 2, 0, ... * { say $_ }Je ne sais pas si Perl6 pourra interprêter le 1012. Quant à vous, essayez de deviner... [ Et vous qui étiez présents le 11 août, ou bien à la réunion technique du 1er septembre, ne soufflez pas aux copains ! ]
chmod -x chmodVous n'avez pas accès à Internet. Comment faites-vous pour réparer votre système ? José apporte plusieurs réponses, dont une qui a beaucoup plu à Nils. Ainsi que l'a exprimé José, cette solution consiste à utiliser un autre système d'exploitation qui a accès au répertoire /bin. Si vous pensez à Windows ou à une solution faisant intervenir Xen, vous avez tout faux. La solution de José consiste à lancer Emacs à demander le répertoire /bin en mode Dired, puis à changer les attributs de chmod par Dired.
If it ain't broke, don't fix it(ou « si c'est pas cassé, faut pas réparer »), les programmes qui fonctionnent aujourd'hui ce sont toujours les mêmes programmes qui fonctionnaient à l'origine, c'est-à-dire des programmes en COBOL. Dans certains cas, c'est cassé quand même, mais comme il s'agit d'une édition sans mise à jour de la base de données et comme personne ne demande le résultat de cette édition, la solution consiste tout simplement à supprimer le résultat. Jusqu'au jour où, après plusieurs années de désintérêt, un manager pressé demande qu'on lui livre cette édition. Cela a été difficile de lui faire admettre que cela faisait longtemps que l'édition ne fonctionnait plus et qu'elle allait directement à la poubelle.
Cela fait déjà presque un mois que je t'ai demandé de faire l'édition 14Z et je n'ai toujours rien vu ! Tu vas te décider à la faire, hein ?
for my $n (0..1e22)La limite supérieure 1022 correspond au moment où les nombres entiers commencent à perdre leur précision pour Lingua::FR::Numbers et peut-être aussi pour Perl. Mais même si la consommation mémoire est raisonnable avec une liste en lazy evaluation, le temps consacré au calcul l'est beaucoup moins. Et en fait, à partir de 100, on a juste besoin d'examiner les puissances de 10. D'où une optimisation sur la boucle.
#!/usr/bin/perl
use strict;
use warnings;
use feature ':5.10';
use Lingua::FR::Numbers qw(number_to_fr);
my %table;
# Hé les contempteurs des boucles C ! Essayez donc de faire
# une boucle qui commence avec une progression arithmétique
# et qui se poursuit avec une progression géométrique !
# En concentrant la logique de boucle sur une seule ligne
# ou sur un nombre restreint de lignes *consécutives*.
# Ou avec une liste en *lazy evaluation*.
for (my $n = 0; $n <= 1e22; $n < 100 ? ($n++) : ($n *= 10)) {
my $ch = Lingua::FR::Numbers::number_to_fr($n);
$ch =~ tr/eE/ee/;
for (split '', $ch) {
$table{$_} //= $n;
}
}
for ('a'..'z') {
say $table{$_} // 'undef';
}