Wie man ein Array in Swift mischt: Optimierung und Leistung

Wie man ein Array in Swift richtig mischt: vom Anfänger zum Profi

Haben Sie sich jemals gefragt, wie Sie eine zufällige Playlist in Ihrer App erstellen? Oder mussten Sie vielleicht Fragen in einem Quiz mischen, damit sie jedes Mal in einer neuen Reihenfolge erscheinen? Wenn Sie mit Swift arbeiten, werden Sie früher oder später auf die Aufgabe stoßen: Wie man ein Array mischt (shuffle array). Diese Frage auf Stack Overflow hat tausende Aufrufe, und das zu Recht – die Fallstricke sind zahlreicher, als es auf den ersten Blick scheint.

In diesem Artikel zeigen wir nicht nur, wie man shuffle() aufruft. Wir schauen unter die Haube: analysieren Algorithmen, vergleichen die Leistung, lernen optimiertes Mischen und verstehen, wann die Standardmethode schlecht und wann sie das Beste ist, was die Menschheit erfunden hat. Los geht's!

Warum einfaches "random" eine schlechte Idee ist?

Angenommen, Sie haben ein Array:

var cards = ["Ass", "König", "Dame", "Bube"]

Der naivste Ansatz ist, ein neues Array zu erstellen und Elemente an zufällige Positionen einzufügen. Sieht logisch aus, oder?

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}

Bei kleinen Arrays (4-10 Elemente) funktioniert das. Aber sobald die Anzahl der Elemente über hundert steigt, werden Sie den Schmerz spüren. Warum? Weil insert(at:) eine Komplexität von O(n) hat – jedes Mal, wenn Sie ein Element am Anfang oder in der Mitte einfügen, werden alle nachfolgenden Elemente verschoben. Die Gesamtkomplexität: O(n²). Für ein Array mit 1000 Elementen sind das 500.000 Operationen. Für 10.000 bereits 50 Millionen. Die App beginnt zu "ruckeln", der Nutzer geht, die Bewertung sinkt. Machen Sie das nicht.

Die integrierte Methode shuffle(): Ihr neuer bester Freund

Seit Swift 4.2 haben wir die native Methode shuffle() (für veränderbare Arrays) und shuffled() (gibt ein neues Array zurück). So funktioniert es:

var numbers = [1, 2, 3, 4, 5]\nnumbers.shuffle()  // ändert das ursprüngliche Array\nprint(numbers)     // z.B.: [3, 1, 5, 2, 4]\n\nlet shuffledNumbers = numbers.shuffled()  // neues Array\nprint(shuffledNumbers)                    // [4, 2, 1, 5, 3]

Unter der Haube verwendet Apple den Fisher-Yates-Algorithmus (auch bekannt als Knuth-Algorithmus). Das ist der Goldstandard für das Mischen. Wie funktioniert er? Wir gehen das Array vom letzten zum ersten Element durch, wählen für jedes einen zufälligen Index von 0 bis zur aktuellen Position und tauschen die Elemente. Komplexität: O(n). Für ein Array mit 10.000 Elementen sind das nur 10.000 Operationen. 5000 Mal schneller als der naive Ansatz!

Der Fisher-Yates-Algorithmus: Einfach erklärt

Lassen Sie uns ihn manuell implementieren, um die Magie zu verstehen:

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]

Was passiert hier? Angenommen, ein Array mit 5 Elementen. Wir beginnen bei Index 4 (dem letzten). Wählen eine Zufallszahl von 0 bis 4, tauschen. Dann gehen wir zu Index 3, wählen von 0 bis 3, tauschen. Und so weiter bis Index 1. Jedes Element ist garantiert genau einmal an einer zufälligen Position. Keine Verschiebungen, keine wiederholten Einfügungen – reine Mathematik.

Ein wichtiger Punkt: Im Fisher-Yates-Algorithmus darf man nicht bei jedem Schritt einen zufälligen Index von 0 bis count-1 wählen. Warum? Weil dann einige Elemente an ihrem Platz bleiben könnten, während andere mehrmals verschoben werden, was die Gleichmäßigkeit der Verteilung stört. Vertrauen Sie der Standardimplementierung von Apple – sie ist optimal.