c++ - 使用交换和递归在 C 和 C++ 中实现字符串反转性能

Question

我正在练习我的 C 和 C++ 技能，然后我决定使用两种语言中使用的方法来解决字符串反转问题。我写了一个递归解决方案和索引方法。这里有4个反向函数； 2 个严格使用 C 方法进行计算，另外 2 个使用 C++(STL、String、算法)调用。

• 这是一个很好的比较来了解每种方法的速度还是我缺少什么吗？
• 我还想知道每个有多少内存方法使用，但我还没有弄清楚如何做到这一点。

// C++ reverse string
#include <string> // string
#include <algorithm> // reverse
#include <iostream> // cout

#include <cstring> // std::strcpy
#include <stdio.h> // printf
#include <sys/time.h> // gettimeofday

inline void swap_characters(char* left, char* right) {
    char temp = *left;
    *left = *right;
    *right = temp;
}

void c_index_reverse(char* input, size_t inputSize) {

    const size_t strSize = inputSize - 1;
    char temp;

    for(int i=0 ; i < inputSize / 2 ; i++) {
        swap_characters(&input[i], &input[strSize - i]);
    }
}

void c_recursive_reverse(char str[], int index, int size)
{
    swap_characters(&str[index], &str[size - index]);

    if (index == size / 2)
        return;

    c_recursive_reverse(str, index + 1, size);
}


void c_plusplus_index_reverse(std::string& input) {

    const size_t strSize = input.length();

    for(int i=0 ; i < strSize / 2 ; i++)
        std::swap(input[i], input[strSize - i - 1]);
}


std::string c_plusplus_recursive_reverse(std::string& input) {

    if(input.length() <= 1) {
        return input;
    }

    std::string tmp = std::string(input.begin() + 1, input.end());
    return c_plusplus_recursive_reverse(tmp) + input[0];
}


double timeit(struct timeval &start, struct timeval &end){
    double delta = ((end.tv_sec - start.tv_sec) * 1000000u + end.tv_usec - start.tv_usec) / 1.e6;
    return delta;
}

int main() {

    struct timeval start,end;

    // using C++ STL
    std::string temp = "something very weird is another word that includes a longer text to see the delay" \
    "something very weird is another word that includes a longer text to see the delay" \
    "something very weird is another word that includes a longer text to see the delay" \
    "something very weird is another word that includes a longer text to see the delay" \ 
    "something very weird is another word that includes a longer text to see the delay" \
    "something very weird is another word that includes a longer text to see the delay" \
    "something very weird is another word that includes a longer text to see the delay";
    std::cout << temp << std::endl;

    // using c++ recursive reverse function - 4
    gettimeofday(&start, NULL);
    std::reverse(temp.begin(), temp.end());
    gettimeofday(&end, NULL);

    std::cout << temp << std::endl;
    printf("%lf \n",timeit(start, end));


    // use C++ style functions
    // using recersive - 5
    gettimeofday(&start, NULL);
    temp = c_plusplus_recursive_reverse(temp);
    gettimeofday(&end, NULL);
    std::cout << temp  << std::endl;
    printf("%lf \n",timeit(start, end));

    // using index reverse - 3
    gettimeofday(&start, NULL);
    c_plusplus_index_reverse(temp);
    gettimeofday(&end, NULL);
    std::cout << temp << std::endl;
    printf("%lf \n",timeit(start, end));



    // Now do C style
    char *cStr = new char[temp.length() + 1];
    std::strcpy(cStr, temp.c_str());


    // using index - 1
    gettimeofday(&start, NULL);
    c_index_reverse(cStr, temp.length());
    gettimeofday(&end, NULL);
    printf("%s \n", cStr);
    printf("%lf \n",timeit(start, end));


    // using recersive - 2
    gettimeofday(&start, NULL);
    c_recursive_reverse(cStr, 0, temp.length() - 1);
    gettimeofday(&end, NULL);
    printf("%s \n", cStr);
    printf("%lf \n",timeit(start, end));


    return 0;
}

Answer 1

拥有内联函数 swap_characters() 只需三行代码就可以完成一项艰巨的任务，当您已经拥有它们时，会创建更多指针(尽管编译器可能会优化)。使用另一个索引变量，例如 j，它会递减直到遇到 i 会更高效。

void c_index_reverse(char* input, size_t inputSize) {

    int j = inputSize - 1;
    char temp;

    for(int i=0; i<j; i++) {
        temp = input[i];
        input[i] = input[j];
        input[j--] = temp;
    }
}

“我还想知道每种方法使用了多少内存”。非递归方法使用最少的内存，因为它只使用指针和索引器。但是递归方法使用更多的内存，因为每个字符串字符(最多字符串长度的一半)都会调用递归，因此会使用更多的堆栈。由于您的字符串 "something very odd ..." 大约有 600 个字符，这需要大量的堆栈使用，并且大部分执行时间都花在调用、操作堆栈帧和返回上，交换字符所花费的时间很少。

这里的递归是“无处隐藏”。