manière optimale pour effectuer une opération de décalage sur un tableau

Question

Supposons que j'ai un tableau

unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9}; 

est-il un moyen d'effectuer une opération de changement de vitesses sur eux en plus simplement les copier tous dans un autre tableau. Nous pouvons facilement le faire en utilisant des listes chaînées, mais je me demandais si nous pouvions utiliser un opérateur de changement de vitesse et accélérer le travail.

Remarque: Les données de cette question ne sont qu'un exemple. La réponse devrait être non-spécifique des données dans le tableau.

Answer 1

Si vous voulez un décalage circulaire des éléments:

std::rotate(&arr[0], &arr[1], &arr[10]); 

... fera l'affaire. Vous devrez #include l'en-tête de l'algorithme.

Answer 2

Si vous êtes la seule personne avec un pointeur vers le tableau, il suffit d'incrémenter le pointeur et de décrémenter la longueur.

N'oubliez pas de conserver le pointeur d'origine lorsque vous le libérez.

Answer 3

Tant que le tableau est modifiable, vous pouvez utiliser memmove pour les déplacer (mais ne memcpy pas utiliser à tort comme memcpy n'est pas pour les zones de chevauchement):

memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr)); 

(sizeof (arr) - sizeof (* arr) est la taille en octets de tous sauf 1 élément du tableau).

Answer 4

Je me demande si vous devriez peut-être utiliser un std :: valarray.

Answer 5

Si vous voulez vraiment de la vitesse BLAZING, regardez le décalage de l'assembleur avec les opérations de portage. http://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate#Shift_With_Carry_Instructions Couplé avec une boucle, vous pouvez décoder un tableau en millisecondes.

Answer 6

Si vous êtes à la recherche d'une solution C pure, voici un programme pilote. Il se révèle être assez simple: en rotation par n, vous:

1. inverse les premiers n éléments en place,
2. inverse les autres éléments en place, et
3. inverse tout le tableau en -endroit.

Cela nécessite un élément de stockage supplémentaire (pour l'inversion).

#include <stdio.h> 
#include <stdlib.h> 
#include <errno.h> 

/* print an array */ 
static void print_array(unsigned char *arr, size_t n, const char *prefix) 
{ 
    size_t i; 

    if (prefix) { 
     printf("%s: ", prefix); 
    } 
    for (i=0; i < n; ++i) { 
     printf("%02x ", (unsigned int)arr[i]); 
    } 
    printf("\n"); 
} 

/* reverse 'arr', which has 'narr' elements */ 
static void reverse(unsigned char *arr, size_t narr) 
{ 
    size_t i; 

    for (i=0; i < narr/2; ++i) { 
     unsigned char tmp = arr[i]; 
     arr[i] = arr[narr-i-1]; 
     arr[narr-i-1] = tmp; 
    } 
} 

/* rotate 'arr' of size 'narr' by 'shift' */ 
static void rotate(unsigned char *arr, size_t narr, unsigned long shift) 
{ 
    reverse(arr, shift); 
    reverse(arr + shift, narr - shift); 
    reverse(arr, narr); 
} 

/* driver program */ 
int main(int argc, char *argv[]) 
{ 
    unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9,10}; 
    size_t narr = sizeof arr/sizeof arr[0]; 
    unsigned long shift = 2; 

    if (argc > 1) { 
     char *eptr; 
     shift = strtoul(argv[1], &eptr, 0); 
     if (*eptr || errno == ERANGE) { 
      perror("strtoul"); 
      return EXIT_FAILURE; 
     } 
    } 
    print_array(arr, narr, "before shift"); 
    rotate(arr, narr, shift); 
    print_array(arr, narr, "after shift"); 
    return EXIT_SUCCESS; 
}