问题标签 [sorting-network]

这是我很久以前遇到的问题。我想我可以问问你的想法。假设我有非常小的数字（整数）列表，4 或 8 个元素，需要快速排序。什么是最好的方法/算法？

我的方法是使用 max/min 函数（10 个函数对 4 个数字进行排序，没有分支，iirc）。

我想我的问题更多地与实现有关，而不是算法类型。

在这一点上，它变得有点依赖于硬件，所以让我们假设带有 SSE3 的 Intel 64 位处理器。

谢谢

在回答另一个 Stack Overflow 问题（这个）时，我偶然发现了一个有趣的子问题。对 6 个整数的数组进行排序的最快方法是什么？

由于问题非常低级：

• 我们不能假设库是可用的（并且调用本身有它的成本），只有纯 C
• 为了避免清空指令管道（成本非常高），我们可能应该尽量减少分支、跳转和所有其他类型的控制流中断（比如隐藏在&&or中的序列点后面的那些||）。
• 房间受到限制，最小化寄存器和内存使用是一个问题，理想情况下，就地排序可能是最好的。

实际上，这个问题是一种高尔夫，其目标不是最小化源长度而是最小化执行时间。我将其称为“Zening”代码，正如Michael Abrash所著的Zen of Code optimization及其续集的书名中所使用的那样。

至于为什么有趣，有好几层：

• 该示例简单易懂，易于测量，涉及的C技能不多
• 它显示了为问题选择好的算法的效果，以及编译器和底层硬件的效果。

这是我的参考（天真，未优化）实现和我的测试集。

原始结果

随着变体的数量越来越多，我将它们全部收集在一个可以在此处找到的测试套件中。感谢 Kevin Stock，实际使用的测试比上面显示的要简单一些。您可以在自己的环境中编译和执行它。我对不同目标架构/编译器的行为非常感兴趣。（好的，伙计们，把它放在答案中，我会为新结果集的每个贡献者 +1）。

一年前，我向 Daniel Stutzbach（打高尔夫球）给出了答案，因为他是当时最快解决方案（排序网络）的来源。

Linux 64 位、gcc 4.6.1 64 位、Intel Core 2 Duo E8400、-O2

• 直接调用 qsort 库函数：689.38
• 天真的实现（插入排序）：285.70
• 插入排序 (Daniel Stutzbach) : 142.12
• 插入排序展开：125.47
• 排名顺序：102.26
• 寄存器排名顺序：58.03
• 排序网络 (Daniel Stutzbach)：111.68
• 排序网络（Paul R）：66.36
• 使用快速交换对网络 12 进行排序：58.86
• 排序网络 12 重新排序交换：53.74
• 排序网络 12 重新排序简单交换：31.54
• 带快速交换的重新排序的排序网络：31.54
• 带快速交换 V2 的重新排序的排序网络：33.63
• 内联冒泡排序（Paolo Bonzini）：48.85
• 展开插入排序 (Paolo Bonzini) : 75.30

Linux 64 位、gcc 4.6.1 64 位、Intel Core 2 Duo E8400、-O1

• 直接调用 qsort 库函数：705.93
• 天真的实现（插入排序）：135.60
• 插入排序 (Daniel Stutzbach) : 142.11
• 插入排序展开：126.75
• 排名顺序：46.42
• 寄存器排名顺序：43.58
• 排序网络 (Daniel Stutzbach)：115.57
• 排序网络（Paul R）：64.44
• 使用快速交换对网络 12 进行排序：61.98
• 排序网络 12 重新排序交换：54.67
• 排序网络 12 重新排序简单交换：31.54
• 带快速交换的重新排序的排序网络：31.24
• 带快速交换 V2 的重新排序的排序网络：33.07
• 内联冒泡排序（Paolo Bonzini）：45.79
• 展开插入排序（Paolo Bonzini）：80.15

我将 -O1 和 -O2 结果都包括在内，因为令人惊讶的是，对于几个程序来说，O2 的效率低于O1。我想知道什么具体的优化有这个效果？

对提议的解决方案的评论

插入排序 (Daniel Stutzbach)

正如预期的那样，最小化分支确实是一个好主意。

排序网络 (Daniel Stutzbach)

比插入排序好。我想知道主要效果是否不是来自避免外部循环。我通过展开插入排序进行了尝试，确实我们得到了大致相同的数字（代码在这里）。

排序网络 (Paul R)

迄今为止最好的。我用来测试的实际代码在这里。还不知道为什么它的速度几乎是其他排序网络实现的两倍。参数传递？快速最大值？

排序网络 12 带有快速交换的交换

