logo标签列表

一个排序网络如何能够击败通用的排序算法？

calgorithmsortingcomparisonsorting-network
15

关于如何快速排序固定长度为6的int数组，我不完全理解这个排序网络是如何比插入排序这样的算法更快的。

从该问题可以看出，下面是完成排序所需的CPU周期数的比较：

Linux 32 bits, gcc 4.4.1, Intel Core 2 Quad Q8300, -O2

  • 插入排序（Daniel Stutzbach）：1425
  • 排序网络（Daniel Stutzbach）：1080

使用的代码如下：

插入排序（Daniel Stutzbach）

static inline void sort6_insertion_sort_v2(int *d){
    int i, j;
    for (i = 1; i < 6; i++) {
            int tmp = d[i];
            for (j = i; j >= 1 && tmp < d[j-1]; j--)
                    d[j] = d[j-1];
            d[j] = tmp;
    }
}

排序网络（Daniel Stutzbach）

static inline void sort6_sorting_network_v1(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}
我了解排序网络在并行排序中非常有效，因为某些步骤与其他步骤无关。但是在这里我们没有使用并行化。
我希望它能更快，因为它知道预先确定的元素数量的优点。插入排序在哪里以及为什么会进行不必要的比较？
编辑1：
这是这些代码要与之比较的输入集：
int d[6][6] = {\
    {1, 2, 3, 4, 5, 6},\
    {6, 5, 4, 3, 2, 1},\
    {100, 2, 300, 4, 500, 6},\
    {100, 2, 3, 4, 500, 6},\
    {1, 200, 3, 4, 5, 600},\
    {1, 1, 2, 1, 2, 1}\
};\
这里输入数组的顺序是随机的吗？还是使用的降序数组？ - user191776
6个回答
20

但是在这里我们没有使用并行化。

现代CPU可以判断指令是否独立并将它们并行执行。因此，即使只有一个线程，排序网络的并行性也可以被利用。

插入排序在哪些情况下会进行不必要的比较？

最容易看到额外比较的方法是手动进行一个例子。

Insertion sort:
6 5 4 3 2 1
5 6 4 3 2 1
5 4 6 3 2 1
4 5 6 3 2 1
4 5 3 6 2 1
4 3 5 6 2 1
3 4 5 6 2 1
3 4 5 2 6 1
3 4 2 5 6 1
3 2 4 5 6 1
2 3 4 5 6 1
2 3 4 5 1 6
2 3 4 1 5 6
2 3 1 4 5 6
2 1 3 4 5 6
1 2 3 4 5 6

Sorting network:
6 5 4 3 2 1
6 4 5 3 2 1
5 4 6 3 2 1
4 5 6 3 2 1 # These three can execute in parallel with the first three
4 5 6 3 1 2 #
4 5 6 2 1 3 #
4 5 6 1 2 3
1 5 6 4 2 3
1 2 6 4 5 3
1 2 3 4 5 6
1 2 3 4 5 6
1
@Daniel：好的，由于这些路径完全不同，我们无法直接进行比较。当然，排序网络可以让我们在更少的比较次数内进行排序。换句话说，有什么阻止我们优化插入排序以使用任意数量输入的交换序列呢？ - Lazer
Lazer：恐怕我不明白。你说“这个交换序列”是指哪个序列？此外，你是想优化插入排序还是要提到排序网络？ - Daniel Stutzbach
2
@Daniel：抱歉表达不够清晰。换句话说，如果排序网络更加高效，为什么我们还要使用插入排序算法呢？ - Lazer
3
@Lazer: 啊，那样更有意义了。 :-) 感谢澄清！排序网络的问题在于它们只适用于固定的n。此外，它们仅在n较小时实用，因为您必须手动编写所有比较和交换，并且将有O(nlogn)个操作。它们之所以快速，部分原因是代码被写出来并且没有循环，因此速度与限制密不可分。 - Daniel Stutzbach
@Daniel：那么，您的意思是说没有一种好的方法来编写程序以生成要执行的交换集（用于网络排序）任何n吗？为什么排序网络适用于固定的n？不能泛化吗？ - Lazer
2
@Lazer：是的，那就是我的意思。如果一个算法使用变量n，它需要在某个地方有一种循环。排序网络没有循环。你可以编写一个程序来生成交换操作，然后执行它们，但是生成这些交换操作将耗费比使用排序网络节省的时间更多的时间。你能做到的最接近的方法是使用像MergeSort或QuickSort这样的递归算法，并将排序网络用作基本情况。 - Daniel Stutzbach
4
更好的问题是为什么排序网络只比插入排序（通常非常慢）快大约50％。答案是当n很小的时候，大O并不重要。至于OP的问题，Daniel给出了最好的答案。
即使你有1000000个微小的排序，即使只有一点点的差异也会产生变化，这仍然非常重要！ - Den Roman
1
@DenRoman：当你有1000000个小排序时，大O并不重要，相反，在这种情况下，常数因子才是重要的。 - R.. GitHub STOP HELPING ICE
1

我认为展开循环是导致排序网络算法结果更快的原因。

1

我相信并行算法和串行算法中所做的'工作'量几乎总是相同的。只不过由于工作得到分配，你会更快地得到输出结果。我认为，只有当输入数据的大小足够大以证明使用并行算法时，你才会更快地获得令人信服的输出结果。

对于插入排序，将数组划分到处理器之间形成一个管道，需要一些时间来填充管道，然后才能产生并行算法的好处。

0
理论上，如果编译器能够完全展开插入排序中的循环，那么代码可能会差不多。第一个循环可以轻松展开，而第二个循环则不能轻松展开。
还有一种情况是，由于代码不像网络排序代码那样简单，因此编译器可以进行较少的优化。我认为，在插入排序中存在更多的依赖关系，这可能在编译器尝试优化代码时产生很大的差异（如果我错了，请纠正我）。
0

我认为你所有的问题都在Daniel Stutzbach对原帖的回答中得到了解答：

你发布的算法类似于插入排序，但看起来你最小化了交换次数，却增加了比较次数。然而，比较要比交换更昂贵，因为分支可能会导致指令流水线停顿。

你不能做出那个概括性的断言。如果你的数据对象很大但提取和比较键是快速的，那么比较操作要比交换操作更便宜。我猜想只有在数据元素是简单类型时，交换操作才更便宜。 - R.. GitHub STOP HELPING ICE
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接