我目前有以下这个循环
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语言字符串比较方法？
strcmp通常被所有供应商进行了优化。但是，如果您对此不满意，可以尝试以下方法：
libc曾经针对小字符串进行过这种优化，在其中将长度小于五个字节的字符串作为整数进行测试。MS cl也对小字符串进行了一些优化（请查阅相关资料）。但更重要的是确保strcmp是您的真正瓶颈。
cl ...”语句的链接吗？还有，“GNU libc曾经有过…”这个语句的链接也可以吗？谢谢。 - Vishwajith.Kstrcmp函数绝对不是瓶颈。通常情况下，strcmp已经被优化得非常好了，并且可以对长于4/8字节的字符串进行32位或64位比较，具体取决于架构。新libc和GNU libc都是如此。但即使您要在两个字符串中每个字节上查看20次，也不像算法和数据结构选择所做的那样重要。在进行调用之前，通过检查问题字符串的前几个字符，可以节省一些时间。显然，如果第一个字符不同，则没有理由调用strcmp来检查其余部分。由于自然语言中字母的非均匀分布，因此大写数据的回报率不是26：1，而更像是15：1。
#define QUICKIE_STRCMP(a, b) (*(a) != *(b) ? \
(int) ((unsigned char) *(a) - \
(unsigned char) *(b)) : \
strcmp((a), (b)))
#define QUICKIE_STRCMP(a, b, offset) \
(*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))
strcmp() 来实现非常快的字符串比较（标准 8 位 char），如果你事先知道字符串长度。我对比了字节比较宏和 glibc 的 strcmp()，宏版本明显优于 strcmp() 实现；它利用了 CPU 的 矢量处理器。#define str3_cmp(x, y0, y1, y2, y3) x[0] == y0 && x[1] == y1 && x[2] == y2 && x[3] == y3
static inline bool str3_cmp_helper(const char *x, const char *y) {
return str3_cmp(x, *y, *(y + 1), *(y + 2), *(y + 3));
}
const char *i = "hola"; // dynamically generated (eg: received over a network)
if (str3_cmp_helper(i, "hola")) {
/* do something */
} else {
/* do something else */
}
#!/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);
?>
脚本示例：$ ./gen_faststrcmp.php 3 5 fast_strcmp.h。
这将生成fast_strcmp.h，其中包含用于比较长度为3和5的字符串的宏：
#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 */ }
你已经在进行优化编译了，对吧？
如果你有 Trie 或 hashtable 数据结构可供使用，那么最好使用它们。
如果没有，一个相当简单的改变可以加速程序，那就是在开始生成字符串搜索之前，对数组 line 进行一次排序。然后在排序后的数组中用二分查找来搜索 buffer。这很容易实现，因为你只需要使用两个标准函数——qsort 和 bsearch。
在已排序的数组中进行二分查找只需要进行约 log2(filelines) 次字符串比较，而不是 filelines 次。因此，在你的情况下，每次调用 generate_string 只需要进行大约 20 多次字符串比较，而不是几百万次。根据你提供的数据，我认为你可以合理地期望它的速度会快 20-25 倍，但我不能保证。
qsort()的名称暗示它可能是快速排序，其最坏情况下的性能为O(N*N)。除非我确定qsort()在目标平台上的行为，否则我会选择平均较慢但最坏情况下更快的hepasort或smoothsort。 - Brian McFarlandqsort 的优点在于它是标准的。如果我必须自己完成这项工作，那么说实话，我宁愿编写哈希表而不是堆排序 :-) 无论如何，启动时间是否重要并不完全清楚，与我们运行时每秒生成的字符串数量相比。如果启动时间并不真的很重要，那么将 qsort 实现为冒泡排序就绰绰有余了！ - Steve Jessoplines 中的字符串列表是否可能被恶意构造为快速排序和/或哈希杀手。如果你担心这种情况，那么你必须决定是编写自己的算法，还是选择一个标准库，其中 qsort 是抗攻击的。 - Steve Jessop对于普通字符串，请使用strcmp。但如果字符串非常长，您可以使用memcmp。它将比较内存块。
这取决于字符串的长度。
如果不是太长，你可以尝试逐字节比较：
str[0] == str2[0] && str[1] == str2[1] && str[2] == str2[2]
memcmp()，它可以比较内存块。strcmp更快的字符串比较方法，但是你可以通过使用哈希表来存储你的字符串，从而避免频繁调用strcmp。然后，你可以检查buffer中的字符串是否在哈希表中。如果命中的索引在“做某事”时很重要，那么该表可以将字符串映射到索引。