C回文

bool palindrome(char *text);

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>
#include "header.h"

int main() {
    clock_t start;
    start = clock();

    int j;
    for(j = 0; j < 1000000; j++) {
        palindrome("racecar");
    }

    printf("%.10f", (double) (clock() - start) / CLOCKS_PER_SEC);
    return 0;
}

bool palindrome(char *text) {
    char *right = text + strlen(text);
    while(text < --right) {
        if(*text++ != *right) {
            return false;
        }
    }
    return true;
}

#1 楼

一些注意事项：


在标头中包含一些防护。
为标头命名更独特，更合适。

始终声明您的参数函数可以接受，即使什么也没有。

int main(void)

您可能想知道为什么我们必须这样做。想象一下，我们将函数foo()声明为：

int foo()

在C语言中，这称为标识符列表，它表示“可以接受任意数量的未知参数”类型”。我们实际上可以将值传递给函数，即使我们并非故意或不打算这样做。如果调用方调用给函数提供一些参数的函数，则该行为是不确定的。例如，堆栈可能会损坏，因为被调用的函数在获得控制权时会期望使用不同的布局。

不建议在函数参数中使用标识符列表。最好执行以下操作：

int foo(void)

在C语言中，这称为参数类型列表，它定义该函数接受零个参数（并进行通信读取时）-与所有使用参数类型列表声明该函数的情况（称为原型）一样。如果调用者调用该函数并为其提供了一些参数，则这是一个错误，并且编译器吐出了相应的错误。当然之一是检查参数的数量和类型。另一个区别是，由于编译器知道参数类型，因此可以将参数的隐式转换应用于参数的类型。如果没有参数类型列表，则无法完成，参数将转换为提升的类型（称为默认参数提升）。例如，char将变为int，而float将变为double。


我不确定我是否会在您的代码中实现计时，而是使用bash命令time来计时（请注意，此输出与您的程序无关，只是一个示例）：

$ time ./a.out
real    0m0.007s
user    0m0.004s
sys     0m0.005s

请注意，您可以将palindrome()函数从while()循环折叠为for循环：

bool palindrome(char *text) 
{
    for(char *right = text + strlen(text) - 1; text < right; text++, right--) 
    {
        if(*text != *right) 
        {
            return false;
        }
    }
    return true;
}

您也可以像@ JS1在他的代码示例中那样，从指针用法转换为数组用法，我可能会建议初学者使用。请注意，如果您确实要过渡到数组，则可能会对性能造成小的影响（取决于编译器的优化）。

根据C标准，您不需要在main末尾添加return 0;。

#2 楼

简化

我发现您使用的多指针解决方案有点难以阅读和验证正确性（尽管该功能是正确的）。我会改用数组语法和索引，例如：

bool palindrome(const char *text)
{
    for (int left=0, right=strlen(text)-1; left < right; left++, right--) {
        if (text[left] != text[right])
            return false;
    }
    return true;
}

const关键字

如果您在上面的代码中注意到，我在函数参数上使用了const。作为初学者C程序员，请注意const存在并且意味着该参数不会被修改。

对于此特定功能，使用const不会带来速度优势。在其他功能中，编译器有可能基于其对变量不会改变值的认识而改进优化。我觉得const的最大好处是通过区分哪些变量是可变的和哪些是不可变的，从而提高了您对程序的理解。在Java中，您具有完整的不可变类型，例如String。在C语言中，您使用const代替一个不可变的变量。

打印换行符

您的输出不包括换行符，当我运行程序时，它弄乱了我的shell提示。

#3 楼

请注意，您的回文功能仅适用于字符编码为每个字符1个字节的字符串。如果您收到的多字节编码字符串的编码方式中字符的宽度并不总是相同，则此方法将不起作用。

例如如果您有一个UTF-32字符串，并且某些类型的utf32_char*可以处理整个字符，则当两个光标逐个字符地遍历字符串时，可以使用相同的方法。

但是，UTF-8字符串被两个char*迭代，将导致您检查中间字符的多字节代码点。

废话'düd'似乎是回文，但其UTF-8编码为

0x64 0xC3 0xBC 0x64

