11

我目前有这种循环

while(1)
{
    generate_string(&buffer);

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

我有一个包含几百万个字符串的文件（希望很快会减半），所有这些字符串的数量都存储在文件行中

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

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

4

11 回答 11

15

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

  • 查找突发尝试
  • 使用后缀树进行快速字符串比较——参见这篇文章
  • 根据应用程序中字符串的大小，您可以编写自定义字符串比较器。例如：GNUlibc曾经对小字符串进行过这种优化，他们将小于 5 个字节的字符串作为整数进行测试。MScl还对小字符串进行了一些优化（请查一下）。

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

于 2012-05-23T14:57:22.013 回答
6

我可以向你保证，这个功能strcmp绝对不是瓶颈。通常，strcmp 进行了很好的优化，可以根据架构对超过 4/8 字节的字符串进行 32 位或 64 位比较。newlib 和 GNU libc 都这样做。但是，即使您要查看两个字符串中的每个字节 20 次，也没有这里选择的算法和数据结构那么重要。

真正的瓶颈是 O(N) 搜索算法。文件中的单个 O(N log N) 传递可用于在适当的数据结构（无论是普通的 BST、trie 还是简单的排序数组）上进行 O(log N) 查找。

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

在 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 次操作，或 999,600 次操作比在未排序数组上的 O(N) 搜索要好。因此，在 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 次操作。

2,001,000,000 / 20,020,000 ~= 100 倍于 O(N) 搜索的操作。

在 1e6 次搜索中，即 (1e6 + 1e6 * 1e6) / (20e6 + 1e6 * 20 ) = 25,000 倍的操作。

假设您的计算机可以在 1 分钟内处理进行 log N 搜索所需的 40e6 次“操作”。使用您当前的算法完成相同的工作需要 25,000 分钟或 17 天。或者另一种看待方式是，O(N) 搜索算法只能处理 39 次搜索，而 O(log N) 算法可以执行 1,000,000 次。你做的搜索越多，它就越难看。

有关数据结构和算法的几种更好选择，请参阅 Steve 和 dirkgently 的回复。我唯一需要注意的是，qsort()史蒂夫建议的最坏情况复杂度可能为 O(N*N)，这比使用堆排序或各种树状结构得到的 O(N log N) 还要糟糕得多结构。

于 2012-05-23T16:13:08.537 回答
5

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)))
于 2014-01-31T13:06:06.623 回答
2

如果我正确地回答了您的问题，您需要检查一个字符串是否符合目前所读取的所有行。我建议从文件行中使用 TRIE 甚至更好的Patricia 树。这种方式而不是遍历所有行，您可以线性检查您的字符串是否存在（并且需要更多的努力 - 在哪里）。

于 2012-05-23T14:57:25.163 回答
1

你已经在编译优化了，对吧？

如果你有一个 Trie 或哈希表数据结构，可以随时使用，那么你应该这样做。

如果做不到这一点，一个可能会加快速度的相当简单的更改是line在开始生成要搜索的字符串之前对数组进行一次排序。然后buffer在排序后的数组中进行二分查找。这很容易，因为您需要的两个功能是标准的 -qsort和bsearch.

对已排序数组的二进制搜索只需要对 log 2（文件行）字符串进行比较，而不是关于文件行。因此，在您的情况下，每次调用要进行 20 次字符串比较，generate_string而不是几百万。根据您提供的数据，我认为您可以合理地预期它会快 20-25 倍，尽管我不保证。

于 2012-05-23T15:04:25.687 回答
1

我对使用strcmp()和宏进行了基准测试，以逐字节进行比较。与strcmp(). 通常对于字符串比较，使用字节比较器宏要快得多，而不是strcmp(). 前任：

#define str3_cmp(m, c0, c1, c2, c3) m[0] == c0 && m[1] == c1 && m[2] == c2 && m[3] == c3

与 相比，这“非常”快strcmp()。但是把这些写下来是一件很痛苦的事情，而且你需要逐个字符地拆分字符串，所以我编写了一个方便的 PHP 脚本来为你生成它作为头文件。

您可以在热循环中使用此字符串比较，您可以确切地知道char*要比较的大小。

