swift - 为什么编程语言(例如 Swift)不使用最快的可用排序——桶排序？

Question

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

项目数量 | Swift 的 sort() |桶排序 |区别:

• 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)

附言内存消耗几乎相同。

更新

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

项目数量 | Swift 的 sort() |桶排序 |区别:

• 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

没有“最快排序”，这取决于数据。

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

在某些情况下，桶排序是一个非常好的选择，但前提是键很小或者它可以被划分为不太小的部分(并非总是如此)。

快速排序和变体使用随机来避免最坏的情况，并且只使用键之间的小于比较(总是可用的东西)。如果对数据知之甚少并且适合快速随机存取存储器，这是一个很好的默认选择。

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

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

...

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

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