15

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

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

Linux 32 位，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}\
};\
4

6 回答 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
于 2010-10-10T16:34:37.710 回答
4

更好的问题是为什么排序网络只比插入排序（通常是一种非常慢的排序）高出约 50%。答案是 big-O 在n很小的时候并不那么重要。至于OP的问题，丹尼尔有最好的答案。

于 2010-10-10T17:48:45.860 回答
1

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

于 2010-10-10T16:32:21.740 回答
1

我相信并行算法和串行算法完成的“工作量”总是几乎相同。只有这样，由于工作得到分配，您才能更快地获得输出。如果输入的大小足以证明使用并行算法的合理性，我认为你会更快地获得令人信服的输出。

如果在处理器之间进行数组的插入排序划分，它会形成一个管道，并且需要一些时间来填充管道，然后它会产生并行算法的好处。

于 2010-10-10T17:00:24.920 回答
0

理论上，如果编译器可以完全展开插入排序中的循环，则代码可能大致相同。第一个循环可以很容易地展开，而第二个循环不能那么容易展开。

也可能是这样，因为代码不像网络排序代码那么简单，编译器可以做的优化较少。我认为插入排序中的依赖关系比网络排序中的更多，这在编译器尝试优化代码时可能会产生很大的不同（如果我错了，请纠正我）。

于 2010-10-10T16:33:11.317 回答
0

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

您发布的算法类似于插入排序，但看起来您以更多比较为代价最小化了交换次数。但是，比较比交换要昂贵得多，因为分支会导致指令流水线停止。

于 2010-10-10T16:35:45.617 回答