c 检查char是元音还是辅音的最快方法

Question

我有一个问题，涉及使用回溯来查找具有各种规则的许多“单词”（它们不必是真实的）。一些规则涉及我可以一个接一个的元音数量。

我知道我可以使用一个开关，或者一个带有元音数组的 for 循环，然后说所有不是元音的字母字符都是辅音，但是由于这个函数可能会被调用几千次，我想它尽可能快。

检查字符是元音还是辅音的最快方法是什么？

原文由 Mark Gardner 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

最快的方法是创建一个 bool 的数组，并使用字符值作为索引：

 bool is_vowel[CHAR_MAX] = { false }; // initializes all values to false
void init() {
    is_vowel['A'] = true;
    is_vowel['a'] = true;
    // etc.
}

现在，对于任何非负数 char 值 ch ， is_vowel[ch] 如果是元音则为真，否则为假。

原文由 Pete Becker 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果您有 ASCII 字符，并且您知道该字符是一个字母（其 ASCII 码大于或等于 64），那么您可以这样做：

 // pre-condition: v is alphabetic ASCII, upper or lower case
bool isvowel(char v) {
    return (0x208222>>(v&0x1f))&1;
}

如果您使用的是 x86，那么您甚至可以删除 &0x1f 部分（注意：根据标准，这是 未定义的行为，但作为 >> 编译为 SHR/SAR ，其中 v 将被自动屏蔽为 0x1f）：

 bool isvowel_UB_for_dumb_compilers(char v) {
    return (0x208222>>v)&1;
}

注意：这是一个“肮脏”的解决方案，但如果真的需要速度，有时肮脏的解决方案是最快的（基本上这个解决方案在魔法常数 0x208222 中存储了一个 32 元素表：为 wovels 设置了位。此外，它是利用小写和大写字符具有相同的 5 个最低位）。

如果你的编译器足够新，它知道 sar 是如何工作的，并且会优化 &0x1f 。例如，gcc8 和更新的版本会省略任何 and edi,31 指令。 （ Godbolt%3B%0A%7D%0A%0Abool+isvowel_naive(char+v)+%7B%0A++++return+(v%3D%3D!‘a!’+%7C%7C+v%3D%3D!‘e!’+%7C%7C+v%3D%3D!‘i!’+%7C%7C+v%3D%3D!‘o!’++%7C%7C+v%3D%3D!‘u!’+%7C%7C%0A++++++++++++v%3D%3D!‘A!’+%7C%7C+v%3D%3D!‘E!’+%7C%7C+v%3D%3D!‘I!’+%7C%7C+v%3D%3D!‘O!’++%7C%7C+v%3D%3D!‘U!’%0A++++)%3B%0A%7D’),l:‘5’,n:‘0’,o:‘C%2B%2B+source+%231’,t:‘0’)),k:50,l:‘4’,n:‘0’,o:“,s:0,t:‘0’),(g:!((h:compiler,i:(compiler:g83,filters:(b:‘0’,binary:‘1’,commentOnly:‘0’,demangle:‘0’,directives:‘0’,execute:‘1’,intel:‘0’,libraryCode:‘1’,trim:‘1’),lang:c%2B%2B,libs:!(),options:‘-O3+-Wall+-march%3Dhaswell’,source:1),l:‘5’,n:‘0’,o:‘x86-64+gcc+8.3+(Editor+%231,+Compiler+%231)+C%2B%2B’,t:‘0’)),k:50,l:‘4’,n:‘0’,o:”,s:0,t:‘0’)),l:‘2’,n:‘0’,o:“,t:‘0’)),version:4) 编译器资源管理器，包括一个简单的 if(v == 'a' || v == 'e' ...) GCC 编译成一些分支，但也有位图检查。

---

注意2：只有在表指针不在的情况下，此版本才比表版本快。如果你做了很多检查，并且表指针已经在寄存器中，并且表在缓存中，那么表版本会更快。

（编者注：在解压缩为 32 位 SIMD 元素后，位图可以自动矢量化以一次检查多个字符。表查找不能。）

原文由 geza 发布，翻译遵循 CC BY-SA 4.0 许可协议