C中的快速字符串比较

Question

我目前有这种循环

while(1)
{
    generate_string(&buffer);

    for(int i = 0; i < filelines; i++)
    {
        if(strcmp(buffer,line[i]) == 0)
        {
           /*  do something  */
        }
    }
}

我有一个包含几百万个字符串的文件(希望很快就会减半),所有这些字符串的数量都存储在filelines中

line [i]基本上是存储字符串本身的位置.

目前,由于这些百万字符串的比较,函数generate_string(&buffer); 每秒执行约42次.有没有更快的方法在C中进行字符串比较？

Answer 1

strcmp通常由所有供应商优化.但是,如果您对此不满意,可以尝试:

• Lookup Burst尝试
• 使用后缀树进行快速字符串比较 - 请参阅此文章
• 根据应用程序中字符串的大小,您可以编写自定义字符串比较器.例如:GNU libc曾经对小字符串进行优化,他们测试小于5个字节的字符串作为整数.MS cl还对小字符串进行了一些优化(请查看).

但更重要的是确保strcmp是你真正的瓶颈.

Answer 2

我可以向你保证,这个功能strcmp绝对不是瓶颈.通常,strcmp经过了很好的优化,可以对长度超过4/8字节的字符串进行32位或64位比较,具体取决于体系结构.newlib和GNU libc都这样做.但是,即使您要查看两个字符串中的每个字节20次,这与此处做出的算法和数据结构选择无关.

真正的瓶颈是O(N)搜索算法.文件中的单个O(N log N)传递可用于进行O(log N)查找的适当数据结构(无论是正常的BST,trie还是仅仅是简单的排序数组).

跟我在一起 - 接下来是很多数学.但我认为这是一个很好的机会来说明为什么算法和数据结构的选择有时比字符串比较方法更重要.史蒂夫谈到这一点,但我想更深入地解释它.

当N = 1e6时,log(1e6,2)= 19.9,因此在理想数据结构上进行最多20次比较.

目前,您正在进行O(N)或1e6操作的最坏情况搜索.

所以说你只需要构建一个红黑树,插入时间为O(log N),然后插入N个项目,即构建树的O(N log N)时间.这就是构建树所需的1e6 x 20或20e6操作.

在您当前的方法中,构建数据结构是O(N)或1e6操作,但最坏情况下的搜索时间也是O(N).因此,当您阅读文件并执行20次搜索操作时,您将达到21,000,000次操作的理论最坏情况.相比之下,使用红黑树和20次搜索的最坏情况是20,000,400次操作,或比未排序阵列上的O(N)搜索更好的999,600次操作.因此,在20次搜索中,您处于第一个更复杂的数据结构真正得到回报的地方.但看看1000次搜索会发生什么:

未排序的数组=初始化+ 1000 x搜索时间= O(N)+ 1000*O(N)= 1,000,000 + 2,000,000,000 = 2,001,000,000次操作.

红黑=初始化+ 1000 x搜索时间= O(N log N)+ 1000*O(log N)= 20,000,000 + 20,000 = 20,020,000次操作.

O(N)搜索的操作数量为2,001,000,000/20,020,000~ = 100x.

在1e6搜索时,那是(1e6 + 1e6*1e6)/(20e6 + 1e6*20)= 25,000x尽可能多的操作.

假设您的计算机可以处理在1分钟内进行日志N搜索所需的40e6'操作'.使用当前算法执行相同的工作需要25,000分钟或17天.或者另一种观察方式是O(N)搜索算法在O(log N)算法可以做1,000,000时只能处理39次搜索.你做的搜索越多,它就越丑陋.

有关数据结构和算法的几种更好选择,请参阅Steve和dirkgently的回复.我唯一需要注意的是,qsort()史蒂夫可能会出现最坏情况下的O(N*N)复杂性,这种情况远远超过你使用堆或类似树的O(N log N)结构.

Answer 3

用 C 语言优化计算机程序

您可以通过在调用之前检查相关字符串的第一个字符来节省一点时间。显然，如果第一个字符不同，则没有理由调用 strcmp 来检查其余字符。由于自然语言中字母的非均匀分布，大写数据的收益不是 26:1，而是更像是 15:1。

#define QUICKIE_STRCMP(a, b)  (*(a) != *(b) ? \  
  (int) ((unsigned char) *(a) - \
         (unsigned char) *(b)) : \
  strcmp((a), (b)))

如果您使用的单词词典定义明确（意味着您不介意以 strcmp 形式返回值，而是 0==equal），例如，一组以相同前缀开头的命令行参数，例如：tcp-accept , tcp-reject 比你可以重写宏并做一些指针算术来比较不是第一个而是第 N 个字符，在这种情况下，第 4 个字符，例如：

   #define QUICKIE_STRCMP(a, b, offset) \
            (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))