logo标签列表

优化'if/else' strcmp()梯形结构以确定可用值

chashordinals
3
//...
if( strcmp( str, "January" ) == 0 )
    month = 1;
else if( strcmp( str, "February") == 0 )
    month = 2;
//...

问：有没有更有效的方法确定例如“四月”是一年中的第四个月？多次调用strcmp()非常低效，而if/else阶梯编码很繁琐。有时是“三月”，有时缩写为“MAR”...必须有更好的方法...

将已知字符串放入排序后的结构体数组中，至少可以进行二进制搜索，但仍需要代码进行许多猜测。

2
查找 gperf 以提前生成键的完美哈希。 - Shawn
1
构建一个 trie 并使用它进行快速查找可能是值得的：https://en.wikipedia.org/wiki/Trie - Jeremy Friesner
3
当然可以。您可以将月份/数字放入按字母顺序排列的表中，并使用二分查找。但这只是最简单的方法。静态集合的查找已经被广泛研究。一些更高级的选项包括完美哈希函数（尝试搜索Gnu工具“gperf”），最优二叉搜索树或trie。但不要过于急于优化。对于仅有12个元素，if链和这些“更有效”的方法之间的差异不太可能产生实际差异。简单性也有其自身的价值。 - Gene
1
@Shawn 感谢你的指引。gperf 看起来很有趣，但比下面回答中发现和发布的快速（且特定）哈希函数要大。我发表这篇文章是因为有人可能在某个时候、某个地方会觉得它有用。干杯！... - Fe2O3
1
通常在效率和可读性之间做出良好的折衷是将所有常量字符串文字放入排序表中，然后通过二进制搜索进行查找。在这种特定情况下，只需要比较12个字符串，因此（根据系统）直接使用for循环调用strcmp可能是最有效的方法。 - Lundin
显示剩余3条评论
3个回答
6

这是一个我可以回答自己的问题吗？的答案。欢迎其他答案。

有几种方法可以将一个有限字符串集合中的任意字符串转换为简洁、可用的形式。 其中大多数涉及迭代（或次优线性）搜索，需要进行重复比较（可能需要考虑大小写敏感性）。

对我最近提出的问题的回应建议“共享”一个（尽管晦涩）哈希函数， 当传递包含英文月份名称的字符串（7位ASCII）时，该函数会返回月份序数（1-12）， 并且具有误报率意识。该函数对第二个和第三个字符执行原始操作， 并弹出字符串的哈希值。请注意，“January”，“jan”和“JAN”都返回值1。 同样，“feb”，“FEBRUARY”和“Feb”将返回值2。

static int monthOrd( char cp[] ) {
    return "DIE@CB@LJF@HAG@K"[ cp[1]/4&7 ^ cp[2]*2 &0xF ] &0xF;
}

通过对多个基本操作进行“暴力”排列，找到了所显示的操作组合，以返回在0x0和0xF（4位）之间12个不同值的结构。 鼓励读者分解两个ASCII字符位混合的每一步。 这个结果并不是“发明”的，而是被“发现”的。

在两个字符的位被混淆后， 该值被用作一个字符串的索引(又名“廉价LUT”), 该字符串由12个字母A-L组成，这些字母被放置在一起， 以使得“？an”（1月）会混淆为字母“A”的索引。 屏蔽该字母的低4位将产生值1作为字符串“JANUARY”的顺序... 当函数传递“Jan”字符串的变化时，将返回1。

注：使用此函数允许调用者检查字符串是否确实为“JAN”，“jan”，“January”，以适应应用程序。 调用者无需尝试匹配其他11个月份名称中的任何一个名称。 此函数将为字符串“Random”返回假阳性值1， 因此调用者只需要针对单个月份的名称进行验证（长度和大小写适合于应用程序）。

额外加分环节：

static int wkdayOrd( char cp[] ) {
    return "65013427"[*cp/2 + ~cp[1] & 0x7] & 0x7;
}

一个等效的函数，将“Sun(day)”（不区分大小写）转换为1，“MON”转换为2，“tue”转换为3，等等...
同样，调用者必须仅针对一天的名称确认字符串，以避免“误报”。

顺便提一下，以下是一个等效的函数，用于从“零”到“十”的“数字名称”，同样不区分大小写。 （数字名称不像月份名称或工作日名称那样缩写。）

static int numberOrd( char cp[] ) {
    return "@~IBAH~FCGE~~DJ~"[ ( cp[0] ^ cp[1]/2 + cp[2]*4 ) & 0xF ] & 0xF;
}