其中0xC3 0xBC是单个代码点ü的UTF-8序列。

#4 楼

这里有一些观察和建议，可能会帮助您改进代码。总而言之，这一切都不是一件容易的事。

消除头文件

对于像这样的小程序，它可以很容易地放在单个文件中。与Java不同，C不会强迫您为每个程序增加大量文件。声明可以在main.c中或更简单，只需将palindrome的定义放在main的定义之上，就不需要任何前向声明。

在可行的地方使用const

palidrome的参数是指向在函数内未更改的文本的指针。为了显示给任何调用程序，声明应改为：

bool palindrome(const char *text) 

用户的思考

如果此代码曾经存在，在其他地方使用时，您既要重新引入头文件（但要给它一个好听的名字！），又要记录代码如何处理某些类型的输入。现在，如果将指针交给NULL，它将崩溃。

省略return 0


从C99开始，编译器会在return 0的末尾自动生成与main对应的代码，因此无需显式编写。 br />

#5 楼

palindrome不是一个好名字。它不会告诉用户它做什么。我建议您简单地选择isPalindrome，或者，如果您愿意，也建议is_palindrome。

#6 楼

关于循环的性能：

请注意，您实际上在扫描字符串两次（一次扫描一次）。如果您可以避免这种情况，或者自己进行显式扫描，则可以提高性能。例如，接受函数长度的API更改使其成为调用方的责任：他们可以使用strlen（这不会造成净损失），但是如果已经有了strlen，您会发现循环会快很多-尤其是在您将其传递给较大的回文。

顺便说一句，将最坏情况的示例传递给它，很不错。如果您传递类似“ alphabet”的字母，它将在第一个字符上生效。

为了提高性能，指针是C固有的，而数组有时可以被优化为与C相同的级别-取决于您的编译器和优化器。使用Visual Studio C编译器和gcc，您可能会看到意想不到的结果。

关于与其他语言的比较，要注意的事情之一是几种语言显式地做了很多工作，使字符串更有效-屏蔽字符可能相对昂贵（与比较芯片的字长相比）。在隐式处理字符串方面，有很多语言比C做更多的事情，在这种特定的测试中它们实际上可能胜过C。

您的实际问题似乎在于性能是否可以提高；对我来说，这将需要一些实验。所以对于这部分，我没有简短的答案。

#7 楼

我不介意++中的循环中的--和palindrome，但我发现在同一行上移动这些操作会更容易理解：

在此版本中，更容易看到指针同步移动。

让我失望的另一件事是，main方法仅对相同的输入字符串循环执行palindrome。
如果：


它会验证结果是否正确
它使用了多个回文和非回文示例
它使用了更长的时间示例，例如itusedlongerexamplesforexampleelpmaxerofselpmaxeregnoldesuti


或者，如果我可以对命令行参数运行该方法，将是用户友好的，例如： />

#8 楼

您问是否可以更快。有趣的问题。有时您必须尝试一下，明显的调整并不总是最好的。

我测试的第一件事是编译器优化。 “ gcc”和“ gcc -O3”之间的差异非常大：

十亿次迭代：


短字符串（3个字符），您的字符串为5.45秒
短字符串（3个字符），我的：2.77秒
中字符串（racecar），你的：9.45秒，
中字符串（racecar），我的：4.30秒
长字符串（ 52个字符），您的：66.94秒
长字符串（52个字符），我的字符串：18.14秒

用gcc -O3优化：


短字符串（3个字符），您的：2.47秒
短字符串（3个字符），我的：0.000001秒
中型字符串（赛车），您的：3.04秒
中型字符串（racecar），我的：2.42秒
长字符串（52个字符），您的：16.28秒
长字符串（52个字符），我的：12.45秒

您可以看到优化器极大地缩小了差距！通常，如果您编写干净的代码并让编译器完成工作，则无需花费很多精力进行优化即可获得相当不错的数字。仍然可以进行一些优化。

我用短字符串进行了测试，以强调函数调用开销和算法设置。在典型情况下为中等字符串；和一个很长的字符串（向前和向后的字母）来测试函数中的紧密循环。

