为什么编程语言（例如 Swift）不使用可用的最快排序 - 桶排序？

Question

Swift 的 sort() 基准，与桶排序相比是 timsort：

项目数 | Swift 的排序() |桶排序 |差异：

10,000 | 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 GHz 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。内存消耗也差不多。

更新

以下代码适用于任何类型，但速度较慢。但它仍然比 Swift 中 sort() 方法的当前实现好一点。因此，该主题实际上仅用于排序整数。

项目数 | Swift 的排序() |桶排序 |差异：

10,000 | 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 GHz 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

周围没有"fastest sort"，要看数据了

例如，对于已经排序的数据，最快的排序是冒泡排序：您不移动任何东西，只需阅读输入后您就知道您完成了。即使对于几乎排序的数据，在某些情况下（足够令人惊讶）冒泡排序算法的变体是一个非常合理的选择（例如，基于链表的扫描线渲染器，其中许多 x 值从一个扫描线少量更新到下一个）。

在某些情况下，桶排序是一个很好的选择，但前提是键很小或者可以将其划分为不太小的块（并非总是如此）。

快速排序和变体使用随机来避免 worst-case 情况，并且仅使用 less-than 键之间的比较（始终可用的东西）。如果对数据知之甚少并且适合快速随机存取存储器，这是一个很好的默认选择。

根据具体情况，您可能想要最小化比较，或者可能想要最小化交换。这不是一回事。

如果数据对于快速内存来说太大并且对整个集合的随机访问存在问题，那么归并排序可能是一个不错的选择。

...

换句话说，这取决于:-)

根据我的经验，您仅对小整数数组进行排序的测试用例并不常见。

Answer 2

正确答案是：

只有整数才能观察到更好的性能；
提供的代码仅适用于最大 100,000,000 的整数 - 更改此代码会降低性能。

通用代码（参见 "UPDATE" 部分）具有几乎相同的性能。

为什么编程语言（例如 Swift）不使用可用的最快排序 - 桶排序？

Why do programming languages (for example, Swift) not use the fastest available sort - bucket sort?

sorting

optimization

performance

programming-languages

swift

更新