为什么std :: rotate这么快？ [英] Why is std::rotate so fast?

问题描述

为什么 std :: rotate 比cplusplus.com描述的等效函数快得多？

Why is std::rotate so much faster than the equivalent function that cplusplus.com describes?

cplusplus.com的实现：

cplusplus.com's implementation:

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个 int 元素对1000个向量进行排序。使用 std :: rotate 的排序花费0.376秒，而其他花费8.181秒。

I have two insertion sorting algorithms which are entirely identical, with the exception that one uses std::rotate, and one uses cplusplus.com's equivalent function. I'm setting them to sort 1000 vectors with 1000 int elements. The sort which uses std::rotate takes 0.376 seconds, and the other takes 8.181 seconds.

这是为什么？我不打算尝试做一些比STL函数更好的东西，但我仍然很好奇。

Why is this? I'm not intending to try and make something better than the STL functions but I'm still curious.

推荐答案

编辑：

由于未提供上下文，因此不清楚您的代码是否调用 std :: swap（）或其他 swap（a，b）算法，例如

Since the context is not given, it is not clear if your code calls std::swap() or another swap(a,b) algorithm like

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

当 a 和 b 是每个1000个 int s的向量，这将复制所有向量元素3次。 std :: swap（）的专用版本，例如 std :: vector< T> 的容器，称为容器<而是使用code> a.swap（b）方法，实际上只交换容器的动态数据指针。

When a and b are vectors of 1000 ints each, this would copy all vector elements 3 times. The specialized version of std::swap() for containers like std::vector<T> call the container a.swap(b) method instead, essentially swapping only the dynamic data pointers of the containers.

另外，对于不同的迭代器类型， std :: rotate（）实现可以利用一些优化（请参阅下面的较旧的，可能引起误解的答案）。

Also, for different iterator types the std::rotate() implementation can utilize some optimizations (see my older, possibly misleading answer below).

注意： std :: rotate（）的实现取决于实现。
对于不同的迭代器类别，可以使用不同的算法
（例如，在 bits / stl_algo.h中查找 __ rotate（ / code> GNU g ++的标头）。

Caveat: The implementation of std::rotate() is implementation-dependent. For different iterator categories, different algorithms can be utilized (e.g. look for __rotate( in bits/stl_algo.h header of GNU g++).

将 n 个元素移动 m = std :: distance（first，middle）一种简单（天真）的算法，例如m个旋转一个元素需要 O（n * m）移动或复制操作。但是，当每个元素直接放置到正确位置时，只需要 O（n）个移动，这将使算法的速度（大约）快 m 倍。

To shift n elements by m=std::distance(first,middle) a simple (naive) algorithm like m rotations by one element needs O(n*m) moving or copying operations. But only O(n) moves are needed, when each element is directly placed to its right position, which results in a (roughly) m times faster algorithm.

一个示例：将字符串 s = abcdefg 旋转三个元素：

An example for illustration: Rotate a string s = "abcdefg" by three elements:

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现在完成。否则，您必须为第一个 m 个连续元素重复该方案 n / m 时间（ n> m 在这里假设）。
这个稍微复杂一点的算法要快得多。

For n and m with greatest common divisor 1 you are done now. Otherwise you have to repeat that scheme n/m time for the first m consecutive elements (n > m assumed here). This little more complicated algorithm is much faster.

对于双向迭代器，可以使用另一种传说中的O（3n）算法，称为作为翻转手。根据乔恩·本特利（Jon Bentley）的书编程珍珠 ，它用于早期的UNIX编辑器用于移动文本：

For bidirectional iterators another legendary O(3n) algorithm can be used, referred to as "flipping hands". According to Jon Bentley's book Programming Pearls it was used in early UNIX editors for moving text:

将您的手放在您的面前，一个放在另一个之上，竖起大拇指。现在

Place your hands in front of you, one above the other, thumbs up. Now

1. 一只手。


2. 另一只手。


3. 将两者都连接在一起。

在代码中：

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

对于随机访问迭代器，大​​块内存可以通过 swap_ranges（）（或POD类型的 memmove（）操作）。

For random access iterators large chunks of memory can be relocated by swap_ranges() (or memmove() operations for POD types).

利用汇编程序进行微优化可以带来少量额外的加速，这可以在禁食算法的基础上完成。

Microoptimization by utilising assembler operations can give a small extra amount of acceleration, it can be done on top of the fasted algorithm.

使用连续元素而不是在内存中跳来跳去也会导致现代计算机体系结构上的高速缓存未命中次数减少。

Algorithms using consecutive elements instead of "hopping around" in memory also result in smaller number of cache misses on modern computer architectures.

这篇关于为什么std :: rotate这么快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！