Think Julia

Nous avons vu que certains algorithmes sont plus performants que d'autres. La fonction fibonacci en section 11.6Mémos (Mémos) est beaucoup plus rapide que fib écrite en section 6.7Un exemple supplémentaire. La macro @time permet de quantifier la différence :

julia> fib(1)
1 
julia> fibonacci(1)
1 
julia> @time fib(40)
0.567546 seconds (5 allocations: 176 bytes) 
102334155 
julia> @time fibonacci(40) 
0.000012 seconds (8 allocations: 1.547 KiB) 
102334155

@time affiche le temps d'exécution de la fonction, le nombre d'allocations et la mémoire allouée avant de retourner le résultat. La version « mémo » est effectivement beaucoup plus rapide, mais elle requiert davantage de mémoire.

« Rien n'est gratuit ».

Dans la section 13.6Soustraction de dictionnaires (Soustraction de dictionnaires), des dictionnaires ont été utilisés pour trouver les mots qui apparaissent dans un document, mais pas dans un tableau de mots. La fonction que nous avons écrite prend d1 contenant les mots du document comme clés et d2 qui renferme le tableau de mots. Elle retourne un dictionnaire qui contient les clés de d1 absentes dans d2.

function subtract(d1, d2)
    res = Dict() 
    for key in keys(d1)
        if key ∉ keys(d2)
            res[key] = nothing
        end
    end 
    res
end

Dans tous ces dictionnaires, les valeurs sont nothing parce qu'elles ne sont jamais utilisées. Par conséquent, nous gaspillons un peu d'espace de stockage.

Julia propose un autre type interne appelé « ensemble ». Ce type se comporte comme un ensemble de clés de dictionnaire sans valeurs. L'ajout d'éléments à un ensemble est rapide, tout comme la vérification d'appartenance à un ensemble. Les ensembles fournissent des fonctions et des opérateurs pour y effectuer des opérations courantes.

Par exemple, la soustraction d'un ensemble est disponible sous la forme d'une fonction appelée setdiff. Nous pouvons donc réécrire la soustraction comme suit :

function subtract(d1, d2)
    setdiff(d1, d2)
end

Le résultat est un ensemble au lieu d'un dictionnaire.

Certains des exercices de ce livre peuvent être réécrits de manière concise et efficace avec des ensembles. Par exemple, voici une solution pour hasduplicates, de l'exercice 10.15.7Exercice 10-7 qui utilise un dictionnaire :

function hasduplicates(t)
    d = Dict() 
    for x in t
        if x ∈ d
            return true 
        end 
        d[x] = nothing 
    end 
    false
end

Lorsqu'un élément apparaît pour la première fois, il est ajouté au dictionnaire. Si le même élément apparaît à nouveau, la fonction retourne true.

En utilisant des ensembles, la même fonction peut être réécrite comme ceci :

function hasduplicates(t)
    length(Set(t)) < length(t)
end

Un élément ne peut apparaître qu'une seule fois dans un ensemble. Ainsi, si un élément apparaît plus d'une fois dans t, l'ensemble sera plus petit que t. S'il n'y a pas de répétitions d'élément, l'ensemble aura la même taille que t.

Nous pouvons également utiliser des ensembles pour faire certains des exercices du chapitre 9Étude de cas : jeux de mots. Par exemple, voici une version d'usesonly (section 9.3Recherche) avec une boucle :

function usesonly(word, available)
    for letter in word
        if letter ∉ available
            return false
        end
    end
    true
end

usesonly vérifie si toutes les lettres contenues dans word se trouvent dans available. Cette fonction peut être réécrite ainsi :

function usesonly(word, available)
    Set(word) ⊆ Set(available)
end

L'opérateur kitxmlcodeinlinelatexdvp\subseteqfinkitxmlcodeinlinelatexdvp (\subseteq TAB) vérifie si un ensemble est inclus dans un autre, en ce compris la possibilité qu'ils soient égaux. Dans ce dernier cas, cela signifie que toutes les lettres de word apparaissent dans available.

20-2-1. Exercice 20-1▲

Les nombres complexes sont pris en charge par Julia. La constante globale im est liée au nombre complexe i (avec kitxmlcodeinlinelatexdvp\mathrm{i}^{2}=-1finkitxmlcodeinlinelatexdvp).

L'identité d'Euler est vérifiable :

julia> e^(im*𝜋)+1
0.0 + 1.2246467991473532e-16im

Le symbole kitxmlcodeinlinelatexdvpefinkitxmlcodeinlinelatexdvp (\euler TAB) est la base des logarithmes naturels.

Illustrons le caractère complexe des fonctions trigonométriques :

Nous pouvons tester cette formule pour différentes valeurs de x.

julia> x = 0:0.1:2𝜋
0.0:0.1:6.2
julia> cos.(x) == 0.5*(e.^(im*x)+e.^(-im*x))
true

Ceci est un autre exemple d'application de l'opérateur « point ». Julia permet également de juxtaposer des constantes numériques avec des identificateurs sous forme de coefficients comme dans 2π.