这是我调整后的回文版本：

bool palindrome(register char *text, int len) {
    register char *right = text + len - 1;
    while (text < right && *text == *right) {
        text++;
        right--;
    }
    return (text >= right);
}

如其他人所建议的那样，将strlen移出循环并仅传递长度对于我来说可以提高15％的速度。

register关键字告诉编译器使用CPU寄存器如果可能，请使用内存变量。在未优化的情况下，它的速度大约提高了一倍，但对优化没有影响，可能是因为编译器已经在这样做了。只有在变量很少（在本例中为两个）的情况下，注册才有帮助。

从表面上看，它是等效的：相同数量的测试，相同数量的变量。但是它的运行速度要快得多。

我玩过很多游戏，但目的是消除尽可能多的测试。我的大多数“聪明的发明”都证明减慢了速度，但其中一个产生了令人惊讶的结果：我发现比较和增量构造*text++ == *right--的运行速度明显慢于将增量分开并将其放入循环体中。我怀疑这是因为它为编译器提供了更多优化事情的灵活性。至少对于很长的回文，这似乎是register关键字之外最大的改进来源。短弦没有什么改善。同样，编写清晰的代码，让编译器完成工作。但绝对可以做实验！

我不确定为什么简短（3个字符）的字符串测试几乎不需要花费我的版本的时间。也许优化器足够聪明，可以预先计算所有内容并优化整个测试循环。在这种简单的循环测试中，这始终是一个问题：您可能没有测试自己认为要测试的内容，并且编译器可能会抛出大量代码。强制它为生成基准而进行不必要的工作可能很棘手。

在很长的回文中尝试这样做很有趣！

#9 楼

免责声明：这不是代码审查。实际上，这比OP编写的要差。但是，根据OP的请求它更快。
编写一个宏
我写了一个宏版本（见下文）。 ({...})是GCC扩展，称为语句表达式，但是如果您不使用GCC，则可以修改变量ret并随后访问它。
通常，宏会更快，因为它们不需要新的堆栈框架，但是我认为GCC可能仍会为语句​​表达式创建一个堆栈框架（也许其他人可以在这里加入）。同样，sizeof将在编译时得到评估，这对于程序在运行时要做的事情少得多。
我的代码输出：

0.0900000000
0.0800000000
0.1000000000
0.0900000000
0.0800000000
0.1000000000

代码输出

0.1600000000
0.1500000000
0.1500000000
0.1500000000
0.1700000000
0.1900000000

这是我运行的代码的版本：

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

bool pal(char * text);

int main() {
    clock_t start, stop;
    start = clock();
    for(int j = 0; j < 10000000; j++) {
        pal("racecar");
    }
    stop = clock();
    printf("%.10f\n", (double) (stop - start) / CLOCKS_PER_SEC);
    return 0;
}

bool pal(char *text) {
    char *right = text + strlen(text);
    while(text < --right) {
        if(*text++ != *right) {
            return false;
        }
    }
    return true;
}

这是我写的内容：

#include <stdio.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

#define pal(STRING)                         \
  ({bool ret = true;                        \
  char * left = STRING;                     \
  char * right = left + sizeof(STRING) - 2; \
  while(right > left){                      \
    if(*right != *left){                    \
      ret = false;                          \
      break;                                \
    }                                       \
    --right;                                \
    ++left;                                 \
  } ret;})

int main() {
    clock_t start, stop;
    start = clock();
    for(int j = 0; j < 10000000; j++) {
        pal("racecar");
    }
    stop = clock();
    printf("%.10f\n", (double) (stop - start) / CLOCKS_PER_SEC);
    return 0;
}

#10 楼

在这里的许多好建议中，没有一个可以解决您除了回文循环之外还对其他代码进行基准测试这一事实。添加一个stop变量，并确保您的start和stop变量直接包围该循环：

int main() {
    clock_t start;
    clock_t stop;
    int j;

    start = clock();

    for(j = 0; j < 1000000; j++) {
        palindrome("racecar");
    }

    stop = clock();

    printf("%.10f", (double) (stop - start) / CLOCKS_PER_SEC);
    return 0;
}