¿Cómo mejorarías este algoritmo? (Inversión de cadena c)

Question

Trabajando a través de algunos desafíos de entrevista de programación que encontré en línea, tuve que escribir un algoritmo para invertir un const char * y devolver un puntero a un nuevo char *. Creo que lo tengo, pero para que funcione correctamente, tuve que hacer algunas cosas incobrables, básicamente tener que dar cuenta del personaje de terminación nula. De alguna manera siento que esto está mal, pero estoy perplejo, y me preguntaba si alguien me podría ayudar:

char * reverse(const char * str) 
{ 
    int length = strlen(str); 
    char * reversed_string = new char[length+1]; 

    for(int i = 0; i < length; ++i) 
    { 
    reversed_string[i] = str[(length-1) - i]; 
    } 
    //need to null terminate the string 
    reversed_string[length] = '\0'; 

    return reversed_string; 

} 

int main(int argc, char * argv[]) 
{ 

    char * rev_str = reverse("Testing"); 

    cout << "Your string reversed is this: " << rev_str << endl; 

    delete rev_str; 
    rev_str = 0; 

    return 0; 
} 

Answer 1

Tenía esta cuestión de una vez. Esa es la primera respuesta que me viene a la mente, pero el seguimiento es: "ahora hazlo sin asignar ningún recuerdo".

int length = strlen(string); 
for(int i = 0; i < length/2; i++) { 
    char c = string[i]; 
    string[i] = string[length - i]; 
    string[length - i] = c; 
} 

EDITAR: Algunas personas han expresado su desdén por no usar punteros. Esto es un poco más legible, aunque no completamente óptimo. Otros han ingresado a la solución del puntero, por lo que no la repetiré aquí.

Un comentarista cuestionó que sea factible sin una celda de retención (basada en pila) para el intercambio. El mecanismo para hacerlo es a nivel de bit XOR. Sustituir el interior del bucle con

string[i] = string[i]^string[length - i]; 
string[length - i] = string[i]^string[length - i]; 
string[i] = string[i]^string[length - i]; 

Pero, en general, los compiladores modernos pueden optimizar la variable local de un intercambio de ingenuo. Para más detalles, See Wikipedia

Answer 2

esto funciona muy bien:

#include <algorithm> 
#include <iostream> 
#include <cstring> 

void reverse_string(char *str) {  
    char *end = str + strlen(str) - 1; 
    while (str < end) { 
     std::iter_swap(str++, end--); 
    } 
} 

int main() { 
    char s[] = "this is a test"; 
    reverse_string(s); 
    std::cout << "[" << s << "]" << std::endl; 
} 

Answer 3

if(string[0]) 
{ 
    char *end = string + strlen(string)-1; 
    while(start < end) 
    { 
     char temp = *string; 
     *string++ = *end; 
     *end-- = temp; 
    } 
} 

Answer 4

std::reverse de <algorithm> obras para cuerdas y char matrices:

string str = "Hello"; 
char chx[] = "Hello"; 

reverse(str.begin(), str.end()); 
reverse(chx, chx + strlen(chx)); 

cout << str << endl; 
cout << chx << endl; 

/EDIT: Esto, por supuesto, modifica el original cuerda. Pero STL al rescate. Lo siguiente crea una nueva cadena invertida. (?) Por desgracia, esto no funciona directamente en C char matrices sin crear un adicional (implícito) copia:

string reverse_string(string const& old) { 
    return string(old.rbegin(), old.rend()); 
} 

cout << reverse_string("Hello") << endl; 

Answer 5

Me he resuelto algo así como este (mi c es un poco oxidado, sin embargo, que perdones me)

char *reverse(const char *source) { 
    int len = strlen(source); 
    char *dest = new char[ len + 1 ]; 
    int i = 0; 
    int j = len; 
    while(j > 0) { 
    dest[j--] = src[i++]; 
    } 
    dest[i] = \0; 
    return dest; 
} 

Answer 6

en realidad, dada la restricción de que la cadena original se deja sin modificar, creo que el enfoque original dada en la pregunta es la mejor. Todos estos enfoques sofisticados para revertir en el lugar que la gente está publicando son grandiosos, pero una vez que se copia la cadena dada, todos son menos eficientes que simplemente copiar la cadena hacia atrás.

Answer 7

Hemos utilizado esta pregunta con anterioridad, con los sorprendentes resultados de encontrar mucha gente que no puede hacerlo (¡incluso con una gran experiencia en C/C++!). Prefiero la variante in situ, ya que ahorra un poco de sobrecarga, y tiene el toque adicional de solo necesitar iterar sobre strlen (s)/2 caracteres.

