Timsort и Introsort: алгоритмы сортировки Swift

Timsort и Introsort: алгоритмы сортировки Swift

Вы когда-нибудь спрашивали себя, какой алгоритм используется методом сортировки Swift? Существует множество алгоритмов сортировки, и есть вероятность, что вам редко придется использовать что-то иное, кроме встроенного sort() метода языка. Однако знание свойств алгоритма сортировки, встроенного в ваш язык, важно, если вы хотите предотвратить нежелательное поведение и неприятные крайние случаи.

При анализе алгоритмов сортировки вам нужно искать два свойства:

Примечание. Если вам сложно читать код на Medium, прочтите этот пост в моем блоге SwiftRocks!

1 - Стабильность сортировки

Стабильность алгоритма сортировки представляет собой способность алгоритма поддерживать исходный порядок равных элементов после сортировки. нестабильный алгоритм сортировки не гарантирует, что порядок равных элементов в несортированном массиве останется неизменным после сортировки, тогда как стабильный алгоритм гарантирует, что они останутся неизменными.

В конце концов, это может показаться странным, но если элементы одинаковые, зачем мне заботиться об их общем порядке? Это может быть верно, если вы сортируете элементы по значению, но при сортировке элементов по произвольному приоритету использование нестабильных алгоритмов может привести к нежелательным результатам.

Предположим, мы создаем музыкальный проигрыватель, и наша текущая задача - отсортировать песни по их популярности:

struct Music: Comparable, Equatable, CustomStringConvertible {
    let name: String
    let popularityValue: Int
    static func < (lhs: Music, rhs: Music) -> Bool {
        return lhs.popularityValue < rhs.popularityValue
    }
    var description: String {
        return name
    }
}
var songs: [Music] = [
    Music(name: "I'm that swifty", popularityValue: 3),
    Music(name: "Swift boi", popularityValue: 5),
    Music(name: "Swift That Walk", popularityValue: 1),
    Music(name: "Too Swift", popularityValue: 5),
]

Если отсортировать songs с помощью Quicksort, мы получим следующий результат:

extension Array where Element: Equatable & Comparable {
    func quicksort(comparison: ((Element, Element) -> Bool)) -> [Element] {
        var copy = self
        copy.quick(0, count - 1, comparison: comparison)
        return copy
    }
    mutating private func quick(_ i: Int, _ j: Int, comparison: ((Element, Element) -> Bool)) {
        guard i < j else {
            return
        }
        let pivot = partition(i, j, comparison: comparison)
        quick(i, pivot - 1, comparison: comparison)
        quick(pivot + 1, j, comparison: comparison)
    }
    mutating private func partition(_ i: Int, _ j: Int, comparison: ((Element, Element) -> Bool)) -> Int {
        let pivotElement = self[j]
        var indexToAdd = i - 1
        for k in i..<j {
            if comparison(self[k], pivotElement) {
                indexToAdd += 1
                swapAt(indexToAdd, k)
            }
        }
        swapAt(indexToAdd + 1, j)
        return indexToAdd + 1
    }
}
songs = songs.quicksort {
    $0.popularityValue > $1.popularityValue
}
print(songs)
// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]

Хотя "Swift boi" был помещен перед Too Swift в исходном массиве, Quicksort изменил их позиции!

Это не так уж и плохо, поскольку мы никогда не использовали несортированную версию массива. Однако подумайте, что произойдет, если мы повторно отсортируем массив несколько раз:

songs = songs.quicksort {
    $0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
    $0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
    $0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
    $0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
    $0.popularityValue > $1.popularityValue
}
print(songs)
// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]

Их относительный порядок постоянно меняется!

Причина в том, что Quicksort - это нестабильный алгоритм сортировки. Если по какой-то причине нам нужно было постоянно обновлять этот список в пользовательском интерфейсе, пользователь мог бы видеть, как песни меняют позиции в рейтинге, даже если они имеют одинаковый приоритет. Это не очень хорошо.

Чтобы сохранить их порядок, нам нужно использовать стабильный алгоритм, например Сортировка слияний.

extension Array where Element: Equatable & Comparable {
    func mergesort(comparison: ((Element, Element) -> Bool)) -> [Element] {
        return merge(0, count - 1, comparison: comparison)
    }
    private func merge(_ i: Int, _ j: Int, comparison: ((Element, Element) -> Bool)) -> [Element] {
        guard i <= j else {
            return []
        }
        guard i != j else {
            return [self[i]]
        }
        let half = i + (j - i) / 2
        let left = merge(i, half, comparison: comparison)
        let right = merge(half + 1, j, comparison: comparison)
        var i1 = 0
        var i2 = 0
        var new = [Element]()
        new.reserveCapacity(left.count + right.count)
        while i1 < left.count && i2 < right.count {
            if comparison(right[i2], left[i1]) {
                new.append(right[i2])
                i2 += 1
            } else {
                new.append(left[i1])
                i1 += 1
            }
        }
        while i1 < left.count {
            new.append(left[i1])
            i1 += 1
        }
        while i2 < right.count {
            new.append(right[i2])
            i2 += 1
        }
        return new
    }
}
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]

