Как бы вы улучшили этот алгоритм? (смена строки)

Question

Работая с некоторыми проблемами программирования, которые я нашел в Интернете, мне пришлось написать алгоритм для обращения к const char * и вернуть указатель на новый char *. Я думаю, что у меня есть это, но чтобы он работал правильно, мне пришлось делать некоторые неуклюжие вещи - в основном, для того, чтобы сам отвечать за нулевой конец. Как-то я считаю, что это неправильно, но я в тупик, и мне было интересно, если кто-то может помочь мне:

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

У меня был этот вопрос раз. Это первый ответ, который приходит на ум, но последующее наблюдение: «Теперь сделайте это, не выделяя никакой памяти».

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

EDIT: Некоторые люди выразили презрение к тому, что не используют указатели. Это немного более читаемо, хотя и не совсем оптимально. Другие ввели указатель, поэтому я не буду повторять его здесь.

Один комментатор поставил под сомнение, что он должен выполняться без ячейки с ячейкой для свопа. Механизм для этого - побитовый XOR. Заменить внутреннюю часть петли с

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

Но в целом, современные компиляторы могут оптимизировать из локальных переменных наивного свопа. Для получения дополнительной информации, See Wikipedia

Answer 2

это прекрасно работает:

#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 из <algorithm> произведений для струнных и char массивов:

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

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

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

/EDIT: Это, конечно, изменяет оригинал строка. Но STL на помощь. Следующее создает новую переменную строку. (?) К сожалению, это не работает непосредственно на C char массивов без создания дополнительного (неявного) копия:

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

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

Answer 5

я бы решил его вроде как это (мои с немного ржавым, хотя, прости меня)

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

на самом деле, учитывая ограничения, что исходная строка останется неизмененной, я думаю, что оригинальный подход дан в вопросе является лучшим. Все эти причудливые подходы к реверсированию на местах - это отличные публикации, но как только копирование данной строки учитывается, все они менее эффективны, чем просто копирование строки назад.

Answer 7

Мы использовали этот вопрос раньше - с удивительно результатами поиска многих людей, которые не могут этого сделать (даже при значительном опыте C/C++!). Я предпочитаю вариант на месте, так как он экономит некоторые накладные расходы и имеет дополнительный поворот, требующий только перебора строк (str)/2 символа.

Ваше решение в интервью будет в порядке. Решение A (правильно!), Использующее указатель вместо синтаксиса массива, будет немного дороже, так как оно показывает более высокий уровень комфорта с указателями, которые так критичны в программировании на C/C++.

Недостаточная критика будет заключаться в том, что strlen возвращает size_t не int, и вы должны использовать delete [] для rev_str.

Answer 8

Это не было бы более эффективным, но вы могли бы продемонстрировать знание структур данных, сделав что-то вроде нажатия каждой буквы на стек, а затем выталкивая их в новый выделенный буфер.

Это займет два прохода и стек царапины, но я, вероятно, буду доверять себе больше, чтобы в первый раз получить это право, чтобы не сделать ошибку за один, как указано выше.

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? Никто не сделал это с указателями?

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

Надеется, года Java не испортили C ;-)

Редактировать: заменены все эти STRLEN звонков с дополнительной вар. Что вернет в эти дни? (Спасибо plinth).

Answer 10

Ваш код прямолинейный и неудивительный. Несколько вещей:

1. Использование size_t вместо междунар для вашего индекса цикла
2. Хотя ваш компилятор является, скорее всего, достаточно умны, чтобы понять, что (длина -1) инвариантна, это, вероятно, не достаточно умны, чтобы понять, что (length-1) -i лучше всего заменяется другой переменной цикла, которая уменьшается в каждом проходе
3. Я бы использовал указатели вместо синтаксиса массива - он будет выглядеть более чистым для меня, чтобы иметь * dst-- = * srC++ ; в петле.

Других слова:

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

Answer 11

Задавая этот вопрос, как интервьюер, я ищу в чистое, понятное решение и могу спросить, как первоначальное решение могло бы быть более эффективным. Меня не интересуют «умные» решения.

Я думаю о такой вещи; имеет ли кандидат старое с отключенной одной ошибкой в ​​своем цикле, они заранее выделяют достаточное количество памяти, они проверяют на плохой ввод, используют ли они достаточно эффективных типов.

К сожалению, как уже указывалось, слишком много людей даже не могут этого сделать.

Answer 12

@Konrad Rudolph: (жаль, что я не имею «опыт», чтобы отправить комментарий)

Я хочу отметить, что STL поставляет reverse_copy() алгоритм, похожий на reverse(). Вам не нужно вводить временный способ, который вы сделали, просто выделите новый символ * нужного размера.

Answer 13

WRT: «Теперь это сделать без переменной временного содержания» ... Что-то вроде этого, может быть (и сохранение индексации массива в настоящее время):

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

Я знаю, что это очень непереносимым, но инструкция x86 ассемблере BSWAP позволяет вам обменивать четыре байта с помощью одной инструкции, которая может быть хорошим путем для повышения кода.

Это пример того, как заставить его работать с 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; 
} 

Результаты на моем старом компьютере под 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

Строка изменилась в месте, не переменной TEMP.

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

метод, который не требует временных переменных

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

Answer 17

Если бы я делал интервью я бы немного более суетливый с качеством решения с точки зрения ее надежности, а не только это производительность.

Все из ответов, представленных до сих пор не удастся, если он принят нулевой указатель - большинство из них прыгают немедленно вызывая strlen() на возможный пустой указатель - который, вероятно, ваш процесс сегментации.

Многие ответы обсессивно о производительности до такой степени, что они пропустить один из ключевых вопросов вопроса: сторнировать const char *, то есть вам нужно сделать перевернутую копию , не перепутать на месте. Вам будет трудно вдвое сократить количество итераций, если требуется копия!

Это вопрос интервью, поэтому мы хотим взглянуть на детали алгоритма, но в реальном мире это просто подчеркивает ценность использования стандартных библиотек, когда это возможно.

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; 

} 

Половина время, но тот же сложность (примечание может быть от одной ошибки)

Answer 19

Выше для контура имеет опечатку. Проверка переменной цикла i должна быть < = вместо <, othrewise не сработает для нечетного элемента. для (INT I = 0; я < = длина/2; ++ я)

Answer 20

Вы не можете (не должны) сделать это:

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

От: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

• * «Этот код имеет неопределенное поведение, так как он изменяет lvalue x дважды без промежуточной точки последовательности.