Su solución en una entrevista estaría bien. Una solución (¡correcta!) Que utiliza el puntero en lugar de la sintaxis de la matriz podría ser un poco más alta, ya que muestra un mayor nivel de comodidad con punteros que son tan importantes en la programación de C/C++.

Las críticas secundarias serían señalar que strlen devuelve un size_t no un int, y debe usar delete [] en rev_str.

Answer 8

No sería más eficiente, pero se podía demostrar el conocimiento de las estructuras de datos al hacer algo como empujar cada letra en una pila, y luego hacerlas estallar apagado en su memoria intermedia recién asignada.

sería tomar dos pases y una pila de cero, pero probablemente confiar en mí mismo más que hacerlo bien la primera vez y luego no hacer un off-por un error como el de arriba.

char* stringReverse(const char* sInput) 
{ 
    std::size_t nLen = strlen(sInput); 
    std::stack<char> charStack; 
    for(std::size_t i = 0; i < nLen; ++i) 
    { 
     charStack.push(sInput[i]); 
    } 
    char * result = new char[nLen + 1]; 
    std::size_t counter = 0; 
    while (!charStack.empty()) 
    { 
     result[counter++] = charStack.top(); 
     charStack.pop(); 
    } 
    result[counter] = '\0'; 
    return result; 
} 

Answer 9

¿Uh? Nadie lo hizo con punteros?

char *reverse(const char *s) { 
    size_t n = strlen(s); 
    char *dest = new char[n + 1]; 
    char *d = (dest + n - 1); 

    dest[n] = 0; 
    while (*s) { 
     *d-- = *s++ 
    } 

    return dest; 
} 

Esperemos años de Java no han arruinado mi C ;-)

Edición: reemplazado todas esas llamadas STRLEN con una var adicional. ¿Qué devuelve strlen en estos días? (Gracias plinth).

Answer 10

Su código es sencillo y no sorprende. Un par de cosas:

1. Uso size_t en lugar de int para el índice de bucle
2. Mientras que su compilador es más probable lo suficientemente inteligente como para darse cuenta de que (longitud -1) es invariante, probablemente no es lo suficientemente inteligente como para saber que (longitud-1) -i mejor se sustituye por una variable de bucle diferente que se decrementa en cada paso a
3. que haría uso de punteros en lugar de la sintaxis de matrices - que se verá más limpio para mí tener dst-- * = * srC++ ; en el lazo.

En otras palabras:

char *dst = reversed_string + length; 
*dst-- = '\0'; 
while (*src) { 
    *dst-- = *src++; 
} 

Answer 11

Al hacer esta pregunta como entrevistador, estoy buscando a una solución limpia, comprensible y puede preguntarse cómo la solución inicial podría ser más eficiente. No estoy interesado en soluciones 'inteligentes'.

Estoy pensando en cosas como; tiene el candidato hecho viejo con un error en su ciclo, preasignan suficiente memoria, revisan a la entrada incorrecta, usan tipos suficientemente eficientes.

Por desgracia, como ya se ha señalado, muchas personas ni siquiera pueden hacer esto.

Answer 12

@Konrad Rudolph: (lo siento, no tengo la "experiencia" para publicar un comentario)

Quiero señalar que el STL proporciona un algoritmo reverse_copy(), similar a reverse(). No necesita presentar un temporal como lo hizo, simplemente asigne un nuevo carácter * del tamaño correcto.

Answer 13

WRT: "Ahora hacerlo sin la variable de retención temporal" ... Algo como esto quizá (y mantener la indexación de matrices por ahora):

int length = strlen(string); 
for(int i = 0; i < length/2; i++) { 
    string[i] ^= string[length - i]; 
    string[length - i] ^= string[i]; 
    string[i] ^= string[length - i]; 
} 

Answer 14

Sé que esto es altamente no portables, pero de instrucciones x86 ensamblador bswap le permite intercambiar cuatro bytes por medio de una sola instrucción que puede ser un buen camino para aumentar el código.

Este es un ejemplo de cómo hacerlo funcionar con GCC.

/* 
* reverse.c 
* 
* $20081020 23:33 fernando DOT miguelez AT gmail DOT com$ 
*/ 

#include <stdint.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define MAX_CHARS 10 * 1024 * 1024 

/* 
* Borrowed from http://coding.derkeiler.com/Archive/Assembler/comp.lang.asm.x86/2007-03/msg00004.html 
* GNU Compiler syntax 
*/ 
inline uint32_t bswap(uint32_t val) 
{ 
    __asm__("bswap %0" : "=r" (val) : "0" (val)); 
    return val; 
} 