编辑
为了反驳那些持否定态度的人，这里再来一个：

static int ZodiacOrd( char cp[] ) {
    return "BJGA@@HIECK@@DLF"[(cp[0]/2 ^ (cp[1]/2&1) + cp[2]*2) & 0xF] & 0xF;
}

将十二星座之一的名称（大小写不敏感）传递给它，它会返回该星座的序号（“白羊座”= 1，...）。像任何哈希函数一样，它会与其他字符串发生冲突。调用者只需随后检查单个已知字符串而不是十二个字符串即可。
为什么有些人由于无法理解小型受限词汇表的哈希而选择停留在分支猜测中？
1
return "DIE@CB@LJF@HAG@K"[ cp[1]/4&7 ^ cp[2]*2 &0xF ] &0xF; 你尝试通过同行评审了吗？他们说了什么？ - 0___________
1
@CostantinoGrana 谢谢你的UV...必须至少有一个“验证”，以确保未知字符串与已知字符串匹配。循环和分支不便宜。这种“无分支”的确定唯一潜在匹配项以验证未知项可以节省周期。我最初写了类似于此的东西（使用更大的LUT更简单）40年前为PDP11/34编写。这意味着该工作已完成并清除，涉及更少的浪费交换在那1/2Mb的核心系统上。 - Fe2O3
2
@0___________ 你没有理解重点。 "Luty" 不是任何月份的名称，但哈希值与 "July" 完全相同... 由于单个 strcmp() 显示 "Luty" 不是 "July"，因此工作已完成。 没有必要进行多达11次 strcmp() 的调用来检查其他可能性... 即使函数返回7，"Julie" 也不是 "July"... 使用哈希值，只需要一个“验证”即可；不需要更多。 - Fe2O3
3
恭喜你。你已经充分优化了将月份名称转换为整数的过程。太棒了。这是一个很酷的技巧，但我敢打赌，在代码的生命周期内，它节省的时间甚至不会接近你构建它所花费的时间。如果我在代码审查中遇到这样的东西，我不会让它通过。你可能能够解释它，但它并不清晰且无法证明是正确的代码。所以，对于这个酷炫的技巧，你做得很好。我想。 - Jim Mischel
1
在这些情况下，在运行时进行快速查找不会有问题，因为您无论如何都要根据日期进行一些计算。 - Lundin
显示剩余9条评论
4
我已经检查了使用 gperf 将所有月份设置为 "January"、"Jan"、"JANUARY"、"JAN"、"january"、"jan" 等等时会发生什么。
struct months {
char *name;
int number;
};

#define TOTAL_KEYWORDS 69
#define MIN_WORD_LENGTH 3
#define MAX_WORD_LENGTH 9
#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 218
/* maximum key range = 216, duplicates = 0 */

#ifdef __GNUC__
__inline
#else
#ifdef __cplusplus
inline
#endif
#endif
static unsigned int
hash (register const char *str, register size_t len)
{
  static unsigned char asso_values[] =
    {
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219,  10,  80,  75,  95,   5,
      125,  95, 219, 219,   5, 219,  95,  55,  45,  60,
       60, 219,  85,  95,  50,  90,  25, 219, 219,  12,
      219, 219, 219, 219, 219, 219, 219,   0,  40,  35,
       35,  35,  40,  25, 219, 219,   0, 219,  10,  50,
        0,  25,  15, 219,  15,  35,  30,  10,  25, 219,
      219,  25, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219, 219, 219, 219, 219,
      219, 219, 219, 219, 219, 219
    };
  return len + asso_values[(unsigned char)str[2]] + asso_values[(unsigned char)str[1]] + asso_values[(unsigned char)str[0]];
}

