logo标签列表

如何优化下面的多个strncmp？

calgorithm
5

我需要检查字符串是否与任何前缀匹配。将来要比较的前缀数量将增加。所以我对以下代码的性能有疑虑。当需要检查很多字符串时，有哪些选项可以使它运行更快？

int checkString(const char *name)
{
    if(!name) return 0;

    if(strncmp(name, "AE_", 3) == 0 ) return 1;                                                                              
    if(strncmp(name, "AEDZ_", 5) == 0 ) return 1;                                                                            
    if(strncmp(name, "EDPZ_", 5) == 0 ) return 1;                                                                            
    if(strncmp(name, "EFAN_", 5) == 0 ) return 1;                                                                            
    if(strncmp(name, "E_GCA", 5 ) == 0 ) return 1;                                                                           
    if(strncmp(name, "EFFAN_", 6) == 0 ) return 1;                                                                           
    if(strncmp(name, "EPDPZ_", 6) == 0 ) return 1;                                                                           
    if(strncmp(name, "EDDPZ_", 6) == 0 ) return 1;                                                                           
    if(strncmp(name, "ECADF_", 6) == 0 ) return 1;                                                                           
    if(strncmp(name, "EPCEA_", 6) == 0 ) return 1;                                                                           
    if(strncmp(name, "CFEXXX_", 7) == 0 ) return 1;                                                                          
    if(strncmp(name, "IFEXX_", 7) == 0 ) return 1;                                                                           
    if(strncmp(name, "EINFFAN_", 8) == 0 ) return 1;                                                                         
    if(strncmp(name, "NXXEFAN_", 8) == 0 ) return 1;                                                                         
    if(strncmp(name, "ENAEAZY_", 8) == 0 ) return 1;                                                                         
    if(strncmp(name, "EYYYYYY_", 8) == 0 ) return 1;                                                                         
    if(strncmp(name, "ENEOENUE_", 9) == 0 ) return 1;                                                                        
    /*
    more strncmp to be added.
    */

    return 0;
}
1
这显然是C语言，而不是C++（因为C++会使用std::string，所以不需要使用strncmp()）。请不要在C问题中使用C++标签。 - Barmar
如果你要有很多的话，使用B树可能是更有效的方法。 - Barmar
4
“Trie”或许是解决方案。 - Blastfurnace
5
多少个字符串，多少次查找？哈希表、二分查找数组、字典树 - 有很多选择。 - 500 - Internal Server Error
1
首先，“最好”的要求是您提供更好的精确描述，否则这只是在征求意见。话虽如此，对您的代码最简单的改进是使用循环。作为新用户，请参加[tour]并阅读[ask]。 - Ulrich Eckhardt
显示剩余2条评论
3个回答
3

一次性、提前设置：

regex_t re;
regcomp(&re, "^(AE_|AEDZ|_EDPZ_|EFAN_|E_GCA|" /*...*/ ")", REG_EXTENDED);

检查：

return regexec(&re, name, 0, 0, 0) == 0;

在任何优秀的正则表达式实现中，regcomp会将正则表达式编译为一个DFA（确定性有限状态自动机），该DFA执行的步骤数量受最长前缀长度的限制。

在我的电脑上，使用C++11的std::regex比POSIX regex慢两个数量级，即使设置了extended、optimize和nosubs。 - Alex Reinking
@AlexReinking：你指的是哪个C++标准库？GCC的libstdc++？LLVM的libc++？MSVC？还是其他的？无论如何，我不确定C++与这个问题有什么关系。 - R.. GitHub STOP HELPING ICE
抱歉，我应该说明一下GCC 8.2.1的Libstdc++。如果我用C++11来编写它（以便在非POSIX系统上实现可移植性），您的解决方案会是什么样子呢？我认为其他有类似问题的人会感兴趣知道libstdc++并不一定是一个“好的正则表达式实现”。 - Alex Reinking
@AlexReinking：是的。在include/bits/regex_executor.tcc的_M_handle_accept中有一条注释，表明他们正在使用一种极慢的方法来查找POSIX BRE/ERE中|的最长匹配。这可能是问题所在。或者它可能会因为某些非原因而使用回溯引擎。 - R.. GitHub STOP HELPING ICE
2
如果将n个前缀排序，最多只需要log2(n)次比较。代码可以使用bsearch()函数来实现，以提高运行速度。
#include <stdio.h>
#include <stdlib.h>

