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é

let k = 1
   if k == 1
       println("k=1")
   end
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
let k = rand(1:2)
    if k != 1
        println("k ≠ 1")
    else
        println("k=1")
    end
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.

let k = rand(1:10)
    @show k
    if k == 5
        println("k = 5")
    elseif k > 5
        println("k > 5")
    else 
        println("k < 5")
    end
end

k = 3
k < 5

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
    @show k, n
end

(k, n) = (145, 1)

(145, 1)

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]
 16.006378 seconds (2.54 M allocations: 37.524 GiB, 17.30% gc time, 3.47% 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 A avant la boucle si on cannait sa taille

  • Utiliser un itérateur avec la fonction collect forsque c’est possible

  • Utiliser 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.001748 seconds (169 allocations: 2.144 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.218892 seconds (188.50 k allocations: 11.779 MiB, 99.44% compilation time)

@time let n = 100000
    A = collect(1:n)
    println(last(A,10))
end

[99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000]
  0.001123 seconds (136 allocations: 787.344 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.005138 seconds (142 allocations: 787.562 KiB, 75.52% gc time)

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 = axes(V,1)
        V[:,i] .= x.^(i-1) # calcul vectorisé
    end
end

  0.775452 seconds (2 allocations: 68.668 MiB, 0.38% gc time)

@time let n = 5000
    x = LinRange(0, 1, n)
    V = zeros(n,n)
    for i = axes(V,1)
        V[i,:] .= x.^(i-1) # calcul vectorisé
    end
end

  2.257027 seconds (2 allocations: 190.738 MiB, 0.59% gc time)

@time let n = 5000
    x = LinRange(0, 1, n)
    V = zeros(n,n)
    for j=axes(V,2), i=axes(V,1)
        V[i,j] = x[i]^(j-1) # calcul dévectorisé
    end
end

  1.999436 seconds (3 allocations: 190.738 MiB, 0.64% gc time)

@time let n = 5000
    x = LinRange(0, 1, n)
    V = zeros(n,n)
    for i=axes(V,1), j=axes(V,2)
        V[i,j] = x[i]^(j-1) # calcul dévectorisé
    end
end

  2.472503 seconds (3 allocations: 190.738 MiB, 0.53% gc time)

@time let n = 3000
    x = LinRange(0, 1, n)
    W = [x[i]^(j-1) for j=1:n, i=1:n]
end;  # le ';' permet d'éviter que la matrice W soit affichée

  0.931028 seconds (63.53 k allocations: 71.957 MiB, 4.07% gc time, 5.16% compilation time)

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

  665.432 ms (3 allocations: 68.67 MiB)

@benchmark Z = Vander1(3000)

BenchmarkTools.Trial: 8 samples with 1 evaluation per sample.
 Range (min … max):  663.924 ms … 672.849 ms  ┊ GC (min … max): 0.68% … 0.68%
 Time  (median):     667.708 ms               ┊ GC (median):    0.67%
 Time  (mean ± σ):   668.039 ms ±   3.338 ms  ┊ GC (mean ± σ):  0.67% ± 0.01%

  █     █   █              ██        █                      █ █  
  █▁▁▁▁▁█▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁██▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁█ ▁
  664 ms           Histogram: frequency by time          673 ms <

 Memory estimate: 68.67 MiB, allocs estimate: 3.

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

  671.756 ms (3 allocations: 68.67 MiB)

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

  678.149 ms (3 allocations: 68.67 MiB)

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.