为什么标准库中的 IsSorted 对切片进行反向迭代？

来到golang学习网的大家，相信都是编程学习爱好者，希望在这里学习Golang相关编程知识。下面本篇文章就来带大家聊聊《为什么标准库中的 IsSorted 对切片进行反向迭代？》，介绍一下，希望对大家的知识积累有所帮助，助力实战开发！

出于好奇，我一直在查看标准库中 sort 包和即将添加到标准库中的实验性 slices 包的源代码。这两个包都定义了 issorted 函数，它们通过验证相邻元素是否已排序来检查列表是否已排序。然而，这是以相反的方式完成的。

我创建了一个小复制品，松散地基于通用 slices 包。我的实验确实表明反向版本更快。

func IsSortedForward[T any](slice []T, compare func(a, b T) int) bool {
    for i := 0; i < len(slice) - 1; i++ {
        if compare(slice[i], slice[i+1]) > 0 {
            return false
        }
    }
    return true
}

func IsSortedForward2[T any](slice []T, compare func(a, b T) int) bool {
    n := len(slice) - 1
    for i := 0; i < n; i++ {
        if compare(slice[i], slice[i+1]) > 0 {
            return false
        }
    }
    return true
}

func IsSortedReverse[T any](slice []T, compare func(a, b T) int) bool {
    for i := len(slice) - 1; i > 0; i-- {
        if compare(slice[i], slice[i-1]) < 0 {
            return false
        }
    }
    return true
}

我最初的想法是前向版本会更加“缓存友好”。然而，我确实注意到反向版本的一个优点，因为 len(slice) - 1 仅计算一次。而在前向版本中，它是在每次迭代时计算的。我的假设是，这就是反向版本稍微快一些的原因。

然后，我在前向版本中将 len(slice) - 1 提取到循环之外，以便仅计算一次，这确实提高了其性能。然而，它仍然比反向版本慢一些。我的猜测是，反向版本（带零）中的比较 i > 0 比正向版本中与 i < n 的比较更快？

为什么你认为反向版本更快？为什么调整后的正向版本仍然不如反向版本快？

编辑：我不知道编译器资源管理器（godbolt）可以与 go 一起使用...这里是这个问题中提到的功能的一些复制。看来go有自己的汇编语言？

正确答案

简而言之：因为可以从向下循环生成更高效的代码，特别是对于条件部分。

个人说明：您应该在自己的代码中使用它吗？如果性能不重要的话就不会。使用更具可读性且更有意义的循环。使用标准库中更快的版本有明显的好处（因为每个人都在使用它），但仅仅几微秒就不会牺牲代码的可读性。

issortedforward2() 和 issortedreverse() 或多或少相同，只是前者在主体内部使用递增运算符 (i++) 和 i+1，后者使用递减运算符 (i-- ) 和 i-1 在体内，这些在性能方面是相当的。

明显的差异来自于条件：前向变体使用 i < n，而反向变体使用 i > 0。第一个需要比较 2 个变量，后者需要将一个变量与一个非常特殊的值进行比较：0。

一般来说，第一个条件需要将 2 个变量（内存位置）加载到寄存器并比较它们的值。后者需要将 1 个变量加载到寄存器中并将其与特殊的 0 值进行比较。请注意，实际上这些变量可能存在于寄存器中，因此可能不必发生实际的内存加载。

您可以通过运行来检查生成的汇编代码：

go tool compile -s play.go > play.s

我使用的源代码行：

20 func issortedforward2[t any](slice []t, compare func(a, b t) int) bool {
21     n := len(slice) - 1
22     for i := 0; i < n; i++ {
23          if compare(slice[i], slice[i+1]) > 0 {
24              return false
25          }
26     }
27     return true
28 }
29 
30 func issortedreverse[t any](slice []t, compare func(a, b t) int) bool {
31     for i := len(slice) - 1; i > 0; i-- {
32         if compare(slice[i], slice[i-1]) < 0 {
33             return false
34         }
35     }
36     return true
37 }

有趣的行是第 22 行和第 31 行，以下是这些行生成的程序集：

play.go:22) JMP     77
play.go:22) MOVQ    main.n+16(SP), DI
play.go:22) MOVQ    main.compare+80(SP), SI
play.go:22) MOVQ    main.slice+64(SP), CX
play.go:22) MOVQ    main.slice+56(SP), BX
play.go:22) MOVQ    main..autotmp_9+24(SP), AX
play.go:22) CMPQ    AX, DI
play.go:22) JGE     136

play.go:31) DECQ    CX
play.go:31) JMP     53
play.go:32) MOVQ    main.i+16(SP), CX
play.go:32) DECQ    CX
play.go:32) MOVQ    main.slice+48(SP), BX
play.go:32) MOVQ    main.compare+72(SP), SI
play.go:31) TESTQ   CX, CX
play.go:31) JLE     100
play.go:31) MOVQ    CX, main.i+16(SP)

issortedforward2() 将 i 和 n 加载到 ax 和 di 寄存器中，并使用 cmpq 进行比较。

issortedreverse() 只需将 i 加载到 cx 中，并使用 testq 测试它是否为零。

超过 icza's answer（这非常好，并且适用于一般情况），反向操作的可能性更大允许在特定的半常见用例中提前短路（并且在没有帮助时无需花费任何费用）。许多高级语言，包括 go，不提供排序的容器类型，因此仅使用内置 + 标准库来维护排序的数据结构是很痛苦的（即使您为任何连续的数据序列类型提供了二进制搜索包）例如go的slice，它只是将搜索工作减少到o(log n)，插入仍然是o(n))。

为了解决这个问题，假设当用户需要一个不经常修改的排序数据结构时，他们只会附加新数据而不是按排序顺序插入，并且如果自此之后添加了任何新数据是最后排序的，它将在下一个需要排序的操作之前对其进行排序。该语言的排序算法通常会对此进行优化，例如python 的 Timsort 在接近 o(n) 时间处理“大部分已排序，有一些未排序的元素”，而 go 的现代 sort.sort （基于 pdqsort (pattern-defeating quick sort)）是 o(n) 如果单个元素已添加到末尾（尽管我不清楚这是否是一种特殊情况，还是当多个元素不合适时利用现有排序的一般能力）。

在这些“大部分已排序，有时末尾有一些未排序元素”的场景中，当调用 issorted 时，有两种可能性：

1. slice 已排序（自上次排序以来未添加任何内容，或者新元素碰巧保持顺序），或者
2. slice 的开头（可能是 slice 的大部分）已排序，但结尾处有（通常很少）未排序的元素。

在情况 #1 中，无论您向哪个方向操作，都必须检查整个 slice 才能最终返回 true，因此您检查的顺序并不重要。但在情况 #2 中，假设新元素是半随机排序的，反向操作意味着您将能够短路并几乎立即返回 false，而按正向顺序操作意味着您必须重新检查 (假设更大）数量的已排序元素在最后遇到较少数量的未排序元素之前保持排序，并缩短了更少的工作量。

为了澄清一个误解，缓存方面，按正向或反向顺序依次操作通常不会产生任何影响；无论方向如何，顺序访问模式在现代系统上都能得到很好的处理。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《为什么标准库中的 IsSorted 对切片进行反向迭代？》文章吧，也可关注golang学习网公众号了解相关技术文章。