2 - Сложность времени / пространства

Вторая важная вещь, о которой нужно знать, - это сколько дополнительной памяти требуется алгоритму для работы и какие лучшие / худшие случаи для алгоритма.

Мой любимый пример - Сортировка с подсчетом: когда массив сортируется, просто подсчитывая количество вхождений каждого элемента, а затем размещая их по порядку. Если разница между каждым значением мала, например [3,1,4,2,5], этот алгоритм может сортировать массивы во время выполнения, очень близком к O (n), но если разница большая, например [1,1000000000], сортировка с подсчетом займет огромное количество времени на выполнение, даже если массив небольшой.

Точно так же знаменитый Quick Sort высоко ценится за то, что он в среднем быстрый и оперативный алгоритм O (n log n), но он имеет ужасный худший случай O (n2), если точка поворота всегда является самым высоким / наименьшим элементом в раздел. Если вы имеете дело с большими объемами данных или в ограниченной среде, будет специальный алгоритм сортировки, который лучше всего соответствует вашим потребностям.

Алгоритм до Swift 5: внутренняя сортировка

До Swift 5 алгоритм сортировки Swift представлял собой гибридный алгоритм под названием Introsort, который смешивал сильные стороны Quicksort, Heapsort и Insertion Sort в один алгоритм, чтобы гарантировать худший случай O (n log n).

Идея Introsort проста: во-первых, если у вас менее 20 элементов в сортируемом разделе, используется сортировка вставкой. Хотя этот алгоритм имеет наихудший случай O (n2), он также имеет лучший случай O (n). По сравнению с обычными алгоритмами O (n log n) сортировка вставкой всегда будет работать лучше при небольших входных данных.

Если массив не маленький, будет использоваться Quicksort. Это доведет наш лучший случай до O (n log n), но также сохранит худший случай O (n2). Однако Introsort может этого избежать - если дерево рекурсии для Quicksort становится слишком глубоким, раздел переключается на Heapsort. В этом случае «слишком глубоко» считается 2 * floor(log2(array.count)).

internal mutating func _introSortImpl(within range: Range<Index>,
                                      by areInIncreasingOrder: (Element, Element) throws -> Bool,
                                      depthLimit: Int) rethrows {
    // Insertion sort is better at handling smaller regions.
    if distance(from: range.lowerBound, to: range.upperBound) < 20 {
        try _insertionSort(within: range, by: areInIncreasingOrder)
    } else if depthLimit == 0 {
        try _heapSort(within: range, by: areInIncreasingOrder)
    } else {
        // Partition and sort.
        // We don't check the depthLimit variable for underflow because this
        // variable is always greater than zero (see check above).
        let partIdx = try _partition(within: range, by: areInIncreasingOrder)
        try _introSortImpl(
            within: range.lowerBound..<partIdx,
            by: areInIncreasingOrder,
            depthLimit: depthLimit &- 1)
        try _introSortImpl(
            within: partIdx..<range.upperBound,
            by: areInIncreasingOrder,
            depthLimit: depthLimit &- 1)
    }
}

Introsort жадно пытается выбрать лучший алгоритм для данной ситуации, прибегая к другому варианту, когда предыдущий выбор идет не так. Он имеет лучший случай O (n) и худший случай O (n log n), что делает его достойным универсальным алгоритмом.

С точки зрения использования памяти он будет работать немного хуже, чем обычный алгоритм сортировки. Хотя три алгоритма могут выполнять сортировку на месте, реализация Introsort в Swift была рекурсивной. Поскольку Swift не гарантирует, что вызовы хвостовой рекурсии будут оптимизированы, запуск встроенного sort() pre-Swift 5 был не лучшим вариантом, если важно было сохранить низкий уровень использования памяти.

Важно отметить, что Introsort был нестабильным. Хотя сортировка вставкой работает стабильно, реализация Quicksort и Heapsort по умолчанию - нет. Если порядок равных элементов был важен, использование sort() pre-Swift 5 также не было хорошей идеей.

После Swift 5 - Timsort

В период с 2015 по 2018 год появилось множество потоков о добавлении стабильного алгоритма сортировки в Swift, который не полагался на рекурсию, но многообещающие обсуждения впервые появились только в начале 2018 года. В октябре 2018 года запрос на вытягивание был окончательно объединен, чтобы изменить Выполните внутреннюю сортировку в модифицированной версии Timsort.

Timsort - это гибридный алгоритм, подобный Introsort, но с разными подходами. Он работает, разделяя массив на более мелкие разделы, сортируя эти более мелкие разделы с помощью сортировки вставкой, а затем объединяя эти разделы вместе с сортировкой слиянием. Поскольку и сортировка вставкой, и сортировка слиянием стабильны, Timsort является стабильным, и, хотя он также имеет наихудший случай O (n log n) и непостоянную сложность пространства, он имеет тенденцию быть значительно быстрее, чем более наивные алгоритмы в реальных сценариях. Причина, по которой Timsort может быть таким быстрым, заключается в том, что, хотя описание звучит достаточно просто, на самом деле каждый из этих шагов сильно настроен на эффективность.