正如 Daniel Stutzbach 所建议的，我将他的 12 交换排序网络与无分支快速交换相结合（代码在此处）。它确实更快，是迄今为止最好的，利润率很小（大约 5%），正如使用少掉 1 次交换所预期的那样。

有趣的是，无分支交换似乎比在 PPC 架构上使用 if 的简单交换效率低很多（4 倍）。

调用库 qsort

为了提供另一个参考点，我还按照建议尝试调用库 qsort（代码在此处）。正如预期的那样，它要慢得多：慢了 10 到 30 倍......随着新的测试套件变得很明显，主要问题似乎是第一次调用后库的初始加载，它与其他的相比并没有那么差版本。在我的 Linux 上，它只慢了 3 到 20 倍。在其他人用于测试的某些架构上，它似乎甚至更快（我对此感到非常惊讶，因为库 qsort 使用更复杂的 API）。

排序

Rex Kerr 提出了另一种完全不同的方法：对数组中的每一项直接计算其最终位置。这是有效的，因为计算排名顺序不需要分支。这种方法的缺点是它需要三倍于数组的内存量（一份数组和变量的副本来存储排名顺序）。性能结果非常令人惊讶（也很有趣）。在我的 32 位操作系统和 Intel Core2 Quad E8300 的参考架构上，循环计数略低于 1000（如使用分支交换对网络进行排序）。但是当在我的 64 位机器（Intel Core2 Duo）上编译和执行时，它的表现要好得多：它成为迄今为止最快的。我终于找到了真正的原因。我的 32 位盒子使用 gcc 4.4.1 和我的 64 位盒子 gcc 4.4。

更新：

正如上面公布的数字所示，这种效果仍然被更高版本的 gcc 增强，并且排名顺序始终是任何其他替代方案的两倍。

使用重新排序的交换对网络 12 进行排序

使用 gcc 4.4.3 的 Rex Kerr 提案的惊人效率让我想知道：内存使用量是 3 倍的程序怎么可能比无分支排序网络更快？我的假设是，它具有较少的读写依赖，从而可以更好地使用 x86 的超标量指令调度程序。这给了我一个想法：重新排序交换以最大程度地减少写入后读取的依赖关系。更简单地说：当您这样做时，SWAP(1, 2); SWAP(0, 2);您必须等待第一次交换完成才能执行第二次交换，因为两者都访问公共存储单元。当你这样做时SWAP(1, 2); SWAP(4, 5);，处理器可以并行执行。我试过了，它按预期工作，排序网络的运行速度快了大约 10%。

使用简单交换对网络进行排序 12

在最初的帖子 Steinar H. Gunderson 建议一年后，我们不应该试图超越编译器并保持交换代码简单。这确实是一个好主意，因为生成的代码快了大约 40%！他还提出了使用 x86 内联汇编代码手动优化的交换，仍然可以节省更多的周期。最令人惊讶的是（它说明了程序员的心理），一年前没有人尝试过那个版本的交换。我用来测试的代码在这里。其他人提出了编写 C 快速交换的其他方法，但它产生的性能与具有良好编译器的简单交换相同。

“最佳”代码现在如下：

如果我们相信我们的测试集（是的，它很差，它的唯一好处是简短、简单且易于理解我们正在测量的内容），那么生成的代码的平均循环数低于 40 个循环（执行 6 次测试）。这使得每次交换平均为 4 个周期。我称之为惊人的快。还有其他可能的改进吗？

参考最快排序的固定长度 6 int 数组，我不完全理解这个排序网络如何击败像插入排序这样的算法。

形成这个问题，这里是完成排序所花费的 CPU 周期数的比较：

Linux 32 位，gcc 4.4.1，Intel Core 2 Quad Q8300，​​-O2

• 插入排序 (Daniel Stutzbach) : 1425
• 排序网络 (Daniel Stutzbach)：1080

使用的代码如下：

插入排序 (Daniel Stutzbach)

排序网络 (Daniel Stutzbach)

我知道排序网络非常适合并行排序，因为某些步骤独立于其他步骤。但是这里我们没有使用并行化。

我希望它更快，因为它具有事先知道元素的确切数量的优势。插入排序究竟在哪里以及为什么会进行不必要的比较？

编辑1：

这是与这些代码进行比较的输入集：

我正在寻找一个 5 元素排序的排序网络实现，但是由于我找不到关于 SO 的好的参考，我想要求对所有 n 的小值进行排序网络，至少 n=3通过 n=6 但更高的值也会很棒。一个好的答案至少应该将它们列为“交换”（对 2 个元素排序）操作的序列，但也可以很好地看到低阶排序网络的递归分解。

