In Place rotation C++ Practice

Question

Ho una funzione di rotazione funzionante per il mio array int "items". Il codice qui sotto lo fa, tranne che im trasferire valori inutilmente. Sto cercando di ottenere la rotazione "inplace". Quello che intendo è che i ptrs aumenterebbero o diminuiranno invece di prendere i valori dall'array. Con quale ho bisogno di "alzare" il livello di efficienza in questo modo per questo metodo .. Qualche suggerimento?

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

Oh sì, Im cercando di praticare C++ e conoscere loro sono molte funzioni che galleggiano intorno che sono programmati per fare questo già ... Im cercando di "costruire il mio". Penso di aver capito sinteticamente, ma l'efficienza è sempre dove faccio fatica. Come, un novizio, Io apprezzo molto maggiori critiche nei confronti di questo aspetto ..

Answer 1

facendo le rotazioni uno per uno non è davvero la strada da percorrere. Se stai facendo qualcosa di più di 2 o 3 rotazioni diventa veramente lento molto veloce.

modifica: come un pensiero finale ... inserendo gli elementi in una (doppia) lista collegata "in loop" (quindi l'elemento finale punta al primo), richiederebbe una rotazione per spostare solo il puntatore a pochi elementi. (Il puntatore capo è un puntatore per indicare quale elemento nella lista ciclica è l'inizio).

questo è di gran lunga il modo più veloce (e più facile) di fare una rotazione in un elenco di elementi

Answer 2

C'è un vecchio trucco per gli elementi rotanti in un array (ho visto la prima volta in perle di programmazione)

Dire di voler ruotare una schiera a sinistra di tre elementi.

Prima invertire i primi tre elementi, accanto invertire i rimanenti elementi, e poi invertire l'intero array.

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 

porzioni di inversione della matrice può essere fatto sul posto in modo che non è necessario alcun ulteriore memoria.

Answer 3

È possibile lasciare i dati sul posto, e hanno un "indice di base" membro per indicare dove l'array dovrebbe iniziare. È quindi necessario utilizzarlo per regolare l'indice quando si accede alla matrice. La matrice stessa deve essere privata e accessibile solo tramite le funzioni di accesso che eseguono la regolazione. Qualcosa di simile a questo:

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

anche se io chiamerei qualcosa come RotatableArray, piuttosto che quack.

Answer 4

In realtà il modo per farlo è utilizzare gli indici anziché i puntatori.

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

Come al solito, se davvero hanno ruotare fisicamente gli elementi, la risposta corretta per C++ sarebbe quella di utilizzare std::rotate, che fa esattamente quello che vuoi fare.

Se è necessario implementarlo manualmente (come compito pratico), dare un'occhiata a questi slides per gli algoritmi di "Perle di programmazione" di John Bentley.

Answer 6

Posso avere una soluzione alternativa per ruotare l'array in linea.Piuttosto che il vecchio trucco di invertire insiemi di elementi, come proposto in precedenza, questo approccio funziona come segue:

inizializzazione:

(Nota q = quantità di spostamento a sinistra, n = lunghezza della matrice)

1. Determinare il primo elemento di origine, che si trova a x1 = q% n
2. l'elemento di destinazione è a x2 = 0
3. char, ch1, AR elemento
4. char, ch2 [x1] , AR elemento

Loop [x2] su i = da 0 a n-1, dove n = lunghezza della matrice

1. sovrascrivere l'elemento di destinazione, ar [x2] con ch1
2. Set ch1 = ch2
3. Set x1 = x2
4. Set x2 = x2 - q
5. Se x2 è negativo a causa della sottrazione di cui sopra, aggiungere ad essa n
6. ch2 = ar [x2]

Quanto segue può aiutare a spiegare come funziona.

Esempio, ruotare a sinistra di 2 caratteri:

abcdefg

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 

Come si può vedere, questo richiede non più di n iterazioni, quindi è algoritmo di tempo lineare che ruota anche in linea (non richiede alcuna memoria aggiuntiva oltre alle poche variabili temporanee).

Ecco una funzione che implementa l'algoritmo di cui sopra in modo da poter provare:

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

Ecco quello che ho ottenuto modificando il codice 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

Ecco il codice per sdtom soluzione

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 : Questo è in qualche modo simile a quanto discusso qui. Rotazione dell'array di una determinata quantità.

Answer 10

Esistono molti modi per eseguire la rotazione degli array di d posizioni.

1. Algoritmo di scambio di blocchi.
2. Algoritmo di giocoleria.
3. Algoritmo di inversione.

Il collegamento di seguito è da Perle di programmazione pdf. Controllalo.Spiegato molto chiaramente con il codice.

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