Najszybszy sposób na odwrócenie ciągu znaków w C

Question

Czy ta funkcja jest najszybszym, najbardziej zoptymalizowanym sposobem odwracania ciągu znaków w C? To działa w czasie O (n/2). Optymalizacja polega na tym, że iteruje ona tylko przez połowę ciągu znaków.

char* str_reverse(char *str, int len) 
{ 
    char word[len]; 
    int i; 
    for (i = 0; i <= len/2; ++i) { 
     word[i] = str[len - i - 1]; 
     word[len - i - 1] = str[i]; 
    } 
    word[len] = '\0'; 
    return word; 
} 

Answer 1

Może coś takiego?

char *str_reverse_in_place(char *str, int len) 
{ 
    char *p1 = str; 
    char *p2 = str + len - 1; 

    while (p1 < p2) { 
     char tmp = *p1; 
     *p1++ = *p2; 
     *p2-- = tmp; 
    } 

    return str; 
} 

Answer 2

Znajdziesz algorytmy podejmowania mniej wskazówek, jak tego w miejscu odwrócić

char* str_reverse_in_place(char *str, int len) 
{ 
    int i; 
    for (i = len/2-1 ; i >= 0 ; --i) { 
     char c = str[i]; 
     str[i] = str[len-i-1]; 
     str[len-i-1] = c; 
    } 
    return str; 
} 

Optymalizacja pod kątem szybkości na tym poziomie, należy spojrzeć na inline hasła, także skompilować (dla gcc) z -O3 (zazwyczaj lepsza praca polega na samodzielnym dodawaniu do rejestru rejestru ...).

Jeśli trzeba mieć odwrócony ciąg gdzie indziej, albo dostarczyć go w funkcji (są przeznaczone dla strlen(str)+1 - faktycznie len+1 tutaj - znaków)

char* str_reverse(char *str, char *reverse, int len) 
{ 
    int i; 
    for (i = len-1 ; i >= 0 ; --i) { 
     reverse[i] = str[len-i-1]; 
    } 
    reverse[len] = 0; 
    return reverse; 
} 

lub malloc to (będzie musiało być uwolniony przez dzwoniącego).

char* str_reverse_malloc(char *str, int len) 
{ 
    char *reverse = malloc(len+1); 
    if (! reverse) return NULL; 
    int i; 
    for (i = len-1 ; i >= 0 ; --i) { 
     reverse[i] = str[len-i-1]; 
    } 
    reverse[len] = 0; 
    return reverse; 
} 

Answer 3

int main() { 
    char str[100], temp; 
    int i, j = 0; 

    printf("\nEnter the string :"); 
    gets(str); 

    i = 0; 
    j = strlen(str) - 1; 

    while (i < j) { 
     temp = str[i]; 
     str[i] = str[j]; 
     str[j] = temp; 
     i++; 
     j--; 
    } 

    printf("\nReverse string is :%s", str); 
    return (0); 
} 

Answer 4

Tutaj jest odmianą, która nie wymaga długości mają być przekazywane i zamienić zarówno początek i znaków kończących w danym przesunięcie w obrębie łańcucha każdym przejściu przez pętlę:

/** strrevstr - reverse string, swaps src & dest each iteration. 
* Takes valid string and reverses, original is not preserved. 
* If str is valid, returns pointer to str, NULL otherwise. 
*/ 
char *strrevstr (char *str) 
{ 
    if (!str) { 
     printf ("strrevstr() error: invalid string\n"); 
     return NULL; 
    } 

    char *begin = str; 
    char *end = str + strlen (str) - 1; 
    char tmp; 

    while (end > begin) 
    { 
     tmp = *end; 
     *end-- = *begin; 
     *begin++ = tmp; 
    } 

    return str; 
} 

Answer 5

"Najbardziej" zoptymalizowany sposób musi odnosić się do architektury procesora i pamięci, a także do tego, co jest odwracane (długie ciągi lub krótkie ciągi i jaka jest dystrybucja).

Nie ma sposobu na złagodzenie wymogu O (N), ale można użyć technik takich jak rozwijanie pętli, blokowanie pętli i paralelizm w celu optymalizacji chybienia pamięci podręcznej dla bardzo dużych ciągów. Można również zwiększyć rozmiar słowa i zamienić na miejscu słowa, dwójki lub większe jednostki (w przypadku prawdopodobnego problemu z wyrównaniem).

// To najprawdopodobniej będzie szybsze niż kopiowanie bajtów mądry, ale to nie jest O (N/8) ...

if (len & 7 == 0) 
{ 
    uint32_t *dst = src+len-4; 
    uint32_t *src = (uint32_t *)ptr; 
    while (src<dst) 
    { 
     a = *src; b = *dst; 
     *src++ = byte_swap(b); 
     *dst-- = byte_swap(a); 
    } 
} 

Answer 6

Jest to najszybszy sposób, aby wydrukować wsteczny ciąg w C

#include <stdio.h> 
 
#include <string.h> 
 

 
int main() 
 
{ 
 
    char str[30],str1[30]; 
 
    printf("Enter string :"); 
 
    scanf("%s",str); 
 
    int i = strlen(str); 
 
    for (int j = 0; j <=5;j++) 
 
    { 
 
    \t \t str1[j]=str[i-j]; 
 
    \t \t printf("%c",str1[j]); \t 
 
    } 
 
    printf("\n"); 
 
}