Две близкие последовательности дают различную производительность на сортировке оболочек - PullRequest
Новая
       28

Две близкие последовательности дают различную производительность на сортировке оболочек

0 голосов
/ 28 декабря 2018

Вопрос

Я обнаружил, что две близкие последовательности имеют большое различное число сравнений на сортировке оболочек.

Первая последовательность - это последовательность Фибоначчи.

F (0) = 1, F (1) = 2

F (n) = F (n - 1) + F (n - 2), n> 1

Вторая последовательность:

G (0) = 1

G (n) = F (n + 2) + (-1)^ n, n> 0

Почему вторая последовательность имеет гораздо меньшее количество сравнений на шелл сортировке, чем первая последовательность?

Тест

Я написал тест длязаписать среднее количество сравнений и относительных отклонений для разных видов алгоритма сортировки.Тестовые случаи включают случайные случаи, упорядоченные случаи и обратные упорядоченные случаи.Кроме того, я добавил std :: sort и std :: sort_heap, чтобы обеспечить базовую линию теста.

Код Shellsort 

template<class Iterator, class Compare, class T, T ...Seq>
constexpr void sort_impl(Iterator first, Iterator last, Compare comp, const T size, std::integer_sequence<T, Seq...>) noexcept {
    for (const auto gap : {Seq...}) {
        if (size > gap) {
            const auto h = first + gap;
            for (auto i = h; i < last; i++) {
                if (comp(*i, *(i - gap))) {
                    auto v = std::move(*i);
                    auto j = i;

                    do {
                        *j = std::move(*(j - gap));
                        j -= gap;
                    } while (j >= h && comp(v, *(j - gap)));

                    *j = std::move(v);
                }
            }
        }
    }
}

Вывод с размером массива 10000000 

random integer array
       fib shell sort   cmp:  1325095023.99 (± 3.73%)
 fib fuzzy shell sort   cmp:   572594719.24 (± 1.40%)
             std sort   cmp:   281854794.48 (± 1.17%)
        std sort heap   cmp:   236300381.92 (± 0.00%)

ascend integer array
       fib shell sort   cmp:   315842185.00 (± 0.00%)
 fib fuzzy shell sort   cmp:   295842191.00 (± 0.00%)
             std sort   cmp:   316531837.00 (± 0.00%)
        std sort heap   cmp:   238288048.00 (± 0.00%)

descend integer array
       fib shell sort   cmp:   353359827.00 (± 0.00%)
 fib fuzzy shell sort   cmp:   339869035.00 (± 0.00%)
             std sort   cmp:   222097162.00 (± 0.00%)
        std sort heap   cmp:   240430389.00 (± 0.00%)
...