Недавно я спросил вопрос в обзоре кода, чтобы просмотреть алгоритм сортировки с именем QuickMergeSort. Я не буду вдаваться в подробности, но в какой-то момент алгоритм выполняет внутренний слияние: вместо использования дополнительной памяти для хранения данных для слияния он меняет элементы на объединение с элементами из другой части исходной последовательности, которая не является В противном случае это не связано с слиянием. Вот часть алгоритма, который меня интересует: функция, которая выполняет слияние:
template<
typename InputIterator1,
typename InputIterator2,
typename OutputIterator,
typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare compare={})
-> void
{
for (; first1 != last1; ++result) {
if (first2 == last2) {
std::swap_ranges(first1, last1, result);
return;
}
if (compare(*first2, *first1)) {
std::iter_swap(result, first2);
++first2;
} else {
std::iter_swap(result, first1);
++first1;
}
}
// first2 through last2 are already in the right spot
}
Эта функция была адаптирована из функции eponym в реализации libС++ std::inplace_merge; эта новая версия свопит элементы с другой частью исходного массива вместо перемещения элементов из вспомогательного массива.
Поскольку слияние является внутренним, я понял, что на самом деле мне не нужно иметь два разных типа ввода: InputIterator1 и InputIterator2 всегда одинаковы. Затем я понял, что, поскольку операции с first1 и first2 всегда были одинаковыми, я мог хранить их в двухэлементном массиве и использовать результат сравнения, чтобы индексировать массив, чтобы узнать, какой итератор должен меняться и увеличивать. С помощью этого небольшого трюка я избавляюсь от ветки и получаю алгоритм с наибольшим разнесением:
template<
typename InputIterator,
typename OutputIterator,
typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
InputIterator first2, InputIterator last2,
OutputIterator result, Compare compare={})
-> void
{
InputIterator store[] = { first1, first2 };
for (; store[0] != last1; ++result) {
if (store[1] == last2) {
std::swap_ranges(store[0], last1, result);
return;
}
bool cmp = compare(*store[1], *store[0]);
std::iter_swap(result, store[cmp]);
++store[cmp];
}
// first2 through last2 are already in the right spot
}
Теперь дело в следующем: с помощью этой новой функции half_inplace_merge общий алгоритм сортировки в 1,5 раза медленнее, чем с исходным half_inplace_merge, и я понятия не имею, почему. Я пробовал несколько уровней оптимизации компилятора, несколько трюков, чтобы избежать потенциальных проблем с псевдонимом, но кажется, что проблема исходит из самого нелетящего трюка.
Итак, кто-нибудь может объяснить, почему нерасширяющийся код медленнее?
Приложение: для тех, кто хочет запустить те же тесты, что и я... ну, это будет немного сложно: я использовал тесты из личной библиотеки, которые включают много вещей; вам необходимо загрузить в библиотеку, добавить этот файл и запустить этот тест после добавления нужной строки для вызова quick_merge_sort рядом с выделенной секцией (вам нужно будет перенаправить стандартный вывод программы в файл в подкаталоге profiles). Затем вам нужно запустить этот Python script, чтобы увидеть результаты, добавив quick_merge_sort к выделенной строке. Обратите внимание, что необходимо установить NumPy и matplotlib.