#!/usr/bin/php
<?php
function generate_macro($num) : string {
        $returner = "#define str".$num."cmp_macro(ptr, ";
        for($x = 0; $x < $num; $x++){
                $returner .= "c".$x;
                if($x != $num-1){ $returner .= ", "; }
        }
        $returner .= ") ";
        for($x = 0; $x < $num; $x++){
                $returner .= "*(ptr+".$x.") == c".$x;
                if($x != $num-1){ $returner .= " && "; }
        }
        return $returner;
}
function generate_static_inline_fn(&$generated_macro, $num) : string {
        $generated_macro .= "static inline bool str".$num."cmp(const char* ptr, const char* cmp)".
                                "{\n\t\treturn str".$num."cmp_macro(ptr, ";
        for($x = 0; $x < $num; $x++){
                $generated_macro .= " *(cmp+".$x.")";
                if($x != $num-1){ $generated_macro .= ", "; }
        }
        $generated_macro .= ");\n}\n";
        return $generated_macro;
}

function handle_generation($argc, $argv) : void {
        $out_filename = $argv[$argc-1];
        $gen_macro = "";
        for($x = 0; $x < $argc-2; $x++){
                $macro = generate_macro($argv[$x+1])."\n";
                $gen_macro .= generate_static_inline_fn($macro, $argv[$x+1]);
        }
        file_put_contents($out_filename, $gen_macro);
}
handle_generation($argc, $argv);
?>

这个脚本有两个参数。

  1. 你的大小char*会比较。
  2. 输出头文件名。

示例：$ ./gen_faststrcmp.php 3 5 fast_strcmp.h 这将生成fast_strcmp.h内容

#define str3cmp_macro(ptr, c0, c1, c2) *(ptr+0) == c0 && *(ptr+1) == c1 && *(ptr+2) == c2
static inline bool str3cmp(const char* ptr, const char* cmp){
                return str3cmp_macro(ptr,  *(cmp+0),  *(cmp+1),  *(cmp+2));
}
#define str5cmp_macro(ptr, c0, c1, c2, c3, c4) *(ptr+0) == c0 && *(ptr+1) == c1 && *(ptr+2) == c2 && *(ptr+3) == c3 && *(ptr+4) == c4
static inline bool str5cmp(const char* ptr, const char* cmp){
                return str5cmp_macro(ptr,  *(cmp+0),  *(cmp+1),  *(cmp+2),  *(cmp+3),  *(cmp+4));
}

在您的代码中，您可以像这样使用该函数，

const char* compare_me = "Hello";
if(str5cmp(compare_me, "Hello")) { /* code goes here */ }
于 2020-12-15T17:03:28.643 回答
0

我不知道有比调用strcmp字符串比较更快的方法，但你也许可以避免调用strcmp这么多。使用哈希表存储您的字符串，然后您可以检查字符串是否buffer在哈希表中。如果在您“做某事”时命中的索引很重要，则该表可以将字符串映射到索引。

于 2012-05-23T14:51:10.963 回答
0

你可以尝试一些“便宜”的东西，比如基于第一个字符的筛选。如果第一个字符不匹配，则字符串不能相等。如果它们匹配，则调用 strcmp 来比较整个字符串。如果适合您的情况，您可能希望考虑更好的算法；例如，使用哈希表或类似的字符串表技术对文件/行进行排序并进行二进制搜索。

于 2012-05-23T14:55:26.163 回答
0

在这种情况下，您可能可以通过二进制比较来解决问题，因为您的程序实际上并没有排序，而是比较是否相等。

您还可以通过提前确定长度来提高比较速度（当然前提是它们变化足够大）。当这里的长度不匹配时，do something不会发生。

当然，这里的散列将是另一个考虑因素，具体取决于您读取散列值的次数。

于 2012-05-23T14:56:13.073 回答
0

这取决于字符串的长度。

如果不是太长，可以尝试逐字节比较：

str[0] == str2[0] && str[1] == str2[1] && str[2] == str2[2]

否则，使用memcmp()，它比较内存块。

于 2021-11-02T20:53:42.183 回答
0

用于strcmp常规字符串。但是如果字符串真的很长，你可以使用memcmp. 它将比较内存块。

于 2021-12-05T21:14:41.703 回答