char * reverseAsm(const char * str) 
{ 
    int i; 
    int length = strlen(str); 
    int dwordLength = length/4; 

    if(length % 4 != 0) 
    { 
     printf("Error: Input string length must be multiple of 4: %d\n", length);  
     return NULL; 
    } 

    char * reversed_string = (char *) malloc(length+1); 
    for(i = 0; i < dwordLength; i++) 
    { 
     *(((uint32_t *) reversed_string) + dwordLength - i - 1) = bswap(*(((uint32_t *) str) + i)); 
    } 

    reversed_string[length] = '\0'; 

    return reversed_string; 
} 

char * reverse(const char * str) 
{ 
    int i; 
    int length = strlen(str); 
    char * reversed_string = (char *) malloc(length+1); 

    for(i = 0; i < length; ++i) 
    { 
     reversed_string[i] = str[(length-1) - i]; 
    } 

     //need to null terminate the string 

    reversed_string[length] = '\0'; 

    return reversed_string; 
} 

int main(void) 
{ 
    int i; 
    char *reversed_str, *reversed_str2; 
    clock_t start, total; 
    char *str = (char *) malloc(MAX_CHARS+1); 

    str[MAX_CHARS] = '\0'; 

    srand(time(0)); 

    for(i = 0; i < MAX_CHARS; i++) 
    { 
     str[i] = 'A' + rand() % 26;  
    } 

    start = clock(); 
    reversed_str = reverse(str); 
    total = clock() - start; 
    if(reversed_str != NULL) 
    { 
     printf("Total clock ticks to reverse %d chars with pure C method: %d\n", MAX_CHARS, total); 
     free(reversed_str); 
    } 
    start = clock(); 
    reversed_str2 = reverseAsm(str); 
    total = clock() - start; 
    if(reversed_str2 != NULL) 
    { 
     printf("Total clock ticks to reverse %d chars with ASM+C method: %d\n", MAX_CHARS, total); 
     free(reversed_str2); 
    } 

    free(str); 

    return 0; 
} 

Los resultados en mi viejo ordenador bajo Cygwin:

fer@fernando /cygdrive/c/tmp$ ./reverse.exe 
Total clock ticks to reverse 10485760 chars with pure C method: 221 
Total clock ticks to reverse 10485760 chars with ASM+C method: 140 

Answer 15

Cuerda invierten en su lugar, hay una variable temporal.

static inline void 
byteswap (char *a, char *b) 
{ 
    *a = *a^*b; 
    *b = *a^*b; 
    *a = *a^*b; 
} 

void 
reverse (char *string) 
{ 
    char *end = string + strlen(string) - 1; 

    while (string < end) { 
    byteswap(string++, end--); 
    } 
} 

Answer 16

Un método que no necesita variables temporales

int length = strlen(string); 
for(int i = 0; i < length/2; i++) { 
    string[i] ^= string[length - i] ^= string[i] ^= string[length - i]; 
} 

Answer 17

Si yo estaba haciendo las entrevistas me gustaría ser un poco más exigente con la calidad de la solución en términos de su robustez, no sólo es rendimiento

Todo de las respuestas presentadas hasta el momento se producirá un error si se pasa un puntero nulo - la mayoría de ellos salto a llamar inmediatamente strlen() sobre un posible puntero nulo - que probablemente segfault su proceso.

Muchas de las respuestas son obsesivos con el rendimiento hasta el punto de que se pierda uno de los temas clave de la cuestión: revertir una const char *, es decir, es necesario hacer una copia invertido , no revierten en el lugar. ¡Te resultará difícil reducir a la mitad el número de iteraciones si se requiere una copia!

Esta es una pregunta de la entrevista, por lo que queremos ver los detalles del algoritmo, pero en el mundo real esto solo resalta el valor de usar bibliotecas estándar siempre que sea posible.

Answer 18

.

char * reverse(const char * str) 
{ 
    if (!str) 
    return NULL; 

    int length = strlen(str); 
    char * reversed_string = new char[length+1]; 

    for(int i = 0; i < length/2; ++i) 
    { 
    reversed_string[i] = str[(length-1) - i]; 
    reversed_string[(length-1) - i] = str[i]; 
    } 
    //need to null terminate the string 
    reversed_string[length] = '\0'; 

    return reversed_string; 

} 

La mitad del tiempo, sino misma complejidad (nota pueden estar fuera por un error)

Answer 19

Por encima de bucle tiene error tipográfico. Comprobación de la variable de ciclo debería ser < = en lugar de <, de lo contrario fallará para el número impar de elementos. for (int i = 0; i < = longitud/2; ++ i)

Answer 20

No se puede (no debe) hacer esto:

string[i] ^= string[length - i] ^= string[i] ^= string[length - i]; 

Desde: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

• * "Este código tiene un comportamiento indefinido, ya que modifica el lvalue x dos veces sin un punto de secuencia intermedio.