Newsgroup: it.comp.lang.c
Titolo: Ruotare un array di char

CIao!
Qualcuno ha una buona idea su come implementare in maniera efficiente
(tempo) la rotazione di un array di char?
In particolare:
- L'array ha una lunghezza fissa
- L'array non sara' modificato nel codice
- La rotazione e' di un solo carattere a destra
Ad esempio:
array: ciaomondo
array dopo la rotazione: ociaomond
Vi ringrazio per ogni aiuto :)

- L'array ha una lunghezza fissa
Nota a priori e quindi definibile nel codice.

- L'array non sara' modificato nel codice
Oltre alle eventuali rotazioni.
Ormai la mia memoria sta cadendo a pezzi! ;)


una soluzione potrebbe essere:
#include <stdio.h>
#include <stdlib.h>
#define DIM 10
void rota(char *str){
	char c;
	int i;
	c=str[DIM-2];
 
	for(i=DIM-2;i>0;i--)
		str[i]=str[i-1];
 
	str[0]=c;
	str[DIM-1]='\0';
}
 
int main (int argc ,char **argv){
	char buf[DIM]="ciaomondo\0";
 
	printf("buf:%s\n",buf);
	rota(buf);
	printf("buf:%s\n",buf);
	return 0;
}

 (tempo) la rotazione di un array di char?
