Вращение на месте C ++ Практика

Question

У меня есть рабочая вращающаяся функция для моего массива "items" int. Код ниже делает это, за исключением того, что я передаю значения без необходимости. Я пытаюсь добиться вращения "на месте". Под этим я подразумеваю, что ptrs будет увеличиваться или уменьшаться вместо того, чтобы извлекать значения из массива. По этому мне нужно «повысить» уровень эффективности для этого метода. Любые предложения?

void quack::rotate(int nRotations)
{
 if ( count <= 1 ) return;
 else  // make sure our ptrs are where we want them.
 {
  intFrontPtr = &items[0].myInt;
  intBackPtr  = &items[count-1].myInt;
 }
 for (int temp = 0; nRotations != 0;)
 {
  if ( nRotations > 0 )
  {
     temp = *intFrontPtr;
    *intFrontPtr = *intBackPtr;
    *intBackPtr  = temp; // Connect temps for the rotation
   --intBackPtr; // Move left [...<-] into the array
  }
  else if ( nRotations < 0 ) 
  {
   temp = *intBackPtr;
   *intBackPtr  = *intFrontPtr;
   *intFrontPtr = temp; // Connect temps for the rotation
   ++intFrontPtr; // Move right [->...] into the array
  }
  if ( intBackPtr  == &items[0].myInt  || 
    intFrontPtr == &items[count-1].myInt ) 
  {
   intFrontPtr = &items[0].myInt; 
   intBackPtr  = &items[count-1].myInt; // need to re-set
   if ( nRotations > 0 ) nRotations--;  // Which ways did we rotate?
   else nRotations++;
  }
 }
 }

О, да, я пытаюсь попрактиковаться в с ++ и знаю, что их множество функций, которые уже запрограммированы для этого ... Я пытаюсь "создать свой собственный". Я думаю, что у меня есть это синтаксически, но эффективность всегда там, где я борюсь. Как новичок, я был бы очень признателен за критику в этом направлении.

Answer 1

Существует старый трюк для вращения элементов в массиве (я впервые увидел его в программировании жемчужин)

Скажем, вы хотите повернуть массив влево на три элемента.

Сначала поменяйте местами первые три элемента, затем поменяйте местами оставшиеся элементы, а затем полностью разверните весь массив.

Starting Array:
1 2 3 4 5 6 7

After reversing the first three elements
3 2 1 4 5 6 7

After reversing the remaining elements
3 2 1 7 6 5 4

Finally reverse the entire array to get the final rotated array
4 5 6 7 1 2 3

Реверсирование частей массива может быть выполнено на месте, поэтому вам не нужна дополнительная память.

Answer 2

Вы можете оставить данные на месте и иметь элемент «базовый индекс», чтобы указать, где должен начинаться массив. Затем вам нужно использовать это для корректировки индекса при доступе к массиву. Сам массив должен быть закрытым, и доступ к нему осуществляется только через функции доступа, которые выполняют настройку. Примерно так:

class quack
{
public:
    explicit quack(int size) : items(new Item[size]), size(size), base(0) {}
    ~quack() {delete [] items;}

    void rotate(int n)      {base = (base + n) % size;}
    Item &operator[](int i) {return items[(base + i) % size];}

private:
    quack(quack const&) = delete;          // or implement these if you want
    void operator=(quack const&) = delete; // the container to be copyable

    Item *items;
    int   size;
    int   base;
};

хотя я бы назвал это чем-то вроде RotatableArray, а не quack.

Answer 3

Как обычно, если вам действительно нужно физически вращать элементы, правильный ответ для C ++ будет использовать std::rotate, который делает именно то, что вы хотите.

Если вам нужно реализовать это вручную (в качестве практического задания), взгляните на эти слайды для алгоритмов из книги «Программирование жемчужин» Джона Бентли.

Answer 4

делать повороты один за другим на самом деле не путь. Если вы делаете что-то больше, чем на 2 или 3 оборота, оно становится очень медленным и очень быстрым.

редактирование: как заключительная мысль ... помещение элементов в (двойной) связанный «зацикленный» список (так, чтобы последний элемент указывал на первый), потребовало бы для поворота, чтобы перемещать указатель головы только на несколько элементов. (Указатель заголовка является указателем, указывающим, какой элемент в зацикленном списке является началом).

