Algorithmes et structures de données en Go : guide pratique

Algorithmes et structures de données en Go : de la théorie à la pratique

Go (Golang) est un langage compilé moderne qui allie les performances du C et la simplicité de Python. Cependant, pour écrire du code efficace en Go, connaître la syntaxe ne suffit pas. La compréhension des algorithmes et des structures de données est la clé pour créer des applications rapides et évolutives. Dans cet article, nous aborderons trois sujets fondamentaux : la recherche binaire, les tables de hachage et le tri, avec des exemples de code concrets en Go.

1. Recherche binaire : vitesse et précision

La recherche binaire est un algorithme classique pour trouver un élément dans un tableau trié. Au lieu d'un parcours linéaire (O(n)), elle réduit l'espace de recherche de moitié à chaque étape, fonctionnant en O(log n). En Go, cela est particulièrement pertinent pour travailler avec de grands slices.

Implémentation en Go :

package main

import "fmt"

// BinarySearch retourne l'index de l'élément s'il est trouvé, sinon -1func BinarySearch(arr []int, target int) int {    left, right := 0, len(arr)-1

    for left <= right {        mid := left + (right-left)/2 // protection contre le débordement

        if arr[mid] == target {            return mid        } else if arr[mid] < target {            left = mid + 1        } else {            right = mid - 1        }    }    return -1}

func main() {    data := []int{2, 5, 8, 12, 16, 23, 38, 45, 56, 72}    target := 23    index := BinarySearch(data, target)    fmt.Printf("Index de l'élément %d : %d", target, index) // Affiche : Index de l'élément 23 : 5}

Conseils pratiques :

• Vérifiez toujours que le tableau est trié. En Go, vous pouvez utiliser sort.Ints() du package sort.
• La formule mid := left + (right-left)/2 évite le débordement d'entier pour les grands tableaux.
• Pour travailler avec des chaînes, utilisez sort.SearchStrings() de la bibliothèque standard.

2. Tables de hachage : accès rapide aux données

En Go, la table de hachage intégrée est map. Elle permet un accès aux éléments en O(1) en moyenne. Mais il est important de comprendre son fonctionnement interne pour éviter les "pièges". La table de hachage utilise une fonction de hachage pour convertir la clé en index d'un tableau (bucket). Les collisions sont résolues par la méthode de chaînage (listes séparées pour chaque bucket).

Exemple d'utilisation de map :

package main

import "fmt"

func main() {    // Création d'une map    scores := make(map[string]int)    scores["Anna"] = 95    scores["Boris"] = 87    scores["Victor"] = 92

    // Recherche avec vérification d'existence    name := "Boris"    if score, exists := scores[name]; exists {        fmt.Printf("Note de %s : %d", name, score)    } else {        fmt.Printf("Étudiant %s non trouvé", name)    }

    // Suppression    delete(scores, "Anna")

    // Itération (l'ordre n'est pas garanti !)    for key, value := range scores {        fmt.Printf("%s : %d", key, value)    }}

Points importants :

• Map en Go est un type de référence. Lorsqu'elle est passée à une fonction, les modifications affectent l'original.
• N'utilisez pas une map nil pour écrire - cela provoquera une panique. Initialisez toujours avec make().
• L'ordre d'itération sur une map n'est pas déterministe. Si un ordre est nécessaire, utilisez un slice de clés séparé.
• Pour les clés, seuls les types comparables peuvent être utilisés : nombres, chaînes, booléens, pointeurs, structures sans slices/maps.

3. Tri : du bulle au rapide

Go propose un package puissant sort, qui implémente le tri rapide (quicksort) et d'autres algorithmes. Mais à des fins pédagogiques et de compréhension, il est important d'écrire un tri manuellement. Examinons deux implémentations : le tri à bulles (O(n²)) pour les petites données et le tri rapide (O(n log n)) pour les grandes