Eléments de programmation#
Pour mener à bien un calcul algorithmique le nombre d’éléments de langage n’est pas très important et peut se résumer aux 3 syntaxes suivantes
Le choix conditionnel if-elseif-else-end.
La boucle for-end.
La boucle while-end
if … elseif … else … end#
Un choix simple si le test est vrai (k==1) alors le bloc d’instruction est évalué
k = 1
if k == 1
println("k=1")
end
k=1
en Julia une autre syntaxe est possible avec
k == 1 && println("k=1")
k=1
Le else permet de donner un résultat par défaut…
using Random
k = rand(1:2)
if k != 1
println("k ≠ 1")
else
println("k=1")
end
k ≠ 1
Une succession de elseif permet de choisir parmi plusieurs critères, dans la succession des blocs de if et elseif le premier qui est “vrai” est évaluer et l’instruction s’arrète.
@show k = rand(1:3)
if k==1
println("k=1")
elseif k>1
println("k>1")
else
println("k<1")
end
k = rand(1:3) = 1
k=1
La boucle for#
Elle peut se définir à l’aide d’itérateurs ou de tableaux de valeurs les syntaxes “=” , “in” ou “\(\in\)” sont équivalentes
for i = 1:10
println(i)
end
1
2
3
4
5
6
7
8
9
10
for i in ["un" 2 im]
println(typeof(i))
end
String
Int64
Complex{Bool}
typeof.(["un", 2, im])
3-element Vector{DataType}:
String
Int64
Complex{Bool}
eltype(["un" 2 im])
Any
La commande break permet de sortir d’une boucle à tout moment
for i = 1:1000
println(i)
if i >= 5
break
end
end
1
2
3
4
5
La commande continue permet elle de courtcircuiter la boucle en court et de passer à la valeur suivante
for i = 1:10
if i % 3 != 0 # i modulo 3 different de 0
continue
end
println(i)
end
3
6
9
La boucle while#
Tant que le test est “vrai” le bloc est évalué, le test se faisant en entrée de bloc
k = 0
while k<10
k += 1 # k=k+1
println(k)
end
1
2
3
4
5
6
7
8
9
10
De même que la boucle for les commandes break et continue sont valables …
k=0
while k < 1000
k += 1 # k=k+1
if k % 5 != 0 # k modulo 5 diffèrent de 0
continue # retour en début de boucle avec de nouveau un test sur k
end
println(k)
if k > 30
break
end
end
5
10
15
20
25
30
35
let
n = 10000000
k = 0
while n > 1
if n % 2 == 0
n = n ÷ 2
else
n = 3n+1
end
k += 1
end
println(n)
println("k \t = \t $k")
end
1
k = 145
Un peu d’optimisation#
Julia est dit un langage performant, regardons rapidement quelques exemples à faire ou ne pas faire.
Exemple de préallocation et utilisation de push!#
@time let n = 100000
A = zeros(0) # Tableau vide qui contiendra des Float64
for i = 1:n
A = [A; i] # a chaque itération on change la taille de A
end
println(last(A,10))
end
[99991.0, 99992.0, 99993.0, 99994.0, 99995.0, 99996.0, 99997.0, 99998.0, 99999.0, 100000.0]
7.581140 seconds (323.98 k allocations: 37.270 GiB, 8.10% gc time, 2.01% compilation time)
Cet exemple montre le coût prohibitif d’une réallocation dynamique qui impose une recopie totale de A à chaque itération. Il faut donc récrire notre code différemment pour réduire cet utilisation excessive du ramasse miettes. Heureusement plusieurs solutions s’offrent à vous
Utiliser la fonction
push!Allouer le tableau
Aavant la boucle si on cannait sa tailleUtiliser un itérateur avec la fonction
collectforsque c’est possibleUtiliser la comprehension
@time let n = 100000
A = zeros(0)
for i = 1:n
push!(A,i) # a chaque itération on change la taille de A
end
println(last(A,10))
end
[99991.0, 99992.0, 99993.0, 99994.0, 99995.0, 99996.0, 99997.0, 99998.0, 99999.0, 100000.0]
0.001357 seconds (324 allocations: 1.838 MiB)
@time let n = 100000
A = zeros(Int64,n)
for i in eachindex(A)
A[i] = i
end
println(last(A,10))
end
[99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000]
0.000547 seconds (304 allocations: 788.203 KiB)
@time let n = 100000
A = collect(1:n)
println(last(A,10))
end
[99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000]
0.000448 seconds (304 allocations: 788.203 KiB)
@time let n = 100000
A = [i for i=1:n]
println(last(A,10))
end
[99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000]
0.000474 seconds (304 allocations: 788.203 KiB)
Exemple de vectorisation#
Regardons la vectorisation sous Julia à l’aide de la construction d’une matrice de Vandermonde
@time let n = 3000
x = LinRange(0, 1, n)
V = zeros(n,n)
for i = 1:n
V[:,i] .= x.^(i-1) # calcul vectorisé
end
end
0.357312 seconds (2 allocations: 68.665 MiB, 2.94% gc time)
@time let n = 3000
x = LinRange(0, 1, n)
V = zeros(n,n)
for j=1:n, i=1:n
V[i,j] = x[i]^(j-1) # calcul dévectorisé
end
end
0.346809 seconds (2 allocations: 68.665 MiB)
@time let n = 3000
x = LinRange(0, 1, n)
W = [x[i]^(j-1) for j=1:n, i=1:n]
end
0.580601 seconds (31.26 k allocations: 70.847 MiB, 4.73% compilation time)
3000×3000 Matrix{Float64}:
1.0 1.0 1.0 … 1.0 1.0 1.0 1.0
0.0 0.000333444 0.000666889 0.999 0.999333 0.999667 1.0
0.0 1.11185e-7 4.44741e-7 0.998 0.998667 0.999333 1.0
0.0 3.70741e-11 2.96593e-10 0.997002 0.998001 0.999 1.0
0.0 1.23622e-14 1.97794e-13 0.996005 0.997335 0.998667 1.0
0.0 4.12209e-18 1.31907e-16 … 0.995008 0.99667 0.998334 1.0
0.0 1.37449e-21 8.79673e-20 0.994013 0.996005 0.998001 1.0
0.0 4.58316e-25 5.86644e-23 0.993019 0.995341 0.997668 1.0
0.0 1.52823e-28 3.91226e-26 0.992025 0.994677 0.997336 1.0
0.0 5.09579e-32 2.60905e-29 0.991033 0.994014 0.997003 1.0
0.0 1.69916e-35 1.73994e-32 … 0.990042 0.993351 0.996671 1.0
0.0 5.66577e-39 1.16035e-35 0.989051 0.992689 0.996338 1.0
0.0 1.88922e-42 7.73824e-39 0.988062 0.992027 0.996006 1.0
⋮ ⋱
0.0 0.0 0.0 0.0502627 0.136241 0.36917 1.0
0.0 0.0 0.0 0.0502124 0.13615 0.369047 1.0
0.0 0.0 0.0 … 0.0501622 0.136059 0.368924 1.0
0.0 0.0 0.0 0.050112 0.135969 0.368801 1.0
0.0 0.0 0.0 0.0500619 0.135878 0.368678 1.0
0.0 0.0 0.0 0.0500118 0.135787 0.368555 1.0
0.0 0.0 0.0 0.0499618 0.135697 0.368432 1.0
0.0 0.0 0.0 … 0.0499118 0.135606 0.368309 1.0
0.0 0.0 0.0 0.0498619 0.135516 0.368186 1.0
0.0 0.0 0.0 0.049812 0.135426 0.368064 1.0
0.0 0.0 0.0 0.0497621 0.135335 0.367941 1.0
0.0 0.0 0.0 0.0497124 0.135245 0.367818 1.0
Pour obtenir de meilleures performances il faut le plus souvent possible écrire des fonctions.
using BenchmarkTools
function Vander1(n)
x = LinRange(0, 1, n)
V = zeros(n, n)
for i=1:n
V[:,i] .= x.^(i-1)
end
return V
end
@btime Z = Vander1(3000)
358.726 ms (2 allocations: 68.66 MiB)
3000×3000 Matrix{Float64}:
1.0 0.0 0.0 0.0 … 0.0 0.0
1.0 0.000333444 1.11185e-7 3.70741e-11 0.0 0.0
1.0 0.000666889 4.44741e-7 2.96593e-10 0.0 0.0
1.0 0.00100033 1.00067e-6 1.001e-9 0.0 0.0
1.0 0.00133378 1.77896e-6 2.37274e-9 0.0 0.0
1.0 0.00166722 2.77963e-6 4.63426e-9 … 0.0 0.0
1.0 0.00200067 4.00267e-6 8.00801e-9 0.0 0.0
1.0 0.00233411 5.44808e-6 1.27164e-8 0.0 0.0
1.0 0.00266756 7.11585e-6 1.89819e-8 0.0 0.0
1.0 0.003001 9.006e-6 2.7027e-8 0.0 0.0
1.0 0.00333444 1.11185e-5 3.70741e-8 … 0.0 0.0
1.0 0.00366789 1.34534e-5 4.93456e-8 0.0 0.0
1.0 0.00400133 1.60107e-5 6.4064e-8 0.0 0.0
⋮ ⋱
1.0 0.996332 0.992678 0.989037 1.64276e-5 1.63673e-5
1.0 0.996666 0.993342 0.99003 4.4797e-5 4.46476e-5
1.0 0.996999 0.994007 0.991024 … 0.000122118 0.000121751
1.0 0.997332 0.994672 0.992019 0.000332784 0.000331896
1.0 0.997666 0.995337 0.993014 0.000906567 0.000904451
1.0 0.997999 0.996003 0.99401 0.00246884 0.0024639
1.0 0.998333 0.996668 0.995007 0.0067211 0.00670989
1.0 0.998666 0.997334 0.996004 … 0.0182912 0.0182668
1.0 0.999 0.998 0.997002 0.0497621 0.0497124
1.0 0.999333 0.998667 0.998001 0.135335 0.135245
1.0 0.999667 0.999333 0.999 0.367941 0.367818
1.0 1.0 1.0 1.0 1.0 1.0
function Vander2(n)
x = LinRange(0, 1, n)
V = zeros(n, n)
for j=1:n, i=1:n
V[i,j]=x[i]^(j-1) # calcul dévectorisé
end
return V
end
@btime Z = Vander2(3000)
360.145 ms (2 allocations: 68.66 MiB)
3000×3000 Matrix{Float64}:
1.0 0.0 0.0 0.0 … 0.0 0.0
1.0 0.000333444 1.11185e-7 3.70741e-11 0.0 0.0
1.0 0.000666889 4.44741e-7 2.96593e-10 0.0 0.0
1.0 0.00100033 1.00067e-6 1.001e-9 0.0 0.0
1.0 0.00133378 1.77896e-6 2.37274e-9 0.0 0.0
1.0 0.00166722 2.77963e-6 4.63426e-9 … 0.0 0.0
1.0 0.00200067 4.00267e-6 8.00801e-9 0.0 0.0
1.0 0.00233411 5.44808e-6 1.27164e-8 0.0 0.0
1.0 0.00266756 7.11585e-6 1.89819e-8 0.0 0.0
1.0 0.003001 9.006e-6 2.7027e-8 0.0 0.0
1.0 0.00333444 1.11185e-5 3.70741e-8 … 0.0 0.0
1.0 0.00366789 1.34534e-5 4.93456e-8 0.0 0.0
1.0 0.00400133 1.60107e-5 6.4064e-8 0.0 0.0
⋮ ⋱
1.0 0.996332 0.992678 0.989037 1.64276e-5 1.63673e-5
1.0 0.996666 0.993342 0.99003 4.4797e-5 4.46476e-5
1.0 0.996999 0.994007 0.991024 … 0.000122118 0.000121751
1.0 0.997332 0.994672 0.992019 0.000332784 0.000331896
1.0 0.997666 0.995337 0.993014 0.000906567 0.000904451
1.0 0.997999 0.996003 0.99401 0.00246884 0.0024639
1.0 0.998333 0.996668 0.995007 0.0067211 0.00670989
1.0 0.998666 0.997334 0.996004 … 0.0182912 0.0182668
1.0 0.999 0.998 0.997002 0.0497621 0.0497124
1.0 0.999333 0.998667 0.998001 0.135335 0.135245
1.0 0.999667 0.999333 0.999 0.367941 0.367818
1.0 1.0 1.0 1.0 1.0 1.0
function Vander3(n)
x = LinRange(0, 1, n)
return [x[i]^(j-1) for i=1:n, j=1:n]
end
@btime Z=Vander3(3000)
406.121 ms (2 allocations: 68.66 MiB)
3000×3000 Matrix{Float64}:
1.0 0.0 0.0 0.0 … 0.0 0.0
1.0 0.000333444 1.11185e-7 3.70741e-11 0.0 0.0
1.0 0.000666889 4.44741e-7 2.96593e-10 0.0 0.0
1.0 0.00100033 1.00067e-6 1.001e-9 0.0 0.0
1.0 0.00133378 1.77896e-6 2.37274e-9 0.0 0.0
1.0 0.00166722 2.77963e-6 4.63426e-9 … 0.0 0.0
1.0 0.00200067 4.00267e-6 8.00801e-9 0.0 0.0
1.0 0.00233411 5.44808e-6 1.27164e-8 0.0 0.0
1.0 0.00266756 7.11585e-6 1.89819e-8 0.0 0.0
1.0 0.003001 9.006e-6 2.7027e-8 0.0 0.0
1.0 0.00333444 1.11185e-5 3.70741e-8 … 0.0 0.0
1.0 0.00366789 1.34534e-5 4.93456e-8 0.0 0.0
1.0 0.00400133 1.60107e-5 6.4064e-8 0.0 0.0
⋮ ⋱
1.0 0.996332 0.992678 0.989037 1.64276e-5 1.63673e-5
1.0 0.996666 0.993342 0.99003 4.4797e-5 4.46476e-5
1.0 0.996999 0.994007 0.991024 … 0.000122118 0.000121751
1.0 0.997332 0.994672 0.992019 0.000332784 0.000331896
1.0 0.997666 0.995337 0.993014 0.000906567 0.000904451
1.0 0.997999 0.996003 0.99401 0.00246884 0.0024639
1.0 0.998333 0.996668 0.995007 0.0067211 0.00670989
1.0 0.998666 0.997334 0.996004 … 0.0182912 0.0182668
1.0 0.999 0.998 0.997002 0.0497621 0.0497124
1.0 0.999333 0.998667 0.998001 0.135335 0.135245
1.0 0.999667 0.999333 0.999 0.367941 0.367818
1.0 1.0 1.0 1.0 1.0 1.0
La conclusion n’est pas toujours évidente a priori… Néanmoins on peut voir que le fait de mettre le code dans une fonction impose une optimisation à la compilation et une contextualisation du type et que l’écriture explicite des boucles donne un meilleur résultat.