struct months *
in_word_set (register const char *str, register size_t len)
{
  static struct months wordlist[] =
    {
      {""}, {""}, {""},
      {"jan",1},
      {""}, {""}, {""},
      {"january",1},
      {"Jan",1},
      {""}, {""}, {""},
      {"January",1},
      {"jun",6},
      {"june",6},
      {""}, {""}, {""},
      {"Jun",6},
      {"June",6},
      {""}, {""}, {""},
      {"jul",7},
      {"july",7},
      {""}, {""}, {""},
      {"Jul",7},
      {"July",7},
      {""}, {""}, {""},
      {"apr",4},
      {""},
      {"april",4},
      {""}, {""},
      {"aug",8},
      {""}, {""},
      {"august",8},
      {""},
      {"Apr",4},
      {""},
      {"April",4},
      {""}, {""},
      {"Aug",8},
      {""}, {""},
      {"August",8},
      {""},
      {"nov",11},
      {""}, {""}, {""}, {""},
      {"november",11},
      {""}, {""}, {""}, {""},
      {"JAN",1},
      {""}, {""}, {""},
      {"JANUARY",1},
      {"mar",3},
      {""},
      {"march",3},
      {""}, {""},
      {"Mar",3},
      {""},
      {"March",3},
      {""}, {""},
      {"may",5},
      {""},
      {"MAY",5},
      {""}, {""},
      {"May",5},
      {""}, {""}, {""}, {""},
      {"sep",9},
      {""}, {""}, {""}, {""},
      {"oct",10},
      {"september",9},
      {""}, {""},
      {"october",10},
      {"Nov",11},
      {""}, {""}, {""}, {""},
      {"November",11},
      {""}, {""}, {""}, {""},
      {"dec",12},
      {""}, {""}, {""}, {""},
      {"december",12},
      {""}, {""}, {""}, {""},
      {"feb",2},
      {""}, {""}, {""}, {""},
      {"february",2},
      {""}, {""}, {""}, {""},
      {"Oct",10},
      {""}, {""}, {""},
      {"October",10},
      {"NOV",11},
      {""}, {""}, {""}, {""},
      {"NOVEMBER",11},
      {""}, {""}, {""}, {""},
      {"JUN",6},
      {"JUNE",6},
      {""}, {""}, {""},
      {"Sep",9},
      {""}, {""}, {""}, {""},
      {"MAR",3},
      {"September",9},
      {"MARCH",3},
      {""}, {""},
      {"APR",4},
      {""},
      {"APRIL",4},
      {""}, {""},
      {"SEP",9},
      {""}, {""}, {""}, {""},
      {"Dec",12},
      {"SEPTEMBER",9},
      {""}, {""}, {""},
      {"December",12},
      {""}, {""}, {""}, {""},
      {"DEC",12},
      {""}, {""}, {""}, {""},
      {"DECEMBER",12},
      {""}, {""}, {""}, {""},
      {"OCT",10},
      {""}, {""}, {""},
      {"OCTOBER",10},
      {"JUL",7},
      {"JULY",7},
      {""}, {""}, {""},
      {"AUG",8},
      {""}, {""},
      {"AUGUST",8},
      {""},
      {"Feb",2},
      {""}, {""}, {""}, {""},
      {"February",2},
      {""}, {""}, {""}, {""},
      {"FEB",2},
      {""}, {""}, {""}, {""},
      {"FEBRUARY",2}
    };

  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
    {
      register unsigned int key = hash (str, len);

      if (key <= MAX_HASH_VALUE)
        {
          register const char *s = wordlist[key].name;

          if (*str == *s && !strcmp (str + 1, s + 1))
            return &wordlist[key];
        }
    }
  return 0;
}

我猜这很快，每个字符串只需要一个strcmp。这正是GCC用于关键字检查的方法。

有一个非常好的gperf介绍可以在这里找到。

哇！谢谢你做这个。:-)……这真是令人印象深刻！UV正在路上！ - Fe2O3
1
这里有一个简单的解决方案，应该更高效，并且会检查正确的拼写。
#include <string.h>

int get_month_number(const char *s) {
    if (s && s[0] && s[1]) {
        switch (s[2]) {
          case 'n': return !strcmp(s, "Jan") || !strcmp(s, "January")   ? 1 :
                           !strcmp(s, "Jun") || !strcmp(s, "June")      ? 6 : 0;
          case 'b': return !strcmp(s, "Feb") || !strcmp(s, "February")  ? 2 : 0;
          case 'r': return !strcmp(s, "Mar") || !strcmp(s, "March")     ? 3 :
                           !strcmp(s, "Apr") || !strcmp(s, "April")     ? 4 : 0;
          case 'y': return !strcmp(s, "May")                            ? 5 : 0;
          case 'l': return !strcmp(s, "Jul") || !strcmp(s, "July")      ? 7 : 0;
          case 'g': return !strcmp(s, "Aug") || !strcmp(s, "August")    ? 8 : 0;
          case 'p': return !strcmp(s, "Sep") || !strcmp(s, "September") ? 9 : 0;
          case 't': return !strcmp(s, "Oct") || !strcmp(s, "October")   ? 10 : 0;
          case 'v': return !strcmp(s, "Nov") || !strcmp(s, "November")  ? 11 : 0;
          case 'c': return !strcmp(s, "Dec") || !strcmp(s, "December")  ? 12 : 0;

        }
    }
    return 0;
}

