为什么std ::旋转这么快？

Question

为什么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个int元素排序1000个向量.使用的排序std::rotate需要0.376秒,而另一个需要8.181秒.

为什么是这样？我不打算尝试做出比STL功能更好的东西,但我仍然很好奇.

Answer 1

正如评论员已经说过的那样,这取决于您的标准库实施.但是,即使对于前向迭代器,您发布的代码也是有效的.因此,它只需要很少的要求(只有这些迭代器可以递增和解除引用).

Stepanov的经典编程元素将整个章节(10)用于rotate和其他重新排列算法.对于前向迭代器,代码中的一系列交换提供了O(3N)分配.对于双向迭代器,三次连续调用以reverse产生另一种O(3N)算法.对于随机访问迭代器,std::rotate可以通过为起始迭代器O(N)定义索引的排列来实现为赋值first.

所有上述算法都是就地的.使用内存缓冲区,随机访问版本可能受益于更高的缓存局部性memcpy()或memmove()(如果基础值类型是POD),其中可以交换整个连续内存块.如果插入排序是在阵列上完成的std::vector,则标准库很可能会利用此优化.

TL; DR:信任您的标准库,不要重新发明轮子!

Answer 2

编辑:

由于没有给出上下文,因此不清楚您的代码是否调用std::swap()或其他swap(a,b)算法

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

当a和b是int每个1000 秒的向量时,这将复制所有向量元素3次.std::swap()容器的专用版本,比如std::vector<T>调用容器a.swap(b)方法,实质上只交换容器的动态数据指针.

此外,对于不同的迭代器类型,std::rotate()实现可以使用一些优化(请参阅下面的旧版,可能误导性的答案).

警告:std::rotate()实现依赖于实现.对于不同的迭代器类别,可以使用不同的算法(例如,__rotate(在bits/stl_algo.hGNU 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)算法,称为"翻转手".根据Jon Bentley的书" Programming Pearls",它在早期的UNIX编辑器中用于移动文本:

将双手放在你面前,一个放在另一个上面,竖起大拇指.现在

1. 转一只手.
2. 转向另一个.
3. 转动两者,相互连接.

在代码中:

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

对于随机访问迭代器,可以通过swap_ranges()(或memmove()POD类型的操作)重新定位大块内存.

通过利用汇编程序操作的微优化可以提供少量额外的加速度,它可以在禁食算法之上完成.

使用连续元素而不是在存储器中"跳转"的算法也导致现代计算机体系结构上的较少数量的高速缓存未命中.