GCC повернуть реализацию - PullRequest
Новая
       10

GCC повернуть реализацию

0 голосов
/ 24 мая 2019

Мне нужно написать реализацию rotate для C ++, которая оптимизирована для итераторов с произвольным доступом (RAI). Распределение входных итераторов неизвестно.

Я видел два распространенных алгоритма вращения:

  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 включает в себя код для 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 операций на позицию?

1 Ответ

1 голос
/ 24 мая 2019

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

В конкретном цикле, на который вы указываете, например, выполняется n-k свопинг, но после этого n уменьшается до k перед следующей итерацией, поэтому он удовлетворяет "не более одного свопа для каждого элемента" править. Если оказалось, что n делится на k, то задание уже выполнено и оно может завершиться.

...