c++ - このアルゴリズムをどのように改善しますか? (C文字列反転)

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

score 16 · Accepted Answer

std::reversefrom<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が助けになります。以下は、新しい逆文字列を作成します。char残念ながら (?)、これは追加の (暗黙的な) コピーを作成しない限り、C 配列では直接機能しません。

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

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

score 14 · Accepted Answer

私はかつてこの質問をしました。それが頭に浮かぶ最初の答えですが、フォローアップは、「今はメモリを割り当てずに実行してください」です。

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

編集: 一部の人々は、ポインターを使用しないことに軽蔑を表明しています。これは、完全に最適ではありませんが、少し読みやすくなっています。他の人はポインターソリューションに参加しているので、ここでは繰り返しません。

あるコメンターは、スワップ用の (スタックベースの) 保持セルがなくても実行可能であるべきだと異議を唱えました。これを行うメカニズムは、ビットごとの XOR です。ループの内側を次のように置き換えます

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

しかし、一般に、最新のコンパイラは、単純なスワップのローカル変数を最適化できます。詳しくはウィキペディア参照

score 7 · Accepted Answer

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

score 3 · Accepted Answer

これは移植性が非常に低いことは承知していますが、x86 アセンブラー命令bswapを使用すると、1 つの命令だけで 4 バイトをスワップできます。

これは、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

score 3 · Accepted Answer

え？誰もポインタでそれをしませんでしたか？

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 は何を返しますか? （台座に感謝）。

score 3 · Accepted Answer

あなたのコードは単純で驚くべきものではありません。いくつかのこと：

ループインデックスに int の代わりに size_t を使用する
あなたのコンパイラはおそらく (length -1) が不変であることを理解するのに十分賢いですが、おそらく (length-1)-i が各パスでデクリメントされる別のループ変数に最もよく置き換えられることを理解できるほど賢くないでしょう
私は配列構文の代わりにポインタを使用します - *dst-- = *src++; を持つ方がきれいに見えますループの中。

言い換えると：

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

score 2 · Accepted Answer

これを行うことはできません（すべきではありません）：

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

差出人：http：//en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

* "このコードは、シーケンスポイントを介さずに左辺値xを2回変更するため、未定義の動作をします。

score 2 · Accepted Answer

@Konrad Rudolph: (申し訳ありませんが、コメントを投稿する「経験」がありません)

STL がreverse()に似たreverse_copy()アルゴリズムを提供していることを指摘したいと思います。一時的な方法を導入する必要はありません。適切なサイズの新しい char * を割り当てるだけです。

score 1 · Accepted Answer

実際、元の文字列を変更せずに残すという制約があるため、質問で指定された元のアプローチが最適だと思います。人々が投稿している場所でリバースするこれらの派手なアプローチはすべて素晴らしいですが、指定された文字列をコピーすることを考慮に入れると、文字列を単純に逆方向にコピーするよりも効率が低下します。

score 1 · Accepted Answer

この質問は以前にも使用したことがありますが、驚くべきことに、(かなりの C/C++ の経験があっても) できない人がたくさん見つかりました。オーバーヘッドがいくらか節約され、strlen(s)/2 文字を反復するだけでよいというひねりが加えられているため、私はインプレースバリアントを好みます。

面接でのあなたの解決策は問題ありません。配列構文の代わりにポインターを使用する (正しい!) ソリューションは、C/C++ プログラミングで非常に重要なポインターを使用することで快適性が向上するため、評価が少し高くなります。

マイナーな批判は、strlen が int ではなく size_t を返すことを指摘することであり、rev_str で delete [] を使用する必要があります。

score 1 · Accepted Answer

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

score 0 · Accepted Answer

インタビュアーとしてこの質問をするとき、私は明確でわかりやすい解決策を探しており、最初の解決策をより効率的にするにはどうすればよいかを尋ねるかもしれません. 「スマート」ソリューションには興味がありません。

次のようなことを考えています。候補者がループ内で 1 つのエラーによって古いものをオフにしたか、十分なメモリを事前に割り当てているか、不正な入力をチェックしているか、十分に効率的な型を使用しているか。

残念ながら、すでに指摘したように、あまりにも多くの人がこれを行うことさえできません。

score 0 · Accepted Answer

一時変数を必要としないメソッド

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

score 0 · Accepted Answer

これはうまくいきます：

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

score 0 · Accepted Answer

私はそれをこのように解決したでしょう（私の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;
}

score 0 · Accepted Answer

文字列が逆になり、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--);
  }
}

score 0 · Accepted Answer

より効率的ではありませんが、各文字をスタックにプッシュし、新しく割り当てられたバッファーにポップするなどのことを行うことで、データ構造の知識を示すことができます。

2 回のパスと 1 回のスクラッチスタックが必要ですが、上記のようなオフバイ 1 回のエラーを起こさないようにするには、最初にこれを正しく行うことに自信を持っていると思います。

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

score 0 · Accepted Answer

.

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;

}

時間は半分ですが、複雑さは同じです (メモは 1 つのエラーでずれている可能性があります)

score 0 · Accepted Answer

もし私がインタビューをしていたら、ソリューションのパフォーマンスだけでなく、堅牢性の観点から、ソリューションの品質にもう少しうるさくなるでしょう。

これまでに送信されたすべての回答は、null ポインターが渡された場合に失敗します。それらのほとんどはstrlen()、可能性のある null ポインターをすぐに呼び出すことに飛びつきます。これにより、おそらくプロセスがセグメンテーション違反になります。

回答の多くは、質問の重要な問題の 1 つを見逃しているという点でパフォーマンスに執着していconst char *ます。コピーが必要な場合、反復回数を半分にするのは難しいでしょう。

これはインタビューの質問なので、アルゴリズムの詳細を見たいと思いますが、現実の世界では、これは可能な限り標準ライブラリを使用する価値を強調するだけです.

c++ - このアルゴリズムをどのように改善しますか? (C文字列反転)

20 に答える 20

Related

Reference