Как сеть сортировки превосходит универсальные алгоритмы сортировки?

Что касается самого быстрого вида массива int с фиксированной длиной 6, я не совсем понимаю, как эта сеть сортировки превосходит алгоритм, подобный сортировке вставкой.

В этом вопросе приведено сравнение количества циклов ЦП, использованных для завершения сортировки:

Linux 32 бита, gcc 4.4.1, Intel Core 2 Quad Q8300, -O2

  • Сортировка вставок (Даниэль Штутцбах): 1425
  • Сортировка сетей (Даниэль Штутцбах): 1080

Используемый код выглядит следующим образом:

Сортировка вставок (Даниэль Штутцбах)

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;
    }
}

Сортировка сетей (Даниэль Штутцбах)

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
}

Я понимаю, что сети сортировки действительно хороши для параллельной сортировки, потому что некоторые этапы не зависят от других этапов. Но здесь мы не используем распараллеливание.

Я ожидаю, что это будет быстрее, так как имеет преимущество в том, что заранее знает точное количество элементов. Где и почему именно сортировка вставок делает ненужные сравнения?

EDIT1:

Это входной набор, с которым сравниваются эти коды:

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}\
};\
Источник

6 ответов

Решение

Но здесь мы не используем распараллеливание.

Современные процессоры могут выяснить, когда инструкции являются независимыми, и выполнять их параллельно. Следовательно, даже если существует только один поток, параллелизм сортировочной сети может быть использован.

Где именно сортировка вставок делает ненужные сравнения?

Самый простой способ увидеть дополнительные сравнения - это сделать пример вручную.

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
Источник

Лучший вопрос заключается в том, почему сеть сортировки превосходит сортировку вставкой (обычно очень медленную сортировку) на ~50%. Ответ в том, что big-O не так важен, когда n крошечный Что касается вопроса ОП, у Даниэля лучший ответ.

Источник

Я думаю, что раскручивание цикла - то, что вызывает более быстрые результаты на алгоритме сортировки сети

Источник

Я считаю, что объем "работы", выполненной в параллельном алгоритме и последовательном алгоритме, всегда почти одинаков. Только потому, что работа распределяется, вы получаете результаты быстрее. Я думаю, что вы получите убедительно более быстрый вывод в случае, если размер ввода будет достаточным, чтобы оправдать использование параллельного алгоритма.

В случае вставки сортировка массива между процессорами такова, что он формирует конвейер, и заполнение конвейера займет некоторое время, а затем получит преимущества параллельного алгоритма.

Источник

Я думаю, что все ваши вопросы даны в ответе Даниэля Штутцбаха на оригинальный пост:

Алгоритм, который вы опубликовали, похож на сортировку вставкой, но похоже, что вы свели к минимуму количество свопов за счет большего количества сравнений. Сравнения намного дороже, чем свопы, потому что ветки могут привести к остановке конвейера команд.

Источник

Теоретически код мог бы быть примерно таким же, если бы компилятор мог полностью развернуть циклы в сортировке вставок. Первый цикл может быть легко развернут, в то время как второй не может быть развернут так просто.

Может также случиться так, что, поскольку код не так прост, как код сетевой сортировки, компилятор может выполнять меньше оптимизаций. Я думаю, что в сортировке вставок больше зависимостей, чем в сетевой сортировке, что может иметь большое значение, когда компилятор пытается оптимизировать код (поправьте меня, если я ошибаюсь).

Источник
Другие вопросы по тегам