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

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

14 голосов
/ 10 октября 2010

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

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

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 ]

19 голосов
/ 10 октября 2010

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

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

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

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

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
4 голосов
/ 10 октября 2010

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

1 голос
/ 10 октября 2010

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

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

1 голос
/ 10 октября 2010

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

0 голосов
/ 10 октября 2010

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

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

0 голосов
/ 10 октября 2010

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

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

...