Dans les chapitres 8Chaînes et 9Étude de cas : jeux de mots, nous avons mené quelques recherches élémentaires dans les objets de type String. Cependant, Julia gère des expressions rationnelles compatibles avec le langage Perl. Ceci facilite la recherche de motifs complexes dans les chaînes de caractères.

La fonction usesonly peut être mise en œuvre comme une expression rationnelle :

function usesonly(word, available)
    r = Regex("[^$(available)]")
    !occursin(r, word)
end

L'expression régulière recherche un caractère qui n'est pas dans la chaîne available et occursin retourne true si le motif est trouvé dans le mot.

julia> usesonly("bonbon", "bno")
true
julia> usesonly("bonbons", "bno")
false

Les expressions rationnelles peuvent également être construites comme des chaînes de caractères non normalisées préfixées par un r :

julia> match(r"[^bno]", "bonbon")

julia> m = match(r"[^bno]", "bonbons")
RegexMatch("s")

Dans ce cas, l'interpolation de chaînes n'est pas autorisée. La fonction match ne retourne rien si le motif (une commande) n'est pas trouvé et retourne un objet RegexMatch dans le cas contraire.

Nous pouvons extraire les informations suivantes d'un objet RegexMatch :

• la sous-chaîne entière correspondant : m.match ;
• les sous-chaînes capturées comme un tableau de chaînes de caractères : m.captures ;
• le décalage auquel commence l'ensemble de la correspondance : m.offset ;
• les décalages des sous-chaînes capturées sous la forme d'un tableau : m.offsets.

julia> m.match
"s"
julia> m.offset
7

Les expressions rationnelles constituent un outil très puissant. La page de manuel de Perl fournit tous les détails pour mener à bien des recherches très poussées, voire sophistiquées.

Dans le chapitre 10Tableaux, nous avons utilisé l'objet Array (tableau) comme conteneur unidimensionnel avec des indices permettant de retrouver ses éléments. Julia manipule aussi les tableaux multidimensionnels.

Créons une matrice de 2 par 3 contenant des zéros :

julia> z = zeros(Float64, 2, 3)
2×3 Array{Float64,2}:
 0.0 0.0 0.0
 0.0 0.0 0.0
julia> typeof(z)
Array{Float64,2}

Le type de cette matrice est un tableau à deux dimensions contenant des nombres à virgule flottante.

La fonction size renvoie un tuple décrivant le nombre d'éléments dans chaque dimension :

julia> size(z)
(2, 3)

La fonction ones construit une matrice avec des éléments de valeur 1 :

julia> s = ones(String, 1, 3)
1×3 Array{String,2}:
""   ""   ""

L'élément unitaire de chaîne de caractères est une chaîne vide, "".

julia> s == ["", "", ""]
false

Une matrice peut être saisie directement en utilisant un espace pour séparer les éléments d'une ligne et un point-virgule ; pour séparer les lignes :

julia> a = [1 2 3; 4 5 6]
2×3 Array{Int64,2}:
 1 2 3
 4 5 6

Pour traiter des éléments individuels, des crochets sont utilisables :

julia> z[1,2] = 1
1
julia> z[2,3] = 1
1
julia> z
2×3 Array{Float64,2}:
 0.0 1.0 0.0
 0.0 0.0 1.0

La sélection d'un sous-groupe d'éléments peut être réalisée par segmentation :

julia> u = z[:,2:end]
2×2 Array{Float64,2}:
 1.0 0.0
 0.0 1.0

L'opérateur . effectue une distribution sur chaque élément dans toutes les dimensions :

julia> e.^(im*u)
2×2 Array{Complex{Float64},2}:
 0.540302+0.841471im            1.0+0.0im
           1.0+0.0im            0.540302+0.841471im

Julia tire parti de certaines interfaces informelles pour définir des comportements, c'est-à-dire des méthodes ayant un objectif spécifique. Lorsque ces méthodes sont étendues à un type, des objets de ce type peuvent être utilisés pour construire ces comportements.

« Si ça ressemble à un canard, si ça nage comme un canard et si ça cancane comme un canard, c'est un canard. »

Dans la section 6.7Un exemple supplémentaire, nous avons mis en œuvre la fonction fib qui retourne le n^ième élément de la suite de Fibonacci. La recherche des valeurs d'une suite constitue une de ces interfaces. Créons un itérateur qui retourne la suite de Fibonacci :

struct Fibonacci{T<:Real} end
Fibonacci(d::DataType) = d<:Real ? Fibonacci{d}() : error("No Real type!")

Base.iterate(::Fibonacci{T}) where {T<:Real} = (zero(T), (one(T), one(T)))
Base.iterate(::Fibonacci{T}, state::Tuple{T, T}) where {T<:Real} = (state[1], (state[2], state[1] + state[2]))

Nous avons mis en œuvre un type paramétrique sans champ Fibonacci, un constructeur extérieur et deux méthodes iterate. La première est appelée pour initialiser l'itérateur et retourne un tuple composé de la première valeur (0) et d'un état. L'état est un tuple contenant la deuxième et la troisième valeur : 1 et 1.