const char *prefix[] = {"AE_", "AEDZ_", "CFEXXX_", "ECADF_", "EDDPZ_",
    "EDPZ_", "EFAN_", "EFFAN_", "EINFFAN_", "ENAEAZY_", "ENEOENUE_", "EPCEA_",
    "EPDPZ_", "EYYYYYY_", "E_GCA",  "IFEXX_", "NXXEFAN_"};

int cmp(const void *key, const void *element) {
  const char *k = key;
  const char *e = *(const char **) element;
  size_t elen = strlen(e);
  printf("strncmp(%s,%s,%zu)\n", k,e,elen);
  return strncmp(k, e, elen);
}

void test(const char *key) {
  printf("Search for <%s>\n", key);
  size_t n = sizeof prefix/sizeof prefix[0];
  const char **s = bsearch(key, prefix, n, sizeof prefix[0], cmp);
  if (s) {
    printf("Found <%s>\n", *s);
  } else {
    printf("Not Found\n");
  }
}

int main() {
  test("E_GC");
  test("E_GCA");
  test("E_GCA_");
}

输出

Search for <E_GC>
strncmp(E_GC,EINFFAN_,8)
strncmp(E_GC,EYYYYYY_,8)
strncmp(E_GC,IFEXX_,6)
strncmp(E_GC,E_GCA,5)
Not Found
Search for <E_GCA>
strncmp(E_GCA,EINFFAN_,8)
strncmp(E_GCA,EYYYYYY_,8)
strncmp(E_GCA,IFEXX_,6)
strncmp(E_GCA,E_GCA,5)
Found <E_GCA>
Search for <E_GCA_>
strncmp(E_GCA_,EINFFAN_,8)
strncmp(E_GCA_,EYYYYYY_,8)
strncmp(E_GCA_,IFEXX_,6)
strncmp(E_GCA_,E_GCA,5)
Found <E_GCA>
1
一个注意事项：代码需要确保prefix[]数组被正确排序。 - chux - Reinstate Monica
1
这是一个不错的解决方案，但比正则表达式更费力且时间复杂度更高（log n vs 1）。 - R.. GitHub STOP HELPING ICE
-2

如果前缀不会改变而只会添加，且您声明了一个常量来表示您拥有的前缀数量，那么您可以使用 strstr 循环：

#include "stdio.h"
#include "string.h"

#define N_STRINGS 17

int checkString(const char *name);

const char *subStrings[N_STRINGS];

int main() {

    subStrings[0] = "AE_";
    subStrings[1] = "AEDZ_";
    subStrings[2] = "EDPZ_";
    subStrings[3] = "EFAN_";
    subStrings[4] = "E_GCA";
    subStrings[5] = "EFFAN_";
    subStrings[6] = "EPDPZ_";
    subStrings[7] = "EDDPZ_";
    subStrings[8] = "ECADF_";
    subStrings[9] = "EPCEA_";;
    subStrings[10] = "CFEXXX_";
    subStrings[11] = "IFEXX_";
    subStrings[12] = "EINFFAN_";
    subStrings[13] = "NXXEFAN_";
    subStrings[14] = "ENAEAZY_";
    subStrings[15] = "EYYYYYY_";
    subStrings[16] = "ENEOENUE_";

    //run for a random string
    printf("%d\n", checkString("AEDZ_value"));

    return 1;
}

int checkString(const char *name)
{
    int i;

    if(!name) return -1;

    for (i = 0; i < N_STRINGS; i++) {
        if (strstr(name, subStrings[i]) != 0) {
            return i;
        }
    }                                                                 

    return -1;
}

函数checkString将返回前缀的索引。

对于这种情况，可能有更多有效的实现方法。

在这种情况下，strstr比strncmp严格更差。 - R.. GitHub STOP HELPING ICE
同时，像这样动态初始化可变全局变量是一个非常糟糕的想法，因为你可以使用静态初始化器，有几个原因。 - R.. GitHub STOP HELPING ICE
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接