c++ - GCC轮流实现

Question

我需要编写一个针对随机访问迭代器 (RAI) 高度优化的 rotate 的 C++ 实现。输入迭代器的分布是未知的。

之前看过两种常见的旋转算法:

1. 只需反转范围即可。这导致每个元素写入 2 次

template<RAI>
RAI rotate(RAI _first, RAI _middle, RAI _last) {
  std::reverse(_first, _middle);
  std::reverse(_middle, _last);
  std::reverse(_first, last);
  return _first + _last - _middle;
}

1. 让n=_last-_first和 d=_middle-_first

template<RAI>
RAI rotate(_first, _middle, _last) { 
    int GCD= gcd(d, n); 
    for (int i = 0; i < GCD; i++) { 
        int temp = *(first+i); 
        int j = i; 
        for (;;) { 
            int k = j + d; 
            if (k >= n) 
                k = k - n; 
            if (k == i) 
                break; 
            *(first+j) = std::move(*(first+k)); 
            j = k; 
        } 
        *(first+j) = temp; 
    } 
} 

奇怪的是，GCC implementation包括 GCD 的代码，甚至说它用于帮助旋转算法，但实际的旋转算法甚至从未使用过它。 GCC 旋转算法如下:

template<typename _RandomAccessIterator>
_RandomAccessIterator
__rotate(_RandomAccessIterator __first,
     _RandomAccessIterator __middle,
     _RandomAccessIterator __last,
     random_access_iterator_tag)
{
  // concept requirements
  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
              _RandomAccessIterator>)

  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;
  typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;

  _Distance __n = __last   - __first;
  _Distance __k = __middle - __first;

  if (__k == __n - __k)
  {
    std::swap_ranges(__first, __middle, __middle);
    return __middle;
  }

  _RandomAccessIterator __p = __first;
  _RandomAccessIterator __ret = __first + (__last - __middle);

  for (;;)
  {
    if (__k < __n - __k)
    {
      if (__k == 1)
      {
        _ValueType __t = _GLIBCXX_MOVE(*__p);
        _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
        *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
        return __ret;
      }
    _RandomAccessIterator __q = __p + __k;
    for (_Distance __i = 0; __i < __n - __k; ++ __i)
    {
      std::iter_swap(__p, __q);
      ++__p;
      ++__q;
    }
    __n %= __k;
    if (__n == 0)
      return __ret;
    std::swap(__n, __k);
    __k = __n - __k;
  } else  {
      __k = __n - __k;
      if (__k == 1)
      {
        _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
        _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
        *__p = _GLIBCXX_MOVE(__t);
        return __ret;
      }
      _RandomAccessIterator __q = __p + __n;
      __p = __q - __k;
      for (_Distance __i = 0; __i < __n - __k; ++ __i)
      {
        --__p;
        --__q;
        std::iter_swap(__p, __q);
      }
      __n %= __k;
      if (__n == 0)
        return __ret;
      std::swap(__n, __k);
    }
  }
}

我不明白为什么这比我上面显示的前两个更快？考虑以下部分:

_RandomAccessIterator __q = __p + __k;
for (_Distance __i = 0; __i < __n - __k; ++ __i)
{
  std::iter_swap(__p, __q);
  ++__p;
  ++__q;
}

如果k很小，那么在那个循环中，几乎每个位置都将被交换两次，而且这只是在外部 while 的一次迭代中环形。那么，这比上面大概每个位置最多只执行 2 次操作的算法快多少？

Answer 1

子列表反转实现对每个元素进行一次交换。 GCC 实现对每个元素最多 进行一次交换，但可能会更少，因为它有多个提前终止条件。

例如，在您指向的特定循环中，n-k 交换，但在那之后 n 在下一个之前减少到 k迭代，因此它满足“每个元素最多交换一次”的规则。但是，如果结果是 n 可以被 k 整除，则作业已经完成并且可以退出。