Comment mélanger un tableau en Swift : optimisation et performance

Formateur Python en ligne pour débutants

Apprenez Python facilement sans surcharge théorique. Résolvez des tâches pratiques avec vérification automatique et écrivez du code directement dans le navigateur.

Start Course

Comment bien mélanger un tableau en Swift : du débutant au pro

Avez-vous déjà réfléchi à la façon de créer une playlist aléatoire dans votre application ? Ou peut-être aviez-vous besoin de mélanger les questions d'un quiz pour qu'elles apparaissent dans un ordre différent à chaque fois ? Si vous travaillez avec Swift, tôt ou tard vous serez confronté à la tâche : comment mélanger un tableau (shuffle array). Cette question sur Stack Overflow a recueilli des milliers de vues, et ce n'est pas pour rien — les pièges sont plus nombreux qu'il n'y paraît.

Dans cet article, nous ne nous contenterons pas de montrer comment appeler shuffle(). Nous allons regarder sous le capot : analyser les algorithmes, comparer les performances, apprendre à faire un mélange optimisé et comprendre quand la méthode standard est un mal, et quand elle est la meilleure invention de l'humanité. C'est parti !

\n\n

Pourquoi un simple "random" est une mauvaise idée ?

Supposons que vous ayez un tableau :

var cards = ["As", "Roi", "Dame", "Valet"]

La méthode la plus naïve consiste à créer un nouveau tableau et à insérer les éléments à des positions aléatoires. Cela semble logique, n'est-ce pas ?

func naiveShuffle(_ array: [String]) -> [String] {\n    var shuffled = [String]()\n    for element in array {\n        let randomIndex = Int.random(in: 0...shuffled.count)\n        shuffled.insert(element, at: randomIndex)\n    }\n    return shuffled\n}

Avec de petits tableaux (4-10 éléments), cela fonctionne. Mais dès que le nombre d'éléments dépasse la centaine, vous ressentirez la douleur. Pourquoi ? Parce que insert(at:) a une complexité O(n) — chaque fois que vous insérez un élément au début ou au milieu, tous les éléments suivants sont décalés. Complexité finale : O(n²). Pour un tableau de 1000 éléments, cela représente 500 000 opérations. Pour 10 000, c'est déjà 50 millions. L'application commencera à ralentir, l'utilisateur partira, la note chutera. Ne faites pas cela.

\n\n

La méthode intégrée shuffle() : votre nouveau meilleur ami

Depuis Swift 4.2, nous avons la méthode native shuffle() (pour les tableaux mutables) et shuffled() (retourne un nouveau tableau). Voici comment cela fonctionne :

var numbers = [1, 2, 3, 4, 5]\nnumbers.shuffle()  // modifie le tableau d'origine\nprint(numbers)     // par exemple : [3, 1, 5, 2, 4]\n\nlet shuffledNumbers = numbers.shuffled()  // nouveau tableau\nprint(shuffledNumbers)                    // [4, 2, 1, 5, 3]

Sous le capot, Apple utilise l'algorithme de Fisher-Yates (également appelé algorithme de Knuth). C'est l'étalon-or du mélange. Comment fonctionne-t-il ? On parcourt le tableau du dernier élément au premier, pour chacun on choisit un index aléatoire de 0 à la position actuelle et on échange les éléments. Complexité : O(n). Pour un tableau de 10 000 éléments — seulement 10 000 opérations. 5000 fois plus rapide que l'approche naïve !

\n\n

Algorithme de Fisher-Yates : explication simple

Implémentons-le manuellement pour comprendre la magie :

extension Array {\n    mutating func customShuffle() {\n        for i in stride(from: count - 1, through: 1, by: -1) {\n            let j = Int.random(in: 0...i)\n            swapAt(i, j)\n        }\n    }\n}\n\nvar deck = Array(1...10)\ndeck.customShuffle()\nprint(deck) // [6, 2, 9, 1, 8, 4, 7, 3, 10, 5]

Que se passe-t-il ici ? Prenons un tableau de 5 éléments. On commence à l'index 4 (le dernier). On choisit un nombre aléatoire entre 0 et 4, on échange. Puis on passe à l'index 3, on choisit entre 0 et 3, on échange. Et ainsi de suite jusqu'à l'index 1. Chaque élément est garanti de se retrouver à une position aléatoire exactement une fois. Pas de décalages, pas de réinsertions — que des mathématiques pures.

Nuance importante : dans l'algorithme de Fisher-Yates, il ne faut pas choisir un index aléatoire de 0 à count-1 à chaque étape. Pourquoi ? Parce qu'alors certains éléments pourraient rester à leur place, tandis que d'autres seraient déplacés plusieurs fois, ce qui briserait l'uniformité de la distribution. Faites confiance à l'implémentation standard d'Apple — elle est optimale.