La seconde itération est appelée pour obtenir la valeur suivante de la séquence de Fibonacci et retourne un tuple avec comme premier élément la valeur suivante et comme second élément un état qui consiste en un tuple avec les deux valeurs suivantes.

À ce stade, nous pouvons appeler Fibonacci dans une boucle for :

julia> for e in Fibonacci(Int64)
           e > 100 && break 
           print(e, " ") 
       end 
0 1 1 2 3 5 8 13 21 34 55 89

Cela semble magique, mais l'explication est simple. Une boucle for en Julia :

for i in iter
    # corps de la boucle
end

est convertie en :

next = iterate(iter)
while next !== nothing
    (i, state) = next
    # corps de la boucle
    next = iterate(iter, state)
end

C'est là un très bon exemple de la façon dont une interface bien conçue permet à une implémentation d'utiliser toutes les fonctions disponibles via cette interface.

Nous avons déjà rencontré le module InteractiveUtils dans la section 18.10Débogage. La macro @which n'est que la partie émergée de l'iceberg.

Le code Julia est transformé par la bibliothèque LLVM (Low Level Virtual Machine) en code machine en plusieurs étapes. Nous pouvons directement visualiser la sortie de chaque étape.

Donnons un exemple simple :

function squaresum(a::Float64, b::Float64)
    a^2 + b^2
end

La première étape consiste à examiner le code de bas niveau :

julia> using InteractiveUtils

julia> @code_lowered squaresum(3.0, 4.0) 
CodeInfo(
1 ─ %1 = (Core.apply_type)(Base.Val, 2) 
│ %2 = (%1)() 
│ %3 = (Base.literal_pow)(:^, a, %2) 
│ %4 = (Core.apply_type)(Base.Val, 2) 
│ %5 = (%4)() 
│ %6 = (Base.literal_pow)(:^, b, %5) 
│ %7 = %3 + %6 
└──     return %7 
)

La macro @code_lowered retourne sous forme d'un tableau une représentation intermédiaire du code utilisé par le compilateur pour produire du code optimisé.

L'étape suivante ajoute des informations sur le type :

julia> @code_typed squaresum(3.0, 4.0) 
CodeInfo( 
1─ %1 = (Base.mul_float)(a, a)::Float64 
│ %2 = (Base.mul_float)(b, b)::Float64
│ %3 = (Base.add_float)(%1, %2)::Float64
└──     return %3 ) => Float64

Nous observons que le type de résultats intermédiaires et la valeur de retour sont correctement déduits.

Cette représentation du code est transformée en code LLVM :

julia> @code_llvm squaresum(3.0, 4.0) 
; @ none:2 within `squaresum'
define double @julia_squaresum_14821(double, double) {
top:
; ┌ @ intfuncs.jl:243 within `literal_pow'
; │┌ @ float.jl:399 within `*'
       %2 = fmul double %0, %0 
       %3 = fmul double %1, %1 
; └└ 
; ┌ @ float.jl:395 within `+'
       %4 = fadd double %2, %3 
; └ 
   ret double %4 
}

Finalement, le code machine est produit :

julia> @code_native squaresum(3.0, 4.0)
                .section __TEXT,__text,regular,pure_instructions
; ┌ @ none:2 within `squaresum'
; │┌ @ intfuncs.jl:243 within `literal_pow'
; ││┌ @ none:2 within `*'
            vmulsd %xmm0, %xmm0, %xmm0 
            vmulsd %xmm1, %xmm1, %xmm1 
; │└└ 
; │┌ @ float.jl:395 within `+'
            vaddsd %xmm1, %xmm0, %xmm0 
; │└ retl 
        nopl      (%eax) 
; └

Les macros Logging fournissent un substitut aux canevas avec des déclarations d'affichage :

julia> @warn "Abandon printf debugging, all ye who enter here!"
┌ Warning: Abandon printf debugging, all ye who enter here!
└ @ Main REPL[1]:1

Les déclarations de débogage ne doivent pas être retirées du code. Par exemple, contrairement à @warn ci-dessus, le code :

julia> @debug "The sum of some values $(sum(rand(100)))"

ne produira, par défaut, aucun résultat. Dans ce cas, sum(rand(100)) ne sera jamais évaluée à moins que la journalisation du débogage ne soit activée.

Le niveau de journalisation peut être sélectionné par une variable d'environnement JULIA_DEBUG :

$ JULIA_DEBUG=all julia -e '@debug "The sum of some values $(sum(rand(100)))"'
┌ Debug: The sum of some values 47.116520814555024 
└ @ Main none:1

En l'occurrence, nous avons utilisé all pour extraire toutes les informations de débogage. Cependant, il est possible de ne produire que les informations associées à un fichier ou à un module spécifique.

regex expression rationnelle, une séquence de caractères qui définit un modèle de recherche.

matrice tableau à deux dimensions.

représentation intermédiaire structure de données utilisée en interne par un compilateur pour représenter le code source.

code machine instructions qui peuvent être exécutées directement par l'unité centrale d'un ordinateur.

enregistrement de débogage stockage des messages de débogage dans un journal.