arrays - 如果使用 IntroSort 算法，Swift Array.sort() 如何比元组更快地对整数进行排序？ Swift 对整数的排序方式不同吗？

Question

我一直在挑选和探索 Swift Array 的排序函数，我惊讶地发现对 500,000 个整数的数组进行就地排序比对 500,000 个元组的数组排序快得多(快 5 倍)。我对这一发现感到惊讶，因为在询问了之前关于 Stack overflow 的问题并深入研究了 Swift 开源之后，Swift 似乎只是使用 introSort() 作为其排序算法。我试图解析代码，看看它是否以任何不同/特殊的方式处理整数排序，但我找不到任何东西。时间复杂度方面 IntroSort() 执行 NlogN 平均和最坏情况，因此我的元组排序和整数排序应该表现相同。如果您进行数学计算，5 倍加速开始看起来像是线性时间复杂度与 NlogN 时间复杂度。

这让我想到，也许 Swift 正在使用线性时间整数排序算法来处理整数排序，也许我只是错过了它。现在我不是整数排序方面的专家，但看起来最可行的整数排序算法候选者是鸽巢排序、计数排序和 RadixSort。我马上就排除了基数排序，因为它的时间复杂度是 O(wn)，其中 w 是字/整数大小。这意味着通用排序中的 (logN) 项需要大于 w，这将迫使我们对一个大得离谱的列表进行排序。查看 int 排序与元组排序的性能，我推断这里不可能使用基数排序。

按照淘汰顺序，这剩下 CountingSort 和 Pigeonhole Sort。它们都表现出最坏情况 O(N + k)，其中 N 是元素的数量，k 是值的范围。因此，为了确定 Swift 的算法是否属于这些类型之一，我认为将具有较小键值的 500,000 个整数的排序与具有大量键的 500,000 个整数的排序进行比较就足够了。对于第一个数组，我选择了 [1, 500,000] 的键范围。对于第二个数组，我选择了 [1, 6,000,500,000] 的键范围。如果第二个数组使用计数排序或鸽巢排序(只需计算一下)，您会期望第二个数组的排序比第一个数组的排序花费更长的时间，但事实并非如此。令我惊讶的是，性能完全一样!下面是我的示例代码和性能结果:

 func testTupleSortVsIntegerSort()
    {
        var intArray = [Int]()
        for value in 1..<500000 {
            intArray.append(value)
        }

        var tupleArray = intArray.map{($0, "sentinelValue")}
        intArray.shuffle()
        tupleArray.shuffle()

        var startTime = CFAbsoluteTimeGetCurrent()
        intArray.sort()
        var endTime = CFAbsoluteTimeGetCurrent()
        print("Integer sort took \(endTime - startTime) seconds")

        startTime = CFAbsoluteTimeGetCurrent()
        tupleArray.sort {
            return $0.0 < $1.0
        }
        endTime = CFAbsoluteTimeGetCurrent()
        print("Tuple sort took \(endTime - startTime) seconds")

    }

    func testIntegerSortWithSmallKeyRangeVsVeryLargeKeyRange()
    {

        var intArrayWithSmallKeys = [Int]()
        for value in 1..<500000 {
            intArrayWithSmallKeys.append(value)
        }

        var intArrayWithLargeKeys: [Int] = intArrayWithSmallKeys.map {
            if $0 < 250000 {
                return $0
            } else if $0 < 350000 {
                return $0 + 50000000
            } else {
                return $0 + 6000000000
            }
        }

        intArrayWithSmallKeys.shuffle()
        intArrayWithLargeKeys.shuffle()

        var startTime = CFAbsoluteTimeGetCurrent()
        intArrayWithSmallKeys.sort()
        var endTime = CFAbsoluteTimeGetCurrent()
        print("Integer sort with small keys took \(endTime - startTime) seconds")

        startTime = CFAbsoluteTimeGetCurrent()
        intArrayWithLargeKeys.sort()
        endTime = CFAbsoluteTimeGetCurrent()
        print("Integer sort with large keys took \(endTime - startTime) seconds")

    }

Test Case '-[ColorExtractorTests.GeneralPerformanceTest testTupleSortVsIntegerSort]' started.
Integer sort took 0.659438014030457 seconds
Tuple sort took 3.40226799249649 seconds

Test Case '-[ColorExtractorTests.GeneralPerformanceTest testIntegerSortWithSmallKeyRangeVsVeryLargeKeyRange]' started.
Integer sort with small keys took 0.665884971618652 seconds
Integer sort with large keys took 0.669007003307343 seconds

这是怎么回事？是否有一些我不知道的神奇整数排序算法？我对这些排序算法的理解是错误的还是我的分析有缺陷？

Answer 1

请参阅 Martin R 和 Honza Denjar 对问题的答复。这些现场帮助我意识到发生了什么。您排序的数据会严重影响性能，而不仅仅是要排序的元素数量。有时这一课会被遗忘。