Нахождение следующего «пробега» (разбиение на разделы)

Вместо того, чтобы сначала разделить все и объединить в качестве последнего шага, как Mergesort, Timsort сканирует массив один раз и постепенно объединяет эти области (так называемые «прогоны») по мере их нахождения.

Прелесть в том, что, в отличие от Mergesort, прогон - это не просто массив, разделенный пополам. Timsort злоупотребляет тем фактом, что каждый массив, который вы хотите отсортировать, скорее всего, будет иметь несколько смежных подпоследовательностей, которые почти или уже отсортированы, что является лучшим случаем сортировки вставкой. Чтобы найти следующий прогон, Timsort будет перемещать указатель до тех пор, пока текущая последовательность не перестанет быть восходящей / нисходящей моделью:

[1, 2, 3, 1, 9, 6]
 i     j

Примечание. Этот пример предназначен только для наглядности - поскольку массив здесь небольшой, Timsort сразу же отсортирует его вставкой.

Диапазон от i до j определяет наш первый запуск запуск, но оптимизация на этом не заканчивается.

Во-первых: если последовательность убывает, мы уже можем отсортировать ее по линейному времени, поменяв местами элементы.

Во-вторых: чтобы увеличить скорость сортировки вставкой и сбалансировать количество операций слияния, которые будут выполнены позже, Timsort определяет, что каждый запуск должен иметь минимальный размер степени двойки от 16 до 128, или, по крайней мере, что-то очень близкое к этому. Если размер найденного прогона меньше минимального размера, то диапазон текущего прогона расширяется и сортируется с помощью сортировки вставкой.

// Find the next consecutive run, reversing it if necessary.
var (end, descending) = try _findNextRun(in: self, from: start, by: areInIncreasingOrder)
if descending {
    _reverse(within: start..<end)
}
// If the current run is shorter than the minimum length, use the
// insertion sort to extend it.
if end < endIndex && end - start < minimumRunLength {
    let newEnd = Swift.min(endIndex, start + minimumRunLength)
    try _insertionSort(within: start..<newEnd, sortedEnd: end, by: areInIncreasingOrder)
    end = newEnd
}

Для фактического размера Swift специально выберет значение от 32 до 64, которое зависит от размера массива. Наконец, после того, как запуск найден, он добавляется в стек, содержащий все другие предыдущие запуски, которые мы нашли.

Объединение прогонов

Каждый раз, когда запускается, Timsort пытается свернуть три верхних прогона стека в один, объединяя их вместе, пока не будут выполнены следующие условия:

runs.count < 3 || runs[runs.count - 2].size > (runs[runs.count - 1].size + runs.last!.count)
&&
runs.count < 2 || runs[runs.count - 1].size > runs.last!.size

Это сделано для того, чтобы уменьшить количество запусков, которые мы должны помнить, но в основном для того, чтобы сбалансировать общий размер запусков, поскольку их близкое расположение полезно для фазы слияния Timsort.

На первый взгляд фаза слияния Timsort работает так же, как Mergesort: мы сравниваем пару элементов из каждого массива, выбираем наименьший из них и перемещаем его в правильную позицию в конечном массиве.

Тем не менее, Timsort прекрасно подчеркивает тот факт, что если один конкретный массив продолжает «выигрывать» в сравнении, то, вероятно, так и будет. Если это произойдет, вместо того, чтобы продолжать сравнение элементов, мы можем просто выполнить двоичный поиск правильной позиции элемента из «проигрышного» массива в «выигрышном», перемещая все элементы перед ним в последний массив. Это называется скачком, и это экономит нам много времени, позволяя пропустить сравнение всего фрагмента выигрышного массива.

Галопирующий процесс может быть прерван, если процесс двоичного поиска проигрывает обычному процессу сравнения. Вы можете увидеть все оптимизации, сделанные в описании Timsort. Наконец, после того, как были найдены все прогоны, оставшиеся прогоны в стеке постепенно объединяются вместе, пока не будет отсортирован весь массив.

Основное отличие Swift заключается в том, что реализация Timsort в компиляторе не использует галопирование и пытается свернуть прогоны на основе последних четырех прогонов вместо последних трех. Тем не менее, он превосходит Introsort практически во всех сценариях.

Заключение

Timsort - один из самых быстрых алгоритмов сортировки для реальных проблем. Знание того, какой алгоритм использует ваш язык, может помочь вам оптимизировать код, принимая более обоснованные решения в зависимости от того, какие данные вы обрабатываете.

Следуйте за мной в моем Твиттере (@rockthebruno) и дайте мне знать о любых предложениях и исправлениях, которыми вы хотите поделиться.

Ссылки и полезные материалы

Предложение стабильной сортировки
PR стабильной сортировки
Интросорт
Timsort
Timsort (Wiki)

Первоначально опубликовано на https://swiftrocks.com.