Se il contenuto non e` una stringa puoi usare in modo semplice memmove
(che molto probabilmente e` ottimizzata). Se e` una stringa puoi
comunque usare memmove ricordandoti di sistemare il terminatore. A
spanne (non ho compilato):
/* Senza termintatore */
char c = array[len - 1];
memmove(array + 1, array, len - 1);
array[0] = c;
/* Con terminatore: come prima, ma lasci il terminatore al suo posto */
char c = array[len - 2];
memmove(array + 1, array, len - 2);
array[0] = c;
Luca
-- 
Home: 
http://kronoz.cjb.net
"New processes are created by other processes, just like new
 humans. New humans are created by other humans, of course,
 not by processes." -- Unix System Administration Handbook

 (tempo) la rotazione di un array di char?
Il modo più veloce per ruotare un array è.. quello di non ruotarlo affatto
;-)
Se riesci prova con delle variabili puntatore a puntare allo start/end del
vettore.. utilizzai la stessa tecnica per cyclare una palette da 256 colori
qualche annetto fà e il tempo macchina richiesto era veramente minimo.

 (tempo) la rotazione di un array di char?
Il metodo più veloce è sicuramente:
- avere un buffer abbastanza grande da contenere la stringa più n 
caratteri di rotazione.
- far si di avere la stringa allineata a destra rispetto al buffer
- nella rotazione; portare indietro il puntatore di una posizione, 
copiare l'ultimo carattere della stringa nella posizione corrente del 
puntatore e scrivere '\0' nell'ultimo carattere della stringa.
Naturalmente tutto questo ha senso se ottimizzi il codice in modo da non 
fare copie di stringhe, altrimenti tanto vale fare una rotazione normale.

 (tempo) la rotazione di un array di char?
Il metodo più veloce è sicuramente:


"FIFO" <FI...@LIFO.org> wrote

Beh, quello che chiedi e' troppo semplice e ti ha gia' risposto Kronos.
Io voglio dare invece una soluzione piu' generale:
void Rotate(char *array, int nmoves, int size)
{
   if(!nmoves) return;
   else if(!size) return;
   else if(nmoves<0) nmoves = size-(-nmoves%size);
   else if(!(nmoves%size)) return;
   char *tmp = (char*)malloc(nmoves%size);
   memmove(tmp,array+size-(nmoves%size),nmoves%size);
   memmove(array+(nmoves%size),array,size-(nmoves%size));
   memmove(array,tmp,nmoves%size);
   free(tmp);
}
questa funzione e' in grado di ruotare a destra ed a sinistra di 0, 1 o
quante posizioni tu voglia. Se hai una stringa di 10 caratteri puoi anche
ruotare tale stringa di 36 posizioni!
Prendiamo come esempio: "0123456789", e' una stringa di 10 caratteri.
Rotate(a,0,10); // proviamo a ruotare di 0 posizioni
0123456789 // originale
0123456789 // ruotata
Rotate(a,1,10); // proviamo a ruotare di 1 posizione
0123456789 // originale
9012345678
 // ruotata
Rotate(a,8,10); // proviamo a ruotare di 8 posizioni
0123456789 // originale
2345678901
 // ruotata
Rotate(a,10,10); // proviamo a ruotare di 10 posizioni
0123456789 // originale
0123456789 // ruotata
Rotate(a,36,10); // proviamo a ruotare di 36 posizioni
0123456789 // originale
4567890123 // ruotata
Rotate(a,-2,10); // proviamo a ruotare di -2 posizioni (2 a sinistra)
0123456789 // originale
2345678901
 // ruotata
Ok, ruotare di 0 posizioni non e' difficile, basta lasciare invariata la
stringa....  la stessa cosa vale per 10 posizioni, infatti ruotare di 10
posizioni e' come non ruotare affatto. Ruotare di una o otto posizioni e'
semplice, basta usare 3 memmove. Ruotare di 36 posizioni equivale a ruotare
di 6 posizioni (nmoves%size), visto che la dimensione e' 10.
In fine, ruotare di -2 posizioni, cioe' due posizioni a sinistra, equivale a
ruotare di 8 posizioni a destra (size+nmoves).
In questo modo una sola funzione puo' fare tutti i tipi di rotazioni ed in
modo abbastanza efficiente. La funzione puo' essere migliorata, ad esempio
si puo' allocare memoria in modo piu' intelligente e si possono gestire
meglio i casi particolari... beh, io ho solo dato l'idea....
Tommy

    char *tmp = (char*)malloc(nmoves%size);
scusate per il cast... ma il compilatore che avevo sotto mano si
lamentava.... ehm, anche perche' ero in modalita' C++ ;-)
Tommy

 meglio i casi particolari... beh, io ho solo dato l'idea....
Be', l'algoritmo pare buono (a patto che lo sia anche l'implementazione
della memmove...): eccolo con le mie limature e le mie fisime estetiche
(troppi return mi fanno antipatia, specie nelle funzioni void):
void Rotate (char * array, int nmoves, int size)
{
   if (array != NULL && size > 0 && (nmoves %= size) != 0)
   {
      register char * tmp;
      if (nmoves < 0)
      {
         nmoves += size;
      }
      if ((tmp = malloc(nmoves)) != NULL)
      {
         memmove(tmp, array + size - nmoves, nmoves);
         memmove(array + nmoves, array, size - nmoves);
         memmove(array, tmp, nmoves);
         free(tmp);
      }
   }
}
--
Cingar
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 (troppi return mi fanno antipatia, specie nelle funzioni void):
Ed ecco la mia versione che se tutto va bene ritorna il primo argomento,
altrimenti ritorna NULL.
char * Rotate (char * array, int nmoves, int size)
{
    if (array != NULL && size > 0 && (nmoves %= size) != 0) {
       register char * tmp;
       if (nmoves < 0)
          nmoves += size;
       if ((tmp = malloc(nmoves)) != NULL) {
          memmove(tmp, array + size - nmoves, nmoves);
          memmove(array + nmoves, array, size - nmoves);
          memmove(array, tmp, nmoves);
          free(tmp);
          return array;
       }
    }
    return NULL;
}
- Dario

 (troppi return mi fanno antipatia, specie nelle funzioni void):
questo e' vero.
Tommy

       register char * tmp;
io lascerei perdere queste ottimizzazioni inutili e mi affiderei al
optimiser.
Tommy

 C++ ed ho chiesto gia' scusa per questo.
Ma non c'è mica bisogno di scusarsi, che cappero! Stiamo rispondendo a uno
che sta imparando il C: immagino bene che tu sai già tutte queste
pignolerie, ma lui magari no.


 optimiser.
So che la keyword register viene bellamente ignorata da qualsiasi buon
compilatore moderno (perché l'ottimizzazione si basa su ben altri criteri,
automatici) ma, comunque, non fa male a nessuno metterla.
Nel caso improbabile che il sorgente venga portato su qualche processore
strano per cui esiste solo un compilatore sempliciotto, può sempre tornare
utile.
In ogni caso, serve anche come avvertimento per i tuoi colleghi: "Occhio che
questa è una delle variabili su cui si gioca l'efficienza del programma.
State ben attenti a come modificate questo pezzo di codice: non mi
introducete stupidaggini che possano rallentare l'algoritmo."
