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

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

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

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

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

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

Но в целом современные компиляторы могут оптимизировать локальную переменную наивного свопа. Подробности: См. Википедию

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

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

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;

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

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

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

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

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

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

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

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

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

Эм-м-м? С указателями никто не делал?

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 на дополнительную переменную. Что возвращает strlen в наши дни? (Спасибо цоколь).

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

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

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

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

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

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

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

@ Конрад Рудольф: (извините, у меня нет опыта, чтобы оставлять комментарии)

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

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

Я знаю, что это очень непереносимо, но инструкция ассемблера 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

Перевернутая строка на месте, без временной переменной.

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

Метод, не требующий временных переменных

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

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

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

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

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

.

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;

}

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

Над циклом for есть опечатка. Проверка переменной цикла i должна быть <= вместо <, othrewise не удастся из-за нечетного количества элементов. для (int i = 0; i <= length / 2; ++ i)

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

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

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

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