Ubuntu-fr

Zakhar

Re : (résolu)tri des valeurs après plusieurs "for in ... do.. done"

On peut aller encore plus loin avec la force de la programmation ensembliste (technique du pipe) sans que le programme soit énormément plus long.

+ une optimisation en constatant que la boucle interne n'est autre qu'une séquence !

#! /bin/sh

if [ -z "$3" ]; then
	{ seq 1 $1 $(($1*$2)) | xargs -n 1 -P $2 $0 $1 $2 ; } | sort -n | uniq -c
else
	l=$(($1*$2))
	faces=$(seq 1 $l)
	for de1 in $(seq $3 $(($3+$1-1))); do
		for de2 in $faces; do
			seq $(($de1+$de2+1)) $(($de1+$de2+$l))
		done
	done
fi

Le principe est de faire X threads pour calculer tous les "lancers" possible, c'est un shell récursif (il s'appelle lui-même).

Donc si on lance ma précédente version avec 300 (non optimisé avec la boucle interne remplacée par seq) on obtient :

$ /usr/bin/time -v ./test1.sh
(...)
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:55.74
(...)

Maintenant on lance la version avec parallélisme, ça marche ainsi :
-1er paramètre est le "bloc"
-2ème paramètre est le nombre de blocs

Quand le programme se rend compte qu'il n'a "que" 2 paramètres, c'est le programme principal. Il se lance alors lui-même en parallèle, autant de fois qu'il y a de "nombre de blocs" (paramètre 2), en rajoutant un 3ème paramètre est le début du sous-bloc à calculer.
Lancé avec 3 paramètres, c'est là qu'on calcule les lancers. Le premier lancer est un des N sous-blocs (en fonction de l'indice reçu en paramètre 3) et les deux autres lancers sont "complets" à "bloc x nombre de blocs"

Notons que cela fonctionne car les écritures dans un pipe sont atomiques jusqu'à 4096 octets sur Linux, et chaque thread lancé n'écrit que de toutes petites lignes de quelques caractères, largement moins que 4096 !

Donc

$ ./test2.sh 150 2

Va faire 2 "blocs" de 150, ce qui fait bien 300
Voyons ce qu'on gagne avec trois tests:

$ /usr/bin/time -v ./test2.sh 150 2
(...)
Command being timed: "./test2.sh 150 2"
User time (seconds): 45.04
System time (seconds): 7.33
Percent of CPU this job got: 186%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:28.02
(...)

$ /usr/bin/time -v ./test2.sh 75 4
(...)
Command being timed: "./test2.sh 75 4"
User time (seconds): 49.67
System time (seconds): 8.13
Percent of CPU this job got: 270%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:21.39
(...)

$ /usr/bin/time -v ./test2.sh 50 6
(...)
Command being timed: "./test2.sh 50 6"
User time (seconds): 51.04
System time (seconds): 8.18
Percent of CPU this job got: 316%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:18.72
(...)

Temps elapse (temps mis pour faire le calcul) :

• 42.0s (1 process) / 55.7 non optimisé

• 28.0s (2 process)

• 21.4s (4 process)

• 18.7s (6 process)

Bien sûr, cela va dépendre de votre nombre de "cores". Sur une machine mono-core on perd juste du temps en inter-process.
N'oubliez pas non plus qu'il y a déjà un process pour "sort" en parallèle des lancers, donc sur mon Core i7 découper en 6 blocs est déjà bien.
Faites tourner avec le moniteur système en face, vous verrez nettement la différence entre le truc qui tourne avec 6 blocs en parallèle, et le programme d'origine non-récursif.
Enfin ne pas confondre performance et efficacité. Plus il y a de parallélisme, moins c'est "efficace" au sens consommation de ressources car on rajoute de l'overhead inter-process. Pour faire un calcul basique, on multiplie l'elapse par le pourcentage de CPU, ou on ajoute les temps user et system ce qui donne un résultat similaire. On a alors des temps machine respectifs de 52s, 58s et 59s pour les 3 exécutions ci-dessus.

Je vous mets au défi de faire la même technique de parallélisme dynamique aussi simplement avec un tableau externe... même avec bash !

P.S.: mes deux langages préférés sont chacun à un bout du spectre, c'est le C et XSLT. XSLT a aussi un raisonnement "ensembliste" (on applique des "patterns" sur des "sélections" = ensembles) qui est assez déroutant quand on vient de la "programmation impérative" comme le C (avec l'exemple typique "d'effet de bord" de la technique du tableau global).

Avec le shell on peut faire un peu d'ensembliste aussi en jouant avec les "pipe" et c'est vraiment d'une puissance colossale pour gagner du temps, d'autant que les processeurs n'augmentent plus trop en "vitesse brute" mais ont tendance à avoir plusieurs "core" et donc le parallélisme est gagant.

Un exemple, à l'époque où certains forums découpaient les fichiers avec un utilitaire W$ bizarre : xTremSplit, bien sûr non dispo sur Linux (sauf via Wine!) j'avais fait un équivalent Linux en shell... qui allait plus vite que l'orignial W$ pourtant écrit en C... bien sûr pipe power inside avec un astucieux jeux de pipe et tee le shell faisait du parallélisme et économisait plein d'I/O, là où le programme d'origine faisait tout "bêtement" en séquentiel. Et faire ça en shell c'est facile car c'est "natif" : un pipe lance déjà un autre process !

@cristobal78 : eh oui, il y a sans doute un moyen "mathématique" (indiqué dans le livre ?) de calculer le nombre d'occurrences d'une valeur pour un jet de N dés à P faces !..  C'est sans doute plus rapide que d'écrire le programme quand on a la formule.
Par exemple, on peut déjà affirmer de façon triviale que la somme N n'apparaît qu'une fois (les N dés font 1) et la somme N * P de même. Là je me suis pas trop foulé dans le raisonnement mathématique.
J'ai dû étudier ce genre de chose... mais moi aussi, l'école c'était il y a fort longtemps !

Dernière modification par Zakhar (Le 19/10/2020, à 00:32)

---

"A computer is like air conditioning: it becomes useless when you open windows." (Linus Torvald)