Почему языки программирования (например, Swift) не используют самую быструю из доступных - сортировку по группам?

Question

Тест сортировки Swift (), который является timsort по сравнению с сортировкой сегмента:

Количество предметов | Сортировка Свифта () | Ковш сортировки | Разница:

• 10000 | 0,0403 секунды | 0,0058 секунд | x6.9
• 100 000 | 0,494 секунды | 0,059 секунды | x8.4
• 1 000 000 | 6,2 секунды | 0,68 секунды | x9.1
• 10 000 000 | 42 секунды | 8,2 секунды | X5.1
• 100 000 000 | 506 секунд | 94 секунды | X5.4

Машина: iMac Pro (2017), 3,2 ГГц Intel Xeon W. Значения приведены для жесткого кода self.max(). Предоставленный код работает немного дольше.

Почему языки программирования (включая Swift) не используют более быструю сортировку сегментов?

import Foundation

extension Array where Element == Int {
    mutating func sort() {
        guard count > 0 else {
            return
        }
        var count = [Element:Int]()
        for item in self {
            if count[item] != nil {
                count[item] = count[item]! + 1
            } else {
                count[item] = 1
            }
        }
        let n = self.max()!
        self = []
        for value in 0..<n {
            if let count = count[value] {
                for _ in 0..<count {
                    self.append(value)
                }
            }
        }
    }
}

func sort(n: Int) {
    var array = [Int]()
    for _ in 0..<n {
        let newItem = Int.random(in: 0..<n)
        array.append(newItem)
    }
    let start = CFAbsoluteTimeGetCurrent()
    array.sort()
    let end = CFAbsoluteTimeGetCurrent()
    print("Time: \(end - start)")
}

sort(n: 1000000)

P.S. Потребление памяти практически одинаково.

UPDATE

Следующий код работает с любым типом, но он медленнее. Но это все же немного лучше, чем текущая реализация метода sort () в Swift. Итак, тема актуальна только для сортировки целых чисел.

Количество предметов | Сортировка Свифта () | Ковш сортировки | Разница:

• 10000 | 0,0403 секунды | 0,0405 секунд | x1
• 100 000 | 0,494 секунды | 0,48 секунды | x1
• 1 000 000 | 6,2 секунды | 3,6 секунды | X1.7
• 10 000 000 | 42 секунды | 43 секунды | x1
• 100 000 000 | 506 секунд | еще не проверен | ~ X1

Машина: iMac Pro (2017), 3,2 ГГц Intel Xeon W

import Foundation

extension Array where Element: Comparable & Hashable {
    mutating func sort() {
        var count = [Element:Int]()
        for item in self {
            if count[item] != nil {
                count[item] = count[item]! + 1
            } else {
                count[item] = 1
            }
        }
        self = []
        let keys = count.keys.sorted()
        for value in keys {
            if let count = count[value] {
                for _ in 0..<count {
                    self.append(value)
                }
            }
        }
    }
}

func sort(n: Int) {
    var array = [Int]()
    for _ in 0..<n {
        let newItem = Int.random(in: 0..<n)
        array.append(newItem)
    }
    let start = CFAbsoluteTimeGetCurrent()
    array.sort()
    let end = CFAbsoluteTimeGetCurrent()
    print("Time: \(end - start)")
}

sort(n: 1000000)

Answer 1

Нет «самой быстрой сортировки», это зависит от данных.

Например, для данных, которые уже отсортированы, самая быстрая сортировка - пузырьковая сортировка: вы ничего не перемещаете и, просто прочитав ввод, вы знаете, что все готово. Даже для данных, которые почти отсортированы, есть случаи, в которых (как ни удивительно) вариант алгоритма пузырьковой сортировки является очень разумным выбором (например, средство рендеринга строки сканирования на основе связанного списка, когда многие значения x обновляются небольшими количествами из одной строки сканирования). к следующему).

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

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

В зависимости от ситуации вы можете минимизировать сравнения или минимизировать свопы. Это не одно и то же.

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

...

Другими словами, это зависит от: -)

Ваш тестовый пример сортировки массива маленьких целых чисел не очень распространен в моем опыте.

Answer 2

Правильный ответ таков:

1. Гораздо лучшая производительность наблюдается только с целыми числами;
2. Предоставленный код работает только с целыми числами до 100 000 000 - изменение этого значения приведет к снижению производительности.

Универсальный код (см. Раздел «ОБНОВЛЕНИЕ») работает практически с той же производительностью..