对于我的应用程序，我实际上只关心 5 个元素的中位数，而不是真正将它们按顺序排列。也就是说，只要中位数在正确的位置结束，其他 4 个元素的顺序可能在结果中未指定。可以使用与排序网络相关的方法来计算交换次数少于执行完整排序的中位数吗？如果是这样，那么对我的问题（对于 n = 5）和其他情况的这种解决方案也将是一个很好的答案。

（注意：我已将此问题标记为 C，因为 C 是我使用的语言，我怀疑遵循 C 标签的人有很好的答案，但我并不关心答案是否实际上是用 C 和伪代码编写的只要它很容易翻译成C，只要满足上述标准，它自然应该这样做。）

我实现了一个使用排序的算法。我尝试了 Thrust::sort_by_key 大约需要 0.4 秒来对包含 10^7 个元素的数组进行排序。

我认为双音排序网络应该比 Thrust::sort_by_key 更快。但是，双调排序需要大约 2.5 秒才能对上述相同的数组进行排序。我使用了 SDK 提供的双音排序网络。我只是稍微修改了原来的双音排序。

你能告诉我为什么吗？或者给我一些建议？

谢谢，

易

2011 年 8 月 15 日

我有一些性能关键代码，涉及在 C++ 中对一个非常短的固定长度数组进行排序，其中包含大约 3 到 10 个元素（参数在编译时更改）。

我突然想到，专门针对每个可能的输入大小的静态排序网络可能是一种非常有效的方法：我们进行所有必要的比较以确定我们处于哪种情况，然后进行最佳交换次数以进行排序数组。

为了应用这一点，我们使用了一些模板魔法来推断数组长度并应用正确的网络：

显然，编写所有这些代码很麻烦，所以：

• 有人对这是否值得努力有任何意见吗？
• 有谁知道这种优化是否存在于任何标准实现中，例如 std::sort ？
• 是否有一个简单的地方可以获取实现这种排序网络的代码？
• 也许可以使用模板魔术静态生成这样的排序网络。

现在我只使用带有静态模板参数的插入排序（如上），希望它会鼓励展开和其他编译时优化。

欢迎您的想法。

更新： 我编写了一些测试代码来比较“静态”插入短和 std::sort。（当我说静态时，我的意思是数组大小是固定的，并在编译时推导出来（可能允许循环展开等）。我得到至少 20% 的 NET 改进（请注意，生成包含在时间中）。平台：铿锵声，OS X 10.9。

代码在这里https://github.com/rosshemsley/static_sorting如果您想将它与您的 stdlib 实现进行比较。

我还没有为比较器网络分类器找到一套不错的实现。

我正在研究 C++ 中的 Robert Sedwick 算法中的奇数合并排序。

作为文本作者的一部分，作者提到了如何使用奇偶合并排序来实现排序网络中的并行排序。在这种情况下，作者提到了蝴蝶网络

我的问题是蝴蝶网络基本上是什么，为什么它被称为蝴蝶。用简单的例子进行解释将不胜感激。

我已经用谷歌搜索了它，但没有找到简单的示例解释。

插入排序，重写为排序网络产生如下内容：

它对六个项目进行排序，例如使用以下比较：

现在假设我有第七个值要排序。修改是微不足道的，添加另一组/线比较......

其他类型（如双音）需要更复杂的修改，特别是需要在所有地方对之前的行进行添加。

我的问题是： 是否有任何其他类型（如插入）允许简单的单行添加以支持搜索中的额外项目？我对像双音这样的较低计算复杂度的排序特别感兴趣。

我在 vhdl 中有一个模块，它执行标题中的状态。问题是，这在一组排序的数字、一个递减的排序集和一组半混合的数字中完美无缺，但是对于真正的随机数，这个模块确实有效，知道为什么吗？

我正在使用一个 64 到 64 模块，它使用两个 32 到 32，这个使用两个 16 到 16，最后一个使用两个 8 到 8 模块，我很确定 8 到 8 和 16to16 模块是正确的，由我的老师完成，但对 64 到 64 不太确定，请给我一些反馈，可能有什么问题:)

我的作业文档中有一个问题，我很难想象和理解这个问题。问题如下：

我们可以将具有 c 个比较器的 n 输入比较网络表示为从 1 到 n 范围内的 c 对整数的列表。如果两个对包含一个共同的整数，则网络中相应比较器的顺序由列表中对的顺序决定。给定这个表示，描述一个 O(n + c) 时间（串行）算法来确定比较网络的深度。

在比较网络的上下文中，整数对意味着什么？通常我们使用下面的符号来表示一个比较网络，其中每条水平线代表一个数字。