如果你可以假设s指向的是一个至少包含3个字符的字符串，代表一个英文月份的名称（可以是缩写或不缩写），不论大小写，你可以简化上述代码，同时保持可读性：
// return the month number 0..11 assuming argument is correct.
int get_month_number(const char *s) {
#define HASH(a,b,c)  ((((b) | 0x20) == 'a') + ((c) & 0x1f))
    switch (HASH(s[0],s[1],s[2])) {
      default:
      case HASH('J','a','n'): return 0;
      case HASH('F','e','b'): return 1;
      case HASH('M','a','r'): return 2;
      case HASH('A','p','r'): return 3;
      case HASH('M','a','y'): return 4;
      case HASH('J','u','n'): return 5;
      case HASH('J','u','l'): return 6;
      case HASH('A','u','g'): return 7;
      case HASH('S','e','p'): return 8;
      case HASH('O','c','t'): return 9;
      case HASH('N','o','v'): return 10;
      case HASH('D','e','c'): return 11;
    }
#undef HASH
}

这里是一个替代方案，使用查找表而不是switch语句：
// return the month number 0..11 assuming argument is correct.
int get_month_number(const char *s) {
#define HASH(a,b,c)  ((((b) | 0x20) == 'a') + ((c) & 0x1f))
    static const unsigned char month_num[33] = {
        [ HASH('J','a','n') ] = 0,
        [ HASH('F','e','b') ] = 1,
        [ HASH('M','a','r') ] = 2,
        [ HASH('A','p','r') ] = 3,
        [ HASH('M','a','y') ] = 4,
        [ HASH('J','u','n') ] = 5,
        [ HASH('J','u','l') ] = 6,
        [ HASH('A','u','g') ] = 7,
        [ HASH('S','e','p') ] = 8,
        [ HASH('O','c','t') ] = 9,
        [ HASH('N','o','v') ] = 10,
        [ HASH('D','e','c') ] = 11,
    };
    return month_num[HASH(s[0],s[1],s[2])];
#undef HASH
}

如您在 Godbolt's Compiler Explorer上所见，这两个函数在gcc和clang编译器下生成无分支代码。而且，switch语句还可以免费检测哈希冲突。这两个函数都可以使用您的哈希函数。
#define HASH(a,b,c)  ((b)/4&7 ^ (c)*2&0xF)
需要调用者将候选人隔离为以空字符结尾的字符串。可能需要一次或两次，甚至三次调用strcmp()来确定"June"。希望消除或减少对strcmp()的调用！当源更改为混合大小写到全部大写时，这种方法是否仍然有效？例如 "JAN"？而且，stricmp()的开销会比strcmp()更高...（注意：我的更新答案将从1-12和0更改为struct tm的约定，使用12代表NAM（即：绝对不是月份的名字！甚至不接近！）。） - undefined
我的回答将“正确拼写”的决定留给调用者。如果候选字符串的来源可靠（例如C程序中的__DATE__中的3个字母月份名称），则无需检查拼写。只想将25 DEC 2023的月份区域转换为11（其中Jan == 0）... - undefined
内存便宜且丰富（除了在嵌入式系统中，它是一个重要的考虑因素）。这就是为什么gperf的想法不是一个好的通用解决方案。由于它有23个字符串字面量，这个解决方案可能会消耗所需平台有限的资源。 - undefined
1
@Fe2O3：你的解决方案虽然紧凑，但如果没有详尽的分析，是无法验证的。将你的方法应用到其他语言中更加困难。我修改了我的答案，提供了一些替代版本，既结合了代码和数据的紧凑性，又采用了一种既可读性又易于验证的方法。我也记得那些日子，我会花几个小时寻找方法来减少一些CPU周期和一些内存字节...谢谢你唤起了这些美好的回忆 :) - undefined
1
这真是有趣，不是吗？:-)... 你添加的两个解决方案对于读者来说更加明显（比我的）并且更易于维护！干得好！我以前写的版本也使用了类似你的稀疏数组，但我没有看到你在这里使用的更清晰/聪明的哈希函数。很棒！ - undefined
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接