In Place rotation C++ Practice

Question

У меня есть работающая вращающаяся функция для моего массива int. Приведенный ниже код делает это, за исключением того, что im передает значения без необходимости. Я пытаюсь добиться поворота «на место». То, что я имею в виду, это то, где 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++; 
    } 
} 
} 

Ах да, я пробую на практике C++ и знаю их много функций, плавающие вокруг, которые запрограммированы, чтобы сделать это уже ... Im пытаясь «построить свой». Я думаю, что я получил это синтаксически, но эффективность всегда там, где я борюсь. Будучи новичком, я был бы очень благодарен за этот аспект.

Answer 1

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

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

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

Answer 2

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

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

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

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 3

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

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 4

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

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; } 

Answer 5

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

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

Answer 6

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

Initialization:

(Примечание д = сумма сдвиг влево, п = длина массива)

1. Определить первый исходный элемент, который расположен на х1 = д% п
2. элемент назначения при x2 = 0
3. полукокса, CH1, является элементом ар [x1]
4. символ, ch2 , Является ар элементом [х2]

петли на I = 0 до N-1, где п = длина массива

1. Перезапишите элемент назначения, ар [x2] с ch1
2. Установите CH1 = ch2
3. Набор x1 = x2
4. Набор х2 = х2 - д
5. Если х2 является отрицательным из-за выше вычитания, добавить к нему п
6. ch2 = ar [x2]

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

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

АБВГДЕЖ

cdefgab

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 

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

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

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 7

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

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 8

Вот код 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 9

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

Answer 10

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

1. Алгоритм замены блоков.
2. Жонглирование Алгоритм.
3. Реверсивный алгоритм.

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

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf