Почему std :: вращается так быстро?

Почему std::rotate намного быстрее, чем эквивалентная функция, описанная cplusplus.com?

Внедрение cplusplus.com:

template <class ForwardIterator>
  void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
{
  ForwardIterator next= middle;

  while (first != next)
  {
    swap (*first++, *next++);

    if(next == last)
        next= middle;
    else if (first==middle)
        middle= next;
  }
}

У меня есть два алгоритма сортировки вставки, которые полностью идентичны, за исключением того, что один использует std::rotate, а один использует эквивалентную функцию cplusplus.com. Я устанавливаю их для сортировки 1000 векторов с 1000 элементами int. Сорт, который использует std::rotate занимает 0,766 секунды, а другой - 8,181 секунды.

Почему это? Я не собираюсь пытаться сделать что-то лучше, чем функции STL, но мне все еще интересно.

Ответ 1

Редактировать:

Поскольку контекст не задан, неясно, вызывает ли ваш код std::swap() или другой алгоритм swap(a,b), например

T tmp = a; a = b; b = tmp;

Когда a и b являются векторами по 1000 int каждый, это будет копировать все векторные элементы 3 раза. a.swap(b) версия std::swap() для контейнеров, таких как std::vector<T> вместо этого вызывает метод a.swap(b) контейнера, по существу заменяя только указатели динамических данных контейнеров.

Кроме того, для разных типов итераторов реализация std::rotate() может использовать некоторые оптимизации (см. Мой старый, возможно, вводящий в заблуждение ответ ниже).

Caveat: Реализация std::rotate() зависит от реализации. Для разных категорий итераторов могут использоваться различные алгоритмы (например, искать __rotate( в заголовке bits/stl_algo.h GNU g++).

Чтобы сдвинуть n элементов на m=std::distance(first,middle) простой (наивный) алгоритм, такой как m вращений одним элементом, требует O (n * m) операций перемещения или копирования. Но нужны только движения O (n), когда каждый элемент находится непосредственно в его правильном положении, что приводит к (примерно) m раз быстрее алгоритму.

Пример для иллюстрации: Поверните строку s = "abcdefg" тремя элементами:

abcdefg : store 'a' in temporary place
dbcdefg : move s[3] to s[0] (where it belongs in the end, directly)
dbcgefg : move s[6] to s[3]
dbcgefc : move s[9%7] to s[6] (wrapping index modulo container size: 9%7 == 2)
dbfgefc : move s[5] to s[2]
dbfgebc : move s[1] to s[5] (another wrapping around)
defgebc : move s[4] to s[1]
defgabc : move 'a' from temporary place to s[4]

Для n и m с наибольшим общим делителем 1 вы делаете это сейчас. В противном случае вам нужно повторить эту схему n/m время для первых m последовательных элементов (n > m принятых здесь). Этот более сложный алгоритм выполняется намного быстрее.

Для двунаправленных итераторов можно использовать еще один легендарный алгоритм O (3n), называемый "перевернутыми руками". Согласно книге Джона Бентли " Программирование жемчуга", она использовалась в ранних редакторах UNIX для перемещения текста:

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

Поверните одну руку.
Поверните другое.
Поверните оба, подключенных друг к другу.

В коде:

reverse(first, middle);
reverse(middle, last);
reverse(first, last);

Для итераторов с произвольным доступом большие куски памяти могут быть перемещены с помощью swap_ranges() (или memmove() для типов POD).

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

Алгоритмы, использующие последовательные элементы вместо "прыжков вокруг" в памяти, также приводят к меньшему количеству промахов кэш-памяти на современных компьютерных архитектурах.

Ответ 2

Как уже отмечали комментаторы, это зависит от реализации стандартной библиотеки. Но код, который вы опубликовали, действительно даже для форвардных итераторов. Таким образом, он предъявляет очень мало требований (только эти итераторы могут быть увеличены и разыменованы).

Классические Элементы программирования Степанова посвящают целую главу (10) rotate и другим алгоритмам перегруппировки. Для форвардных итераторов серия свопов в вашем коде дает задания O(3N). Для двунаправленных итераторов три последовательных вызова для reverse выхода дают еще один алгоритм O(3N). Для случайных итераторов доступа, std::rotate может быть реализован в виде O(N) назначения путем определения перестановки индексов WRT к исходному итератора first.

Все вышеуказанные алгоритмы на месте. Используя буфер памяти, возможно, что версия произвольного доступа может извлечь выгоду из большей локальности кэша memcpy() или memmove() (если базовый тип значения - POD), в котором могут быть заменены целые блоки смежной памяти. Если сортировка вставки выполняется в массиве или std::vector, вполне вероятно, что ваша стандартная библиотека воспользуется этой оптимизацией.

TL; DR: доверяйте своей стандартной библиотеке и не заново изобретайте колесо!