это, безусловно, самый быстрый (и самый простой) способ поворота списка элементов

Answer 5

Существует много способов вращения массива на d мест.

1. Алгоритм блочного обмена.
2. Алгоритм жонглирования.
3. Алгоритм обращения.

Ссылка ниже от Programming Pearls pdf. Проверь это. Объясняется очень четко с кодом.

http://www.cs.bell -labs.com / см / CS / жемчуг / s02b.pdf

Answer 6

https://stackoverflow.com/q/17119000/2383578: Это несколько похоже на то, что обсуждается здесь. Вращение массива на определенную величину.

Answer 7

Вот код для sdtom решения

void rotateArray(int arr[], int low, int high)
{
    while  (low<high) {
        int temp = arr[low];
        arr[low]=arr[high];
        arr[high]=temp;
        low++;
        high--;
    }
}
void rotate (int arr[], int k,int uperLimit)
{
    rotateArray(arr,0,k);
    rotateArray(arr,k+1,uperLimit-1);
    rotateArray(arr,0,uperLimit-1);

}

Answer 8

Вот тот, который я получил, изменив код здесь :

template<class It>
It rotate(It begin, It const middle, It end)
{
    typename std::iterator_traits<It>::difference_type i = 0, j;
    if (begin != middle && middle != end)
    {
        while ((i = std::distance(begin, middle)) !=
               (j = std::distance(middle,   end)))
        {
            It k = middle;
            std::advance(
                k,
                std::max(typename std::iterator_traits<It>::difference_type(),
                j - i));
            std::swap_ranges(k, end, begin);
            if (i > j) { std::advance(begin, j); }
            else { std::advance(end, -i); }
        }
    }
    return std::swap_ranges(middle - i, middle, middle);
}

Answer 9

У меня может быть альтернативное решение для вращения массива в строке. В отличие от старого трюка с перестановкой наборов элементов, как предлагалось ранее, этот подход работает следующим образом:

Инициализация:

(Примечание q = величина смещения влево, n = длина массива)

1. Определите первый элемент источника, который расположен в x1 = q% n
2. Элемент назначения имеет х2 = 0
3. char, ch1, является элементом ar [x1]
4. char, ch2, является элементом ar [x2]

Цикл от i = 0 до n-1, где n = длина массива

1. Перезаписать целевой элемент ar [x2] с помощью ch1
2. Set ch1 = ch2
3. Set x1 = x2
4. Set x2 = x2 - q
5. Если x2 отрицательно из-за вышеуказанного вычитания, добавьте к нему n
6. ch2 = ar [x2]

Следующее может помочь объяснить, как это работает.

Пример, повернуть влево на 2 символа:

a b c d e f g

c d e f g a b

x1    ch1    x2    ch2
2     c      0     a
0     a      5     f
5     f      3     d
3     d      1     b
1     b      6     g
6     g      4     e
4     e      2     c

Как видите, для этого требуется не более n итераций, поэтому алгоритм линейного времени также вращает inline (не требует дополнительной памяти, кроме нескольких временных переменных).

Вот функция, которая реализует описанный выше алгоритм, поэтому вы можете попробовать его:

void rotate(char *ar, int q)
{
    if (strlen(ar) < 2)
    {
        return;
    }

    if (q <= 0)
    {
        return;
    }

    char ch1;
    char ch2;
    int x1;
    int x2;
    int i;
    int n;

    n = strlen(ar);

    q %= n;

    if (q == 0)
    {
        return;
    }

    x1 = q;
    ch1 = ar[x1];
    x2 = 0;
    ch2 = ar[x2];

    for (i=0;i<n;i++)
    {
        ar[x2] = ch1;
        ch1 = ch2;

        x1 = x2;

        x2 -= q;

        if (x2 < 0)
        {
            x2 += n;
        }

        ch2 = ar[x2];
    }
}

Answer 10

Действительно, способ сделать это - использовать указатели вместо указателей.

int to = 0;
int from = (to + nRotations) % count;
if (to == from)
    return;

for (int i=0; i < count; i++) {
   swap(from, to);
   from = advance(from);
   to = advance(to);
}

// ...
static inline int advance(int n, int count) { return (n + 1) % count; }