Как перемешать массив в Swift: оптимизация и производительность

Как правильно перемешать массив в Swift: от новичка до профи

Вы когда-нибудь задумывались, как создать случайный плейлист в своём приложении? Или, может быть, вам нужно было перемешать вопросы в викторине, чтобы каждый раз они шли в новом порядке? Если вы работаете с Swift, то рано или поздно столкнётесь с задачей: как перемешать массив (shuffle array). Этот вопрос на Stack Overflow собрал тысячи просмотров, и не зря — подводных камней здесь больше, чем кажется на первый взгляд.

В этой статье мы не просто покажем, как вызвать shuffle(). Мы заглянем под капот: разберём алгоритмы, сравним производительность, научимся делать оптимизированное перемешивание и поймём, когда стандартный метод — зло, а когда — лучшее, что придумало человечество. Поехали!

Почему просто "random" — это плохая идея?

Допустим, у вас есть массив:

var cards = ["Туз", "Король", "Дама", "Валет"]

Самый наивный способ — создать новый массив и вставлять элементы в случайные позиции. Выглядит логично, правда?

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

На маленьких массивах (4-10 элементов) это работает. Но как только количество элементов перевалит за сотню, вы почувствуете боль. Почему? Потому что insert(at:) имеет сложность O(n) — каждый раз, когда вы вставляете элемент в начало или середину, все последующие элементы сдвигаются. Итоговая сложность: O(n²). Для массива из 1000 элементов это 500 000 операций. Для 10 000 — уже 50 миллионов. Приложение начнёт "подтормаживать", пользователь уйдёт, рейтинг упадёт. Не делайте так.

Встроенный метод shuffle(): ваш новый лучший друг

Начиная с Swift 4.2, у нас есть родной метод shuffle() (для изменяемых массивов) и shuffled() (возвращает новый массив). Вот как это работает:

var numbers = [1, 2, 3, 4, 5]
numbers.shuffle()  // изменяет исходный массив
print(numbers)     // например: [3, 1, 5, 2, 4]

let shuffledNumbers = numbers.shuffled()  // новый массив
print(shuffledNumbers)                    // [4, 2, 1, 5, 3]

Под капотом Apple использует алгоритм Фишера-Йетса (он же алгоритм Кнута). Это золотой стандарт перемешивания. Как он работает? Проходим по массиву от последнего элемента к первому, для каждого выбираем случайный индекс от 0 до текущей позиции и меняем элементы местами. Сложность: O(n). Для массива из 10 000 элементов — всего 10 000 операций. В 5000 раз быстрее, чем наивный подход!

Алгоритм Фишера-Йетса: разбор на пальцах

Давайте реализуем его вручную, чтобы понять магию:

extension Array {
    mutating func customShuffle() {
        for i in stride(from: count - 1, through: 1, by: -1) {
            let j = Int.random(in: 0...i)
            swapAt(i, j)
        }
    }
}

var deck = Array(1...10)
deck.customShuffle()
print(deck) // [6, 2, 9, 1, 8, 4, 7, 3, 10, 5]

Что здесь происходит? Допустим, массив из 5 элементов. Начинаем с индекса 4 (последний). Выбираем случайное число от 0 до 4, меняем местами. Потом переходим к индексу 3, выбираем от 0 до 3, меняем. И так до индекса 1. Каждый элемент гарантированно побывает на случайной позиции ровно один раз. Никаких сдвигов, никаких повторных вставок — чистая математика.

Важный нюанс: в алгоритме Фишера-Йетса нельзя выбирать случайный индекс от 0 до count-1 на каждом шаге. Почему? Потому что тогда некоторые элементы могут остаться на своих местах, а другие — переместиться несколько раз, что нарушит равномерность распределения. Доверьтесь стандартной реализации Apple — она оптимальна.

Производительность: тест-драйв

Давайте устроим небольшой бенчмарк. Возьмём массив из 100 000 целых чисел и сравним три подхода:

• Наивный shuffle (вставки) — для справки
• Стандартный shuffle() от Apple
• Ручная реализация Фишера-Йетса

Вот код для теста:

import Foundation

let largeArray = Array(0..<100_000)

// 1. Наивный (не делайте так!)
func naiveShuffle(_ array: [Int]) -> [Int] {
    var result = [Int]()
    for element in array {
        let pos = Int.random(in: 0...result.count)
        result.insert(element, at: pos)
    }
    return result
}

// 2. Стандартный
var testArray = largeArray
let start1 = CFAbsoluteTimeGetCurrent()
testArray.shuffle()
let time1 = CFAbsoluteTimeGetCurrent() - start1
print("Стандартный shuffle(): \(time1) сек") // ~0.02 сек

// 3. Ручной Фишер-Йетс
var testArray2 = largeArray
let start2 = CFAbsoluteTimeGetCurrent()
testArray2.customShuffle()
let time2 = CFAbsoluteTimeGetCurrent() - start2
print("Ручной shuffle: \(time2) сек") // ~0.02-0.03 сек

// Наивный — закомментируйте, если не хотите ждать 10 минут
// let start3 = CFAbsoluteTimeGetCurrent()
// let naiveResult = naiveShuffle(largeArray)
// let time3 = CFAbsoluteTimeGetCurrent() - start3
// print("Наивный: \(time3) сек") // ~120-150 сек

Результаты говорят сами за себя: стандартный shuffle() и ручная реализация практически идентичны по скорости (разница в пределах погрешности). Наивный подход — катастрофа. Вывод: используйте встроенный метод, если только вы не пишете библиотеку для iOS 10 и ниже (где его не было).

Когда стандартный shuffle() может подвести?

Казалось бы, всё прекрасно. Но есть пара сценариев, где стоит задуматься:

• Криптографическая стойкость. Стандартный shuffle() использует SystemRandomNumberGenerator, который основан на arc4random_buf. Для игр и викторин этого более чем достаточно. Но если вы пишете криптографическое приложение или систему лотерей, где от качества случайности зависят деньги, используйте SecRandomCopyBytes или другой криптостойкий генератор.
• Свой генератор случайных чисел. Ин