我最近被一个问题难住了:如何快速判断字符串中是否包含元音?
这应该很简单吧?
但当我开始深入研究时,我意识到这背后还有更多内容。我挑战自己想出尽可能多的检测元音的方法。我还让几位朋友尝试了一下。哪种方法最快?哪种方法绝不能使用?哪种方法最巧妙?哪种方法最易读?
这篇文章涉及11种不同的检测元音的方法,包括算法分析、解析Python字节码、检查CPython实现,甚至查看编译后的正则表达式操作码。让我们开始吧。
def has_vowels(s: str) -> bool:
...
这是我需要填充的函数模板。如果输入字符串中至少包含一个元音字母,则返回True,否则返回False。你可以从这篇博文的GitHub中找到代码。
方法#1:for循环
我首先采用了最简单的做法:
def loop_in(s):
for c in s.lower():
if c in “aeiou”:
return True
return False
这段代码合理、易读,且可能不会有性能问题。
不过,我还是觉得调用 lower() 函数有点让人困扰,因为它会始终创建一个副本(向字符串追加内容有时会就地修改字符串,但lower函数不会这样做)。我们可以轻松修复它:
def loop_in(s):
for c in s:
if c in “aeiouAEIOU”:
return True
return False
方法 #2:C 风格的 for 循环
一种不太符合 Python 风格的 for 循环变体:
def loop_or(s):
for c in s.lower():
if c == ‘a’ or c == ‘e’ or c == ‘i’ or c == ‘o’ or c == ‘u’:
return True
return False
方法 #3:嵌套 for 循环
如果我们想做到面面俱到,那么可以尝试使用嵌套 for 循环:
def nested_loop(s):
vowels = “aeiouAEIOU”
for c in s:
for v in vowels:
if c == v:
return True
return False
方法 #4:集合交集
现在来点有趣的。这是我最喜欢的解决方案:
def set_intersection(s):
return set(s) & set(“aeiouAEIOU”)
它简洁、干净,而且有点巧妙。
将输入字符串放入一个集合中,将元音放入另一个集合中,然后进行集合交集运算。集合的效率很高。向第一个集合插入元素的复杂度是 O(n), 第二个集合的长度是常数,因此创建它的复杂度是 O(1), 而集合交集的复杂度与两个集合中较小的那个集合的长度成正比,即常数,因此是 O(1), 整体时间复杂度为 O(n)。
然而,它会处理整个输入字符串,而不是在遇到第一个元音时终止。对于非常长的字符串,如果元音在早期出现,它会做很多无用功。
方法 #5:生成器表达式
def any_gen(s):
return any(c in “aeiouAEIOU” for c in s)
人们喜欢一行代码解决问题。我发挥了内心的 Python 精神,想出了这样的生成器表达式。我认为性能将与第一种方法相当,再加上生成器对象的一点开销。
方法 #6:递归
既然我已经进入了函数式编程的思维模式,我们必须尝试递归:
def recursion(s):
if not s:
return False
return s[0] in “aeiouAEIOU” or recursion(s[1:])
CPython对此并不友好。它会为输入字符串中的每个字符创建一个新字符串,并且如果字符串长度达到1000(最大递归限制)时会崩溃。
方法 #7:正则表达式搜索
只要涉及字符串,总有人会建议使用正则表达式。
import re
def regex(s):
return bool(re.search(r'[aeiouAEIOU]', s))
在最佳情况下,我预计这与 C 风格的循环性能相当,但会增加一些初始化开销。
方法 #8:正则表达式替换
import re
def regex_replace(s):
return len(re.sub(r'[aeiouAEIOU]‘, ’', s)) != len(s)
该方法会替换所有元音,然后比较字符串长度以判断是否存在被移除的字符。由于不会短路执行且会创建字符串副本,因此效率较低。
方法 #9:过滤
既然已经有了显而易见的方法,我们还能做些什么?
def filter_lambda(s):
return bool(list(filter(lambda x: x in “aeiouAEIOU”, s)))
它能工作,但效率低下且不会提前终止。
方法 #10:映射
类似但可能稍好一些:
def map_lambda(s):
return any(map(lambda x: x in “aeiouAEIOU”, s))
使用lambda表达式确实能提升你的编程风格,但这是否比我们目前的方法更优?《Effective Python》一书指出,“列表推导式比内置的map和filter函数更清晰,因为它们不需要lambda表达式”。因此,它可能不如其他方法易读且效率较低。
方法 #11:素数
我的一位前学生Gregory Croisdale提出了一个天马行空的创意方法:
primes = [i for i in range(2, 1000) if factorial(i - 1) % i == (i - 1)]
def prime(s: str) -> bool:
vowels = “aeiouAEIOU”
vowel_primes_dict = {c: primes[ord(c)] for c in vowels}
try:
s_num = reduce(lambda acc, v: acc * primes[ord(v)], s, 1)
v_num = reduce(lambda acc, v: acc * vowel_primes_dict[v], vowels, 1)
return gcd(s_num, v_num) != 1
except Exception:
return False
它将输入字符串中的每个字符和每个元音映射到一个唯一的素数,将输入字符串编码为其字符素数的乘积,并返回True,如果该乘积与元音素数乘积的GCD大于1(意味着它共享一个元音素数)。🤯
方法#12:线程
如果使用线程并行化搜索呢?将字符串分割为 n 个子字符串,并对所有子字符串应用上述方法之一。我试过了。速度非常非常慢。也许如果字符串非常庞大(如大于 1GB)并且我 禁用了 GIL。
基准测试
好,11种方法涵盖了我能想到的所有方法。是时候进行基准测试了!
我对这些函数在随机字符串上进行了比较,包括带元音和不带元音的字符串,长度各不相同。它生成2000个随机字符串(其中一半不带元音),并对每个字符串运行每种方法5次。此过程重复3次,并报告总用时最短的结果。
首先,我尝试了字符串长度为10的情况,因为检查元音的上下文是在用户名中。
Function | Time (seconds) |
---|---|
loop_in | 0.001219 |
regex | 0.002039 |
any_gen | 0.002735 |
regex_replace | 0.003047 |
map_lambda | 0.003179 |
recursion | 0.004066 |
filter_lambda | 0.004234 |
set_intersection | 0.004465 |
loop_or | 0.008870 |
nested_loop | 0.010895 |
prime | 0.016482 |
好,这看起来合理。所有方法在这个长度下都很快。值得注意的几点:简单的循环是赢家,但非常相似的或循环却相当慢。正则表达式搜索很快——实际上比我预期的快得多。我钟爱的集合交集在实际应用中足够快,但在排名中表现不佳。甚至递归也比它快。不出所料,素数笑话很慢。但没那么慢。
随着字符串长度的增加,性能差异变得更加明显。以下是字符串长度为 100 时的结果:
Function | Time (seconds) |
---|---|
regex | 0.003778 |
regex_replace | 0.005480 |
loop_in | 0.008526 |
any_gen | 0.015479 |
set_intersection | 0.015495 |
map_lambda | 0.021085 |
filter_lambda | 0.026546 |
recursion | 0.040774 |
prime | 0.077477 |
loop_or | 0.082003 |
nested_loop | 0.104956 |
两种正则表达式方法都领先了!质数不再是最后一个?带有or的循环和嵌套循环是最慢的。哇。
以下是显示长度为10、100、1000和10000的完整表格。
Function | 10 length | 100 length | 1000 length | 10000 length |
---|---|---|---|---|
regex | 0.002079 | 0.003778 | 0.020088 | 0.181247 |
regex_replace | 0.003012 | 0.005480 | 0.027443 | 0.245306 |
set_intersection | 0.004241 | 0.015495 | 0.082475 | 0.601355 |
loop_in | 0.001170 | 0.008526 | 0.076880 | 0.763442 |
any_gen | 0.002662 | 0.015479 | 0.137218 | 1.356772 |
map_lambda | 0.003090 | 0.021085 | 0.192258 | 1.915244 |
filter_lambda | 0.004305 | 0.026546 | 0.244302 | 2.424177 |
loop_or | 0.007713 | 0.082003 | 0.769124 | 7.814960 |
nested_loop | 0.008718 | 0.104956 | 0.797087 | 8.455867 |
prime | 0.016113 | 0.077477 | 2.619118 | 203.579320 |
recursion | 0.004064 | 0.040774 | DNF | DNF |
同一数据的图表(受pronoiac启发):
正则表达式方法无论字符串长度如何都快得令人难以置信。C 风格的循环非常慢。我原本以为正则表达式会与这些方法类似!?质数方法开始爆炸,而其他方法都表现良好。
但我还好奇稀疏元音会如何影响结果。我重新运行了基准测试,将元音始终放置在字符串的最后 10% 处。
Function | 10 length | 100 length | 1000 length | 10000 length |
---|---|---|---|---|
regex | 0.002083 | 0.004288 | 0.025301 | 0.235313 |
regex_replace | 0.002950 | 0.005264 | 0.027415 | 0.244298 |
set_intersection | 0.004346 | 0.015110 | 0.080171 | 0.660243 |
loop_in | 0.001444 | 0.011158 | 0.100641 | 0.989452 |
any_gen | 0.003282 | 0.019758 | 0.179111 | 1.770298 |
map_lambda | 0.003757 | 0.026654 | 0.252468 | 2.528173 |
filter_lambda | 0.004106 | 0.026335 | 0.244043 | 2.424267 |
loop_or | 0.011777 | 0.123697 | 1.029399 | 10.184211 |
nested_loop | 0.010682 | 0.106838 | 1.046352 | 10.762563 |
prime | 0.016026 | 0.076423 | 2.605674 | 205.035926 |
recursion | 0.005025 | 0.053011 | DNF | DNF |
正则表达式仍然占主导地位,但我的最爱集合交集方法表现得更好。
我还比较了 re.search 方法与预编译的正则表达式 (re.compile)。对于短字符串,两者差异显著(100,000 次调用,每个字符串长度为 10 时,分别耗时 0.009 秒和 0.2 秒),但对于长字符串,差异可忽略不计(10,000 次调用,每个字符串长度为 1000 时,分别耗时 0.234 秒和 0.235 秒)。CPython实际上总是会编译正则表达式并缓存结果,即使我们没有显式调用compile方法。请参阅re/__init__.py中的逻辑。因此,差异仅在于是否将编译工作和缓存查找计入基准测试时间。
总结而言,对于非常短的字符串,loop_in 是最快的。在长度为 25 时,正则表达式与之持平。对于更长的字符串,正则表达式占据绝对优势。将 loop_in 与 set_intersection 比较,如果元音倾向于出现在字符串的前部,loop_in 胜出。如果字符串较长(>500 个字符)或元音分布稀疏,set_intersection 胜出。
您可以在 GitHub 上找到所有代码。
正则表达式为何如此快速?
我对正则表达式能快这么多感到非常惊讶。我原本以为它会有额外开销,然后与基本循环方法趋于一致。我不得不深入研究。
这里发生了什么?让我们检查这些方法的 Python 字节码。
def has_vowel(s):
for c in s:
if c in “aeiouAEIOU”:
return True
return False
import re
def has_vowel(s):
return bool(re.search(r'[aeiouAEIOU]', s))
循环方法的字节码:
LOAD_FAST s
GET_ITER
L1 FOR_ITER
STORE_FAST c
LOAD_FAST c
LOAD_CONST 'aeiouAEIOU'
CONTAINS_OP 0
POP_JUMP_IF_TRUE L2
JUMP_BACKWARD L1
L2 LOAD_FAST c
SWAP
POP_TOP
RETURN_VALUE
L3 END_FOR
POP_TOP
RETURN_CONST None
核心部分由从标签 L1 开始的 7 个操作码组成。让我们逐一分析它们。FOR_ITER 弹出迭代器并尝试获取下一个字符(如果没有,则跳转到 L3)。STORE_FAST 将当前字符存储到局部变量中。LOAD_FAST 将字符重新压入栈中。LOAD_CONST 将元音字符串压入栈中。CONTAINS_OP 从栈中弹出两个元素,执行 in 检查,并将 True 或 False 压入栈中。POP_JUMP_IF_TRUE 如果字符是元音则跳转到 L2,否则继续执行。JUMP_BACKWARD 返回 L1 以重复该过程。
这 7 个操作码对每个字符都执行。它们很简单(除了可能的 CONTAINS_OP),尽管确实有一些冗余工作(比如每次都将元音字符串压入栈中)。
与正则表达式字节码比较:
LOAD_GLOBAL re
LOAD_ATTR search
PUSH_NULL
LOAD_CONST ‘[aeiouAEIOU]’
LOAD_FAST s
CALL 2
RETURN_VALUE
它只是调用了一个 C 函数。查看 CPython 正则表达式引擎的实现(sre.c 和 sre_lib.h), 它会创建正则表达式的内部表示,使用单个 for 循环进行迭代,并采用表查找(而非嵌套循环)。相关代码位于 sre_lib.h 文件第 1825 行中的 if 代码块中:
我想要了解正则表达式的内部表示形式,因此运行了 re.compile(“[aeiouAEIOU]”, re.DEBUG),其输出结果为:
IN
LITERAL 97
LITERAL 101
LITERAL 105
LITERAL 111
LITERAL 117
LITERAL 65
LITERAL 69
LITERAL 73
LITERAL 79
LITERAL 85
0: INFO 14 0b100 1 1 (to 15)
in
5: 字符集 [0x00000000, 0x00000000, 0x00208222, 0x00208222,
0x00000000, 0x00000000, 0x00000000, 0x00000000]
14: 失败
15: 输入 11 (到 27)
17: 字符集 [0x00000000, 0x00000000, 0x00208222, 0x00208222,
0x00000000, 0x00000000, 0x00000000, 0x00000000]
26: 失败
27: 成功
字面量是单个元音字母,包括大写和小写。CHARSET 通过位图进行单次查找,以确定当前字符是否为元音。非常巧妙!(我不确定为什么它要进行第二次检查,而不是直接继续。)
我们看到的巨大性能差异是解释器开销和优化正则表达式引擎的结合。
嗯,这真是个有趣的探索。结果真的出乎我的意料。正则表达式非常快,而非Python风格的代码相比之下可能较慢。最终,这些是否会改变你进行字符串搜索的方式?不,其实不会。除非你处理的是数百万个字符串且关心毫秒级性能,否则只需选择最易于维护的方法即可。不过学习这些原理的过程确实很有趣。
现在我可以回答这个问题:检测字符串中元音的最快方法是什么?可能是C语言中的位图。
更新#1:Kranar发现,Python的find()函数(实现于fastsearch.h 实现的 Python 的 find() 函数,比正则表达式快得多。这进一步证明了 CPython 解释器是导致性能差异的主要原因。
def vowel_find(s):
for c in “aeiouAEIOU”:
if s.find(c) != -1:
return True
return False
更新 #2: a_e_k 发现了一个更优雅简单的解决方案!只需交换循环顺序,速度就比正则表达式和find解决方案快得多:
def loop_in_perm(s):
for c in “aeiouAEIOU”:
if c in s:
return True
return False
在短字符串上比 find 快两倍以上,在长字符串上比正则表达式快 16 倍。
交换循环也改善了 any 解决方案,使其与 find 相当:
def any_gen_perm(s):
return any(c in s for c in “aeiouAEIOU”)
假设英语中所有可能的单词,你应该能够确定在随机单词中哪些元音会更早出现(例如,你更可能先看到“e”而不是“i”)。
然后,你不需要使用按字母顺序检查的if语句(例如,检查字符是否为a,是否为e,是否为I……等),而是可以按概率最高的顺序进行检查(因此,一旦找到元音,就可以快速终止)。
我对这种方法如何提高速度感兴趣。
问题中没有提到“单词”或“语言”。
从技术上讲是正确的。
但元音是语言构造……我很难想到在语言上下文之外识别它们的任何用例。
如果文章标题是“在字符串中检测特定字符的最快方法”,那将是另一回事。
但当然,这有价值(假设你的最终目标不是高效的元音检测算法,而是更通用的东西)。即使是前者,它仍然是良好算法的基础。
你不需要脱离语言环境,但使用“英语语言”的统计数据却毫无用处。
元音由语言定义,但并不需要单词来表达意义。也许你想统计这些其他字符串,用于异常检测或验证码考虑。
例如
DNA序列
base64、hex、sha256
用户名
变量名
我总是想找到PNG文件中的第一个元音。
这是一个简单的问题——PNG文件中的第一个元音是大写字母“I”,位于第13个字节处,即IHDR(图像头部)的开头。
我们可以安全地假设文件没有损坏吗?
我完全不惊讶正则表达式选项更快,因为我一看到是Python,这就是我的第一反应。
我的第二反应是,根据字符串的长度,你可能通过numpy获得更好的结果。在现代CPU上扫描大量数据最快的方法,很可能是利用大多数芯片上可用的更宽向量寄存器,而从Python numpy中,这就是你访问这些寄存器的方式。
另一个鲜为人知的有趣事实是,ASCII字符表中A和a的最低有效位相同,等等。因此,利用这一点可以进一步加快速度,如果你想变得特别聪明的话。
偶尔证明这些高级语言通常通过调用低级实现来获得最佳性能是件好事,尽管在 Python 中这通常被认为是理所当然的,因为它本身速度并不快。
假设将正则表达式实现与一些用 C 语言编写并经过良好优化的其他方法进行比较,结果可能会大不相同,因为简单的循环在 C 中应该非常快,而正则表达式相当复杂。
嗯,或许吧,这取决于许多因素。大多数正则表达式实现实际上是有限状态机,有效地操作从表达式本身编译而来的操作树(这就是为什么有re.compile),这种方法在实践中非常快,尽管可能不如直接检查字符串所需的基本操作快,但也未必慢很多。
然而,由于这实际上与虚拟机(VM)的模式类似(源代码 → 操作码树 → 状态机),没有什么能阻止一个非常先进的正则表达式实现做一些像 JIT 编译那样的事情,尤其是当表达式被频繁调用时,甚至可以直接编译为机器码……而且确实有一些实现是这样做的。
事实上,有些实现甚至对 JIT 进行了 SIMD 优化。
因此,从纯技术角度而言,在大规模应用和多次迭代的情况下,正则表达式并不一定比等效的机器码更慢——只要不考虑调用约束,它们完全可以被直接实现为机器码。
这个人用正则表达式
不,我能读懂他的评论。
公平地说,正则语言(可表示为正则表达式)的一个正式定义是可被有限自动机接受的语言,因此这是自然的实现方式。
据我所知,FA 是一种非常罕见的实现方式,尽管最近它们变得越来越常见,因为它们具有一些有用的特性,尤其是线性执行(它们往往以更慢的基线和更高的内存使用量为代价)。我所知道的主要基于 FA 的实现是 re2、go 的 regexp 和 rust 的 regex。
大多数实现都是回溯引擎,据我所知,它们将正则表达式视为一种专门的编程语言,匹配正则表达式基本上是在正则表达式程序上运行一个解释器。这就是它们能够实现非正则特性(如后向引用、向前查找、向后查找)的原因。
当然,还有各种混合方法和实现策略。
我认为回溯方法在面向网络的服务中可能引发问题,因为当正则表达式可能涉及DDOS安全风险时,很难进行合理推断。
我记得云flare曾因类似问题出现过一个漏洞,导致其服务中断?
正则表达式的操作虽复杂,但其底层本质是一个极其紧凑的状态机。
它几乎是通用解决方案中能达到的最优性能。
如果你想通过手动调优的无分支向量化位操作来追求极致性能,可能至少能提升一个数量级的性能。 甚至可能远不止于此。
你可以使用 x86 的 pshufb 或 ARM 的 vtbl 指令,并行检查 16 个字节中是否包含某个(有限的)字节集:http://0x80.pl/notesen/2018-10-18-simd-byte-lookup.html
现在我好奇编译器是否足够智能,能在这种情况下发出这些指令。或者是否有任何正则表达式库直接使用这些指令
https://github.com/intel/hyperscan
除了 hyperscan 之外,Rust 的正则表达式 crate 也可以做到。我相信 .NET 的正则表达式也可以做到。
这是设计上的考虑。以前,我们使用这个和 C 语言中的数字十六进制代码(0x0030-0x0039)来加快速度。
Unicode 问好 ☠️
我在面试中仍然经常这样做。但我会先确认我们是否使用 ASCII 编码。
正则表达式应与 C/C++ 的基础实现接近或相同。它相对于基础 C/C++ 实现有一些固定开销,这可能重要也可能不重要。
对于足够大的数据集,SIMD/向量化或并行化会更快。
我不知道这一点。谢谢提示!
即使它不是解释型语言,还有另一个原因:在字符串中查找内容是正则表达式引擎的专长。它们找到方法让它变快并不奇怪。对于从事这项工作的人来说,这就是他们的专长。
还有一个原因:它是标准库的一部分。它之所以快速,与C语言中的memcpy()函数快速的原因相同。如果你能提升其速度,收益将非常可观,因为大量软件频繁使用它。投入的努力将得到回报。
“鲜为人知”? seriously?
你会惊讶于现在的孩子们知道的有多少。
在 Python 中。它有一个糟糕的编译器。在这个例子中,常量值在每次循环中都被加载。只是一个小例子。
我好奇这在 C++ 中会如何工作。
Python没有编译器。它只是一个高度动态的解释型语言,这带来了性能开销。
它确实有一个编译器,可以将代码编译成字节码。参见https://docs.python.org/3/glossary.html#term-bytecode
虽然从技术上讲是正确的,但我敢肯定,顶层评论者仍然不知道自己在说什么,哈哈
感觉有点吹毛求疵,但从技术上讲,是的,CPython解释器在运行时会生成并缓存字节码中间语言(IL)。
我的意思是,从技术上讲是的,但当我们区分解释型语言和编译型语言时,这不是重点。
当你可以把工作交给一间满是猴子的房间时,不要把工作交给一群鱼
很快。使用 OpenMP 时更快。在我的 8 核/16 线程电脑上,它比正则表达式版本快 390 倍(使用一个糟糕的基准测试,比较不同电脑等)。不使用 OpenMP 时快 55 倍。仍有优化空间。
如果你将元音存储在平衡二叉树中,每个字符的平均比较次数可以从10次([AEIOUaeiou])减少到3.5次。如果处理Unicode元音(如å、é、ü等),差异会更大,因为需要检查的元音数量现在约为80个,但平衡二叉树查找的平均比较次数约为6.3次。
哈希集的平均性能不会更好吗?或者为了避免任何可能的冲突,可以使用一个数组,其中存储了输入字符串中可能出现的ASCII字符的布尔值,元音字符对应true(数组中的索引为该字符的十进制ASCII值)。这样数组的空间复杂度为常数,且能保证常数时间查找。
值得注意的是,这里的大O表示法分析不再适用,因为你的n只有10,且永远只会是10,因此小规模优化往往更有效。哈希在n增长时保持O(1)复杂度,但在这种规模下,单次哈希操作的开销相当高。
现在我好奇是否存在某种语言,其中某个字母及其与组合字符的组合在“是否为元音”的判断中会得到不同结果。
如果不存在,我们可以合理地跳过将所有内容转换为NFD/NFC,直接比较字符而非字形。
布尔数组听起来最快,但这种情况下我们需要知道字符编码是否类似于 UTF-32,因为这将需要 4GB 内存(不考虑位压缩),并且会因频繁的内存查找而成为瓶颈。
UTF-(8|16|32)并不重要,UTF的“码点”(例如:这个字符的编号是多少)是31位,实际上如果忽略未使用的保留字符,则是21位。
UTF-(8|16|32)只是编码方式的语义差异。
UTF-8是一种利用可变编码来编码的极其巧妙的方式。
UTF-16 是一个错误(参见:USC-2),因为最初假设只需 16 个字符。后来在 USC-4 出现时,一个笨拙的可变长度编码方案被加入,所有人都认为 31 位“应该足够了”。
UTF-32 是最自然的编码方案
这段话的要点是:使用位数组仅需 256KiB(1<<21 / 8 = 1024 * 256)。这完全可以容纳在许多现代 CPU 的 L1 缓存中。
或者使用二分搜索的排序数组。
显然,每个字符的平均比较次数并非10次[1],而是略低(如果你找到了要查找的第三个元音,为何还要继续检查剩下的?)。
[1] 每个单词的平均比较次数肯定不是字符平均数乘以元音数,因为在大多数单词中你本可以提前结束。
而且代码难以阅读。不过我确定这无关紧要。
你说的不可读是什么意思?你用的是什么浏览器?
不可读就是我看不懂这该死的代码。这不是写得好的代码。
你连5行代码都看不懂?
你认为什么是写得好的代码?你能给我你的解决方案吗?
你觉得哪些行是无法阅读的?
全部。在缩略图中。
也许启用语法高亮会更容易阅读?https://github.com/AZHenley/vowels/blob/a14a735752829ba3065ac3ca39679c3e622e84b8/vowels_benchmark.py#L95
哈哈,没错,这只是缩略图……我敢打赌没人能在缩略图里看清代码
一直输出“是”就行。你有65%的胜率
AI
基于运气的编码风格
这些循环很容易被极客狙击,因为有太多排列组合。使用哪种编码?Y是元音吗?你是预期没有元音只需验证,还是有相当大的概率出现元音?字符串有多长?有太多需要探索的地方。
在简单情况下,如果AOT编译器或JIT(假设包含一个非常好的正则表达式实现)知道你正在寻找的元音,并且它是ASCII字符,那么今天的CPU可以每纳秒处理几十个字节。然而,字符串通常相当短,因此这主要涉及避免每次调用的开销,就像你看到的那样,重复使用正则表达式与每次调用时编译的区别。
为了好玩,以检查 ASCII 元音的存在这个具体例子为例,以下是一个非常特定的专用轮子中的热循环汇编代码示例,以及一个带有基准测试和可调整参数的测试场链接。
https://rust.godbolt.org/z/oPWc4h9We
https://play.rust-lang.org/?version=stable&mode=release&edition=2024&gist=b4a8ad8413dc28357fc1118cbbfe6d91
感谢您指出这一点。在没有更多上下文的情况下,这种尝试虽然可爱,但并不实用。我们能否安全地假设这里讨论的是拉丁字符集?
在这种情况下,至少我们只讨论一个布尔值。一旦涉及到“第一个元音的位置是什么?”和“如果字符串包含一个元音,它的长度是多少?”等问题,你还需要考虑:Python 方法是否正确处理了字母群?
它从来就不是为了实用而设计的。如果你试图用发音元音来做这件事,那它将成为某个特定 Python 自然语言处理库中各种方法的基准测试,而非 Python 本身的基准测试。要么就是你使用特定英语方言用国际音标(IPA)转录的字符串。
包含Y的问题在于,你也会想包含W,而到了那个时候,你干脆也包含H。现在你得向一些人解释为什么W和H有时实际上是元音,而向其他人解释为什么你假装英语拼写与英语发音之间有任何明确的关联。
我原本期待讨论Unicode中所有字母表中的元音是什么……
大多数荷兰人甚至不知道ij是一个独立的字符——它不在我们的键盘上,大多数字体将其渲染为与ij相同,但它确实存在。偶尔你会发现一些网页调皮地将其渲染为带顶点的小写希腊字母i(类似于传统非草书手写体版本),这就是如何在荷兰程序员与荷兰语言学极客的维恩图中发现那微小的重叠部分。
这些循环甚至没有被优化到最佳状态。应该可以使用 pshufb(或更大版本)进行“表查找”,但我想编译器在优化时没有想到这一点。
还有什么语言?
为什么要在Python中进行性能测试?你已经牺牲了太多性能。
……什么?
你无法实现该问题的最佳算法,因为使用用C语言实现的库会比用Python实现的最巧妙的算法更好。
这并不意味着你应该实现性能最差的算法。参见其他顶级评论中关于使用威尔逊定理的讨论。
因为“在Python中实现X的最快方式是什么”仍然是一个重要的问题。
坦率地说,我不同意这一点。你正在使用一种在性能上根本不适合的语言。如果你处于需要提升性能的场景中,你的选择应该是使用一种快速的语言,而不是学习一种慢速语言的性能技巧或不必要的库,将1000倍的性能下降改为250倍的性能下降。
是的,先生,我会用另一种语言重写整个代码库,而不是试图优化我已经拥有的代码
回到现实世界
糟糕的语言选择与其他技术债务同样严重。为了提升性能进行大规模重写确实存在。像Facebook这样的大型公司曾开展过为期数年的项目,完全重写其前后端的部分代码,以减少50%或更多的硬件需求。
是的,绝大多数公司都无法承担全面重写的成本,即便能承担,说服一群中层管理者认为这值得投入时间和精力也绝非易事。
这里没有人主张Python是性能优选,但当你不得不使用它时,掌握如何充分发挥其潜力绝对是值得的。
通常瓶颈在于数据库,而非语言本身。我见过C#/.NET应用因糟糕的查询和ORM使用不当,其成本效益反而不如Django应用
使用Async FastAPI与Gunicorn的架构能处理绝大多数网站的流量
除非涉及底层优化,否则更换语言并不会像你想象中那样带来显著提升
这就是为什么选择Python;无论在哪里遇到性能瓶颈,你都可以用C语言来实现那部分代码。
99%的情况下,答案是将代码用C语言编写并从Python中调用(根据Python粉丝群体的观点)
这就是为什么你应该始终努力使用对象的内置方法。文章结尾有一个更新,我认为很多人忽略了这一点,即使用find()方法比正则表达式快得多,因为它只是在C中运行fastsearch。
之前在这个子版块上有一篇有趣的文章,比较了C++中算法的实现与Python标准库中的等效实现,结论是要在C++中达到相同的性能,你得跳过一些疯狂的障碍。基本上,平均水平的C++开发者很难写出这样的代码,而且使用这种速度快得多的语言也几乎看不到任何好处。
Python首先是一个出色的“粘合剂”,但一旦试图重新实现轮子,它就会彻底失败。
从纽约到芝加哥,骑在乌龟背上最快的路线是什么?
所以你可以更快地到达,我打赌。
一切都是权衡。对于许多应用程序来说,Python在现代硬件上可以提供足够好的性能。如果你能写出一个好的算法,就可以避免迁移到那些性能更高但需要更长时间才能上手的语言。
同意。对话不再是算法或可重复的;它变成了一种任意的“嗯,这个随机函数存在,而且在当前时间点上基准测试表现良好”。
这有点像对解释型语言进行基准测试,并通过最小化执行的行数来优化代码……这只是不有趣。
至少你不像使用Haskell时那么绝望。
求求你,千万别用威尔逊定理做任何事。
讽刺的是,我没看到应该最快的例子:
遍历字符串中的每个字母,然后设置一个switch语句,从’a’到’U’的每个case都返回true,默认情况继续执行。
设置一个包含每个元音的 case 的 switch 语句应该比一堆 if 语句更快,因为编译器应该设置一些跳转,这样你只需要进行一次评估。所有 ‘c in “aeiouAEIUO”’ 的内容同样是多余的,因为你不需要遍历所有元音。
Python没有switch语句。你必须通过if语句模拟,就像or循环所做的那样,或者通过(default)dict
Python有一个match语句,从所有实际用途来看,它与switch语句无法区分。
不正确。其他语言通过跳转表实现,性能更优,而 Python 没有。match 语句本质上只是 if-elif 链的语法糖。
实现方式是另一回事,我只是评论语言中是否存在该语法。
此外,对于足够小的案例集,即使 C 语言也通过 if-else 实现。
LLVM 或 GCC 会在跳转表和 if-else 链之间切换,无论是 switch case 还是 if 语句。这只是编译器提示,如果有的话。
编辑:我惊讶的是,其他现代 JIT 或编译器没有这样做。
啊,看来卡在3.9版本上让我吃了亏。
好点子
在x86架构上,使用Muła/Langdale算法进行集合匹配可能是最快的。或者使用pcmpistri。
说实话,如果字符集仅限于8位字符表示,你可以使用一些相当简单的AVX2技巧。你可以将每个可能字符的完整256位查找表放入单个向量寄存器中。创建一个常量,其中每个元音对应的位设置为1,然后将另一个变量中单词对应的位全部设置为1。计算两个__m256之间的按位与运算,并将结果转换为布尔值。
这在AVX2上实现起来比较棘手,因为没有完整的字节置换指令。可能更容易通过Muła/Langdale算法按字实现。
可能吧,是的。
1) 为什么
2) 这太棒了,我不在乎为什么
现在包含带重音的元音。
测试10个字节(“aeiouAEIOU”)与字节流的匹配。该帖子忽略了Unicode,所以我也会忽略。测试规模太小,算法细节并不重要。你的测试如果能与CPU缓存完美匹配,解决方案的性能将比不匹配的方案高出几个数量级。
当然,你无法在纯 Python 中实现这些功能。因此,调用 C 库、正则表达式或简单粗暴的方法是你的最佳选择。
我本想耍嘴皮子说最快的方法是不使用 Python。看来这是正确答案 😁
使用量子计算机。
你被点赞是因为量子计算机并不这样工作。
/s
为什么这不是一个256字节的查找表?那将快得惊人,而且基本上就是正则表达式会退化成的样子……但不需要额外的步骤……
假设你指的是256字符的查找表,最佳情况下这相当于2KB的数据,且具有极高的稀疏性。你可以通过使用位而非字节,将整个查找表压缩到一个64位整数中:https://www.reddit.com/r/programming/comments/1lanhgu/comment/mxp0guq/
谁说不能用位?
而且2k并不算大,如果你追求最高速度的话
你怎么得出2k?这实际上是256字节的数据:https://godbolt.org/z/s6M8bqjoa
(此外,该链接包含查找表的使用方式,而判断一个字符是否为元音基本上只需一条指令。要比这更快,只能通过SIMD内置函数或类似方式并行检查输入。)
你完全正确。这是个“差8”的错误,因为我当时在以位而非字节为单位思考。我仍然坚持单次uint64_t掩码检查是最快的,因为它几乎不涉及间接访问,而且你仍然需要从查找表中加载特定数组元素到寄存器进行比较。
此外,如果你查看 GB 输出,你会发现它将你的测试字符串转换为一堆静态四元组。这有点不“现实世界”。最好加载 4k 的随机生成的 ASCII 字符,然后测试不同的方法。
当然可以,为什么不呢?
“` from numba import njit import numpy as np
Numba内核的256条目查找表
lookup_u8 = np.zeros(256, dtype=np.uint8) # 0 / 1 _lookup_bool = np.zeros(256, dtype=np.bool) # False / True for b in bytearray(VOWELS, “utf-8”): _lookup_u8[b] = 1 _lookup_bool[b] = True _lookup_u8.setflags(write=False) _lookup_bool.setflags(write=False)
──────────────────────────────────────────
NUMBA 内核
──────────────────────────────────────────
@njit(cache=True, nogil=True) def njit_any_loop(pbTarget, lookup_u8): “”“按字节循环 – 找到元音时提前退出。”“” view = np.frombuffer(pbTarget, dtype=np.uint8) for x in view: if lookup_u8[x]: return True return False
@njit(cache=True, nogil=True) def njit_any_vector(pbTarget): “”“向量化内核 – lookup_bool[view] 在本地代码中生成一个布尔数组,然后 np.any() 检查是否存在任何 True。”“” view = np.frombuffer(pbTarget, dtype=np.uint8) return np.any(_lookup_bool[view])
def method_njit_loop(s: str) -> bool: return njit_any_loop(bytearray(s, “utf-8”), _lookup_u8)
def method_njit_vector(s: str) -> bool: return njit_any_vector(bytearray(s, “utf-8”)) “`
您可能不需要全部 256 个,但我们先保留在这里:
函数总时间(秒)在 10000 次调用中,方法长度为 100 method_njit_vector 0.005031 method_njit_loop 0.006139 method_regex 0. 007603 method_regex_replace 0.007887 method_loop_in 0.011798 method_set_intersection 0. 020984 method_any_gen 0.025002 method_map 0.031703 method_filter 0.043286 method_loop_or 0.060800 method_recursion 0.062520 method_prime 0.105795 method_nested_loop 0.110201
随着更多次重复运行,你会发现差异可能更加微小,但确实似乎略微更快,即使使用 NJIT 和缓存查找表以及 Numpy 的其他操作,也不会快得离谱。
惊讶的是我没有看到跳转表。可能是因为 Python 不支持它。但我怀疑那才是最快的。
如果这是C#,还有更快的实现方式:
这是正确向量化的。
甚至更快:
是的,C#。那么这是对字符串中的所有字符进行向量化处理吗?如果是这样的话,这相当不错
如果你追踪第一个示例的调用链,你会发现它会自动检测你是否像我一样同时包含大写和小写字符。如果是这样,它会使用二进制技巧。
https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.T.cs,1676
如果你继续跟踪,你会看到向量化代码
https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Packed.cs,348
对于第二个示例,你可以看到SearchValues方法会根据你搜索的字符串内容创建一个优化的查找表。如果你查看该方法的实现,你会发现它还进行了向量化处理。
https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/SearchValues/SearchValues.cs,78
我记得我曾参与过一个由曾参与 C# 和 .NET 库开发的工程师领导的编译器项目……看到他如此全面地考虑性能问题总是令人印象深刻。如果 .NET 团队中聚集了像他这样的开发者,我真的不惊讶会存在如此高度优化的解决方案。我真的应该更好地熟悉它。感谢分享
另外需要注意的是,其中很多检查实际上并不在运行时发生。
例如,考虑这里的if语句:
https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.cs,2849
if (sizeof(T) == sizeof(byte)) 被JIT视为常量。
因此,一旦生成专属方法(即JIT将其转换为非泛型方法),if语句中实际上只剩下一条分支。
有一种更快的方法可以实现这一点,无需进行最坏情况下的10次整数比较。
字符 ‘A’ 的 ASCII 值为 65,‘u’ 的 ASCII 值为 117,范围为 52,这意味着 52 位可以覆盖所有涉及的字符。这很容易放入 unit64_t 中。利用这一知识,你可以构建一个位图,使用 ‘A’ 作为第 0 位(偏移 65),如下所示:
“` (gdb) p /x (0x1ULL << (‘A’-65)) | (0x1ULL << (‘E’-65)) | (0x1ULL << (‘I’-65)) | (0x1ULL << (‘O’-65)) | (0x1ULL << (‘U’-65)) | (0x1ULL << (‘a’-65)) | (0x1ULL << (‘e’-65)) | (0x1ULL << (‘i’-65)) | (0x1ULL << (‘o’-65)) | (0x1ULL << (‘u’-65)) $1 = 0x10411100104111
(gdb) p /t 0x10411100104111 $2 = 10000010000010001000100000000000100000100000100010001 “`
然后要检查一个字符是否为元音,只需这样做:
“` uint64_t vowel_mask = 0x10411100104111ULL;
int is_vowel(char c) { /* 确保字符范围有效 */ if (c < ‘A’ || c > ‘u’) return 0;
} “`这可能通过使用偏移量 64 而不是 65,并进行预处理位运算检查 0x40 到 0x7f(64-127)范围内的值,而不是检查字符值范围来稍微提高效率,但速度提升会很小。节省的大部分时间在于使用单个整数比较来一次检查多个候选字符值。
我怀疑这最终就是原文章中正则表达式方法在后台所做的事情,尽管它会因需要管理正则表达式状态机和初始模式编译而带来更大的开销,但可能不会相差太大。
你还可以将这种方法泛化为对任何在0-255位范围内的ASCII字符集进行处理,通过一个小循环遍历一个包含n个unit64_t的数组,具体取决于所需的整体范围。
注意:如果你必须使用跳转表,我会根据给定语言的频率分析结果,按预期频率对元音进行排序,例如英语中的 E、I、A、O、U。
我也有同样的想法。但你可以进一步优化,一次性减去’A’((*(uint64_t*) string) – 0x4141414141414141ULL),利用CPU的超标量能力并减少内存压力。仍有优化空间,以下是代码。
上述代码并未涉及10次整数比较。它是一个跳转表。
你漏掉了一个技巧:检查字符串中的元音,而不是检查元音中的字符。
这很快——使用你的基准测试代码,并将STRING_LENGTH设置为1000,我得到每次调用2.3毫秒,而正则表达式方法每次调用20.0毫秒:快10倍。
即使是像
的调用时间为5.4毫秒/次。
我建议使用s.lower()——一次性的转换——并在两种方法中都跳过一半的v in s搜索。
在最坏情况下,它应该快一倍。
新分配内存,所以它应该比直接使用ors慢。
我不会这么确定。
单次分配是 O(1),无论大小,且现代内存分配器耗时不到 100 个 CPU 周期,释放内存也大致相同;而复制操作是 O(N),但 memcpy 经过向量化优化,可每周期复制多个字节。
另一方面,这6个“或”操作每个都是O(N)的搜索,即使每个都优化为向量化搜索,每次仍然是O(N)。由于每次调用C函数大约需要25个时钟周期,5次调用C函数(5个元音)的成本是分配成本的一半……当然,C函数还会做一些工作,还有Python字节码需要解释这些“或”操作等……
因此,在最坏情况下(即没有元音),或者字符串开头有一个孤立的U……存在一个字符串长度,使得s.lower()的性能会优于大写字母检查。而且这个长度可能并不大。
你的 O(1) 可能需要永恒的时间。当你可以在“有分配”和“无分配”之间选择时,没有必要讨论 O。你应该进行基准测试。
为什么你忽略了他们说的其他内容(除了关于 O 的部分)?
6个ors如何导致“搜索”?我没有评论它,因为这毫无意义
Cpython可能优化了这个ors
memcpy与这无关:s.lower()需要对每个字符码点进行处理。这可以优化,但据我所知,在Python中(当字符串为ASCII时),它会对每个字符码点进行表查找。
此外,a in b已经相当优化:当a是一个单个ASCII字符,且b也为ASCII时,会使用memchr。C 编译器通常会内联此操作。因此,这是 10 次非常快速的 O(N) 搜索。
s.lower() 方法只有在某些情况下比 5 次 in 操作更快时,整体速度才会更快。而它确实更快!我的微基准测试显示,其速度大致相当于 3 或 4 次 in 操作。
然而!lower 方法最终比多次插入方法慢约 3 倍,至少在我的测试中是这样。为什么?我怀疑这是因为 lower 方法每次都会创建一个新字符串,而这个新字符串必须写入内存,而不是完全保存在缓存中。多次插入方法不会修改任何内容,因此其目标字符串可以保存在缓存中。
为了对比,我用 Tcl 9.0 做了同样的测试,基准测试
字符串匹配函数检查全局模式是否与字符串匹配。这比 Python 使用 multiple-in 方法快约两倍。为什么?因为字符串匹配函数有自己的操作码,该操作码调用一个 C 例程来执行全局匹配。由于一切都是字符串(EIAS),因此没有类型分派。与 Python 相比,分派开销非常小,尤其是考虑到 Python 中 multiple-in 需要 68 个操作码,而上述过程仅需 4 个。
不过,Tcl 在其他方面要慢得多。
教训:优化 Tcl 和 Python 等动态语言并非仅仅是计算循环次数的问题。我的一些经验法则是:
使用性能分析器。你需要加快某些操作吗?可能不需要!:D
尽量减少动态语言中的循环。尽量让C运行时完成任务,即使看起来效率不高(比如多次使用find扫描字符串)。这一点也适用于使用numpy等库。
尽量避免内存分配。这包括切片等操作。虽然有时是可以接受的。
运算符通常比函数或方法调用更快。有些函数本质上是运算符(如’len’)。
发挥优势。Python的正则表达式引擎相当不错,但在Tcl中则不然。Tcl的switch语句使用哈希表,因此检查多个情况与检查少数情况的速度差不多。
重新评估旧假设。曾经,在Python中使用.get()从字典中检索一个不确定是否存在的键更快。现在,使用in进行检查比直接访问更快。捕获 KeyError 很快,如果这是个罕见的情况。
如果你已经添加了 C 代码,考虑一下你可以定义哪些原始函数来加快其他区域的速度。比如,一个函数来测试给定集合中的任何字符是否在另一个字符串中 🙂
这听起来一点也不优化。
在 ASCII 中,这一切都可以优化:加载、范围检测、掩码、写入。
虽然速度不会和 memcpy 一样快,但会非常接近。
当然,这也可以完全用 C 语言实现。
无论如何,感谢你的检查!
我一直被教导元音是 A、E、I、O、U,有时还包括 Y。
所以:
全部修复!
还有w
请说出一个只包含 w 而不含元音的单词。我从未听说过 w
cwm
尽管英语中没有以 w 作为唯一元音的原生单词(cwm 是威尔士语借词),但 w 在“how”等单词中仍被视为元音。
是的,元音因语言而异。我习惯将元音分为三组:aei、ouy、æøå。土耳其人可能需要检测 ı 和 İ,德国人和瑞典人则需要检测 ä 和 ö,依此类推。
例如:
这听起来像是英语程序员对编程的误解。一旦涉及语言问题,就不再简单,你需要一些国际化工具——以及 Unicode。
或者日期…
…物理地址和邮寄地址的有效性和结构
…电话号码的有效性和匹配
…电子邮件地址验证
……甚至数字格式也会有点有趣
我被教导元音是声音而非字符。
所以:
啊。那我们需要让用户说出单词,以便分析音频。
这只在字符串为英文时有效。完全没用 😂
我喜欢测试这类东西,感谢分享
看看这个频道?😉 走吧,我要出门了!
第一步显然是将其重写为C/C++。第二步显然是使用SIMD内置函数。
主循环每次迭代检查 256 个字符。这大约相当于每条指令处理 6 个字符。此外,它具有良好的流水线性能。基准测试:
如您所见,我的版本比第二快的版本快了大约12倍。简单的版本非常直观;遍历字符。其中一个版本使用了带有十个元音(大小写)的switch语句,如果找到任何元音则返回true。lut是一个查找表;一个256字节的数组,元音的索引处为true,其他均为false。any是C++的std::find_any。我对查找表比switch语句快得多感到惊讶;我原本以为它们基本上是一样的。
该博客对一个10,000字符的字符串测得约180毫秒。作者将此结果描述为,我引用他的话,“难以置信的快”。这相当于163纳秒。显然我们使用的CPU不同,因此这不是精确比较,但这大约快了六个数量级。
我喜欢Python,但坦白说,每次你想到“我该如何优化这段Python代码以提升运行速度”时,首先应该做的就是用其他任何编程语言重新编写它。你选择Python是因为它能让你快速轻松地从零开始构建东西。但它在性能方面真的非常糟糕,而且可能永远都会如此。它是一种非JIT解释型语言。它就是……不快。
虽然我明白你的意思,但这已经不再是事实了。
https://github.com/python/cpython/blob/main/Python/jit.c
Python 的 JIT 支持目前处于高度实验阶段,大部分情况下无法正常工作,即使能工作,速度也并不比解释器快。
更多信息:https://peps.python.org/pep-0744/
自 10 月以来未解决的挂起 bug:https://github.com/python/cpython/issues/126127
我不是说它已经死了,但它也没有显示出任何生命迹象。
通过一些优化、更多的咖啡因和大幅减少酒精,我成功将性能从163ns提升至127ns:
步骤 1) 使用 C
我感到震惊的是,有人对正则表达式是完成此任务最快的方法感到震惊。
> 正则表达式方法无论字符串长度如何都快得令人难以置信。
我立即认定正则表达式是赢家,原因如下:
在 Python 中,你几乎可以肯定标准库中的专用功能比你编写的任何 Python 代码都更快,因为其中大部分内容很可能已经在 CPython 中进行了优化。
其次,我不得不问,为什么有人会认为正则表达式(一种专门用于搜索字符串的工具)会比其他工具更慢?当然它会是最快的!(至少在 Python 这样的语言中。)
但它并不是最快的,实际上它非常慢,而且正则表达式通常都非常慢。关键在于,Python中的字符串处理非常慢,而正则表达式在这里能超越其他所有方法,是因为它是唯一用C语言实现的方法。
基于这一洞察,使用另一种C语言实现应该比正则表达式更快,而事实上,本文出于某种原因忽略的以下简单Python方法远远优于所有其他方法:
这是因为 s.find(c) 是用 C 语言实现的。
在我的基准测试中,这种方法比使用正则表达式快 10 倍:
https://gist.github.com/kranar/24323e81ea1c34fb56aff621f6c09…
经过一番尝试,我发现如果对循环嵌套进行排列,生成器方法与这种方法相当,甚至在 1000 个字符的长度下往往稍快一些:
我认为关键在于,你希望内部循环位于快速的C实现的原始函数中,用于遍历较长的字符串,而将外部循环留在Python中,用于遍历较短的字符串。无论是我的版本还是你的版本,Python循环都只遍历并调用C搜索循环10次,因此解释器开销更小。
我怀疑将循环嵌套以类似方式重新排列也会带来显著提速,事实上刚刚尝试:
似乎得到了目前最快的结果。(在我的机器上,使用100个和1000个字符的字符串时,速度大约是排列生成器表达式和你的find实现的两倍。)
对于英文样本,这应该会更快:
这太棒了!!!现在就将其添加到帖子末尾。
你对正则表达式了解得越多,就越明白无法对它们的性能做出普遍性结论。性能取决于引擎、算法、实现方式、模式以及输入内容。
> 通常正则表达式非常慢
我真的不认为这是正确的。如果假设字符串是ASCII的,那么针对此类模式的优化良好的正则表达式应该是一个紧凑的循环,仅执行几条指令,从一个小型数组中加载下一个状态。这个小型数组也应该完全适合缓存。这基本上是无分支的。我预计在现代CPU上,每周期可以处理1个字符。
如果字符串较短(约100个字符或更少,猜测),我预计这种实现将远超find()实现的性能,因为find()几乎肯定会比正则表达式多发生至少一次分支预测错误。对于较长的字符串,这取决于数据,因为无分支的正则表达式实现会扫描整个字符串,因此如果字符串开头有元音,find()会更快。即使没有元音,find() 仍可能更快;具体时间取决于微架构。
对于非 ASCII 字符,情况稍显复杂,但可以构建一个规模不会过大的状态机。
当然,如果你做出一些假设并手动实现你认为正则表达式会如何编译你的代码,允许优化器将你的编译时实现转换为针对特定用例的精细调优算法,你可以创建一个比某种笨拙算法更高效的方案。
但如果你像人们实际使用正则表达式那样使用它,无论是使用标准库提供的正则表达式还是现成的正则表达式,正则表达式都相当慢。当然,从原则上讲,正则表达式既不快也不慢,它是对一组字符串的声明性描述。关于其性能的任何主张都取决于特定的实现。
例如,你编写了一个基准测试,假设它比简单的搜索快得多……但请注意,你没有使用标准库中的<regex>,而是手动实现了一个搜索算法,然后只是认为这就是正则表达式实现本应做的事情(忽略了通过直接在源代码中实现它,优化器可以对其进行微调)。
现在……有10%的可能性是你确实不知道C++有一个<regex>库可以使用,或者你确实知道C++有这样的库,但你选择不使用它,因为……你也知道它非常慢。
我亲自使用标准库正则表达式、Boost 正则表达式和 PCRE2 正则表达式进行了基准测试,所有这些都比简单的循环慢 5-15 倍:
https://gist.github.com/kranar/a3187cba00d57ba630b74b84f09b4…
> 当然,如果你做出一些假设并手动实现你认为正则表达式会如何编译你的代码,允许优化器将你的编译时实现转换为针对特定用例的精细调优算法,
但实际情况并非如此。优化器唯一做的事情就是展开推进状态的循环。否则,指令序列是标准的:两次加载和一些指针运算。没有经过精细调优的算法。https://godbolt.org/z/fqdb5bssc
> 但如果你像人们实际使用正则表达式那样使用它,无论是使用标准库提供的正则表达式还是现成的正则表达式,正则表达式都相当慢。
是的,大多数正则表达式实现并非为效率而设计,而是为易用性而设计(包括支持指数时间复杂度的功能,如环视)。(Boost::regex 和 PCRE2 均支持指数时间复杂度的功能;std::regex 则完全未经过优化。)这是众所周知的。https://swtch.com/~rsc/regexp/regexp1.html. 这就是为什么我说“经过良好优化的正则表达式”。实际上,大多数正则表达式并未经过良好优化!
也许这是你和我对“正则表达式”的语义区别。我将“正则表达式”理解为计算机科学理论中对它的定义,即一个有限自动机,用于判断字符串是否属于给定语言。我认为在这里这样理解是完全合理的,因为给定的问题是找到一个最快的算法,用于判断一个字符串是否属于由ASCII字符(不包含元音)生成的语言。我认为在比较中使用一个符合该定义的(未手动优化的)实现是合理的。
>优化器唯一做的事情就是展开推进状态的循环。
你认为展开循环是一种无关紧要的事情,这令人费解。你只需要比较未启用优化时的基准测试与启用优化时的基准测试,就会发现未优化的版本大约只有一半的速度!
说到Python,最近的Python版本在某些场景下由于利用了额外的循环展开,性能有了显著提升。
>这就是为什么我说“经过良好优化的正则表达式”。实际上,大多数正则表达式在实践中都未经过良好优化!
那么,你论点的核心究竟是什么?我指出使用正则表达式会导致性能低下,这几乎是任何人都能合理推断出的结论,即使用正则表达式库通常会导致性能低下。
你的评论的全部重点是,你可以拿一个正则表达式,然后手动实现一个专门的算法来处理它,而这个算法并不慢?如果这是你的观点,那你一开始就可以说清楚,这样我们俩都能省下很多时间。
>我认为这里这样说完全合理,因为给定的问题是找到最快的算法来判断一个字符串是否属于由ASCII字符(不包括元音)生成的语言。
不,这完全不合理,因为如果你采用你的定义,那就没什么可用的了。作为正则语言并不是你可以“使用”或“不使用”的东西,它是字符串集合的属性,你无法随意使用它。由所有包含至少一个元音的字符串组成的语言是一个正则语言,此事已定,使用与否无关。从你使用的意义上说,任何对字符串匹配某个任意正则语言返回真或假的算法都可以被视为正则表达式的实现,对于某个固定的正则语言而言。但当然,这是一个完全无意义的论点,因此讨论它毫无意义。
在通常意义上,正则表达式(regex)是人们使用的库,允许他们编写一个字符串来表示模式,然后该库返回一个对象,该对象可用于测试字符串是否匹配该模式,或用于搜索匹配模式的子字符串,以及提供一系列其他功能。我原帖中的观点是,这些库(包括博客文章中使用的那个)通常运行较慢。正如你指出的,它们的设计目的是为了易用性和便利性,而非性能。
认为你为某种特定正则语言设计的任意实现,就能证明正则表达式是进行字符串匹配的高性能手段,这种论点完全不合理。但至少你已明确了自己的立场,并证明其完全无意义且毫无价值,希望读过你帖子的人不会 误以为你指的是实际工程师常用的正则表达式库,如Python的、PCRE2、Boost或标准库,这些库是快速的……但我对此表示怀疑。
用实际测试数据说话:https://github.com/tylerhou/benchmarks/blob/main/vowels-benc…
使用C++实现,采用高效正则表达式编译器可能编译元音正则表达式的一种合理编码方式,正则表达式实现除了在M1 Max MBP上处理带元音的长字符串外,在所有情况下都显著优于基于循环的实现。
字符串是根据正则表达式[0-9A-Za-z]随机生成的。短字符串长度在5-20个字符之间。长字符串长度为5000个字符。
速度提升情况如下:
– 短字符串且包含元音:正则表达式快2.6倍
– 短字符串且不包含元音:正则表达式快5.9倍
– 长字符串且包含元音:循环实现快329倍。这是预期的,因为正则表达式实现是无分支的,它必须始终遍历整个字符串。
– 长字符串且不含元音:正则表达式快1.5倍。
如果在正则表达式实现中添加早期返回,带早期返回的正则表达式将严格快于循环版本。对于短字符串且不含元音的情况,早期返回比不带早期返回的版本慢,因为额外的分支有成本。完整输出在链接文件底部的注释中。
为什么你要多次遍历haystack呢?如果你对长字符串进行一次迭代,并以一种有利于自动向量化优化的方式编写固定循环,同时进行元音检查,这样可能更快且更符合C或C++的惯用做法。
感谢提醒,我本打算也对交换版本进行基准测试。我已在上方文件中更新了新的基准测试结果。
原始评论者对每个元音调用一次`find()`,这就是为什么我将正则表达式与不太符合惯例的代码进行基准测试。
交换版本(在外部循环遍历haystack,在内部循环遍历元音)比所有正则表达式版本都稍快,除了短字符串和没有元音的情况。
需要注意的是,所有循环版本都难以推广到非ASCII字符串,而正则表达式版本则相对容易。
我在编译器探索器中研究了那个循环几分钟,我觉得它对自动向量化有抵触。假设未来用合适的语言实现的正则表达式能正确向量化,那它会胜出 🙂
非常棒的发现(双关语)。我在结尾处添加了你的解决方案和指向此评论的链接。
我一直认为正则表达式比其他方法更快地搜索字符串,但总有更多东西要学习!感谢今天的教训。
> 第二,我必须问,为什么有人会认为正则表达式(一种专门用于字符串搜索的工具)会比其他工具更慢?当然它会是最快的!(至少在Python这样的语言中。)
我知道在Go中,手动进行字符串操作几乎总是比正则表达式更快。在快速测试中,这种情况大约快10倍(~120ns vs. ~1150ns,对于100个字符且最后一个是元音的情况)。
当然Python不是Go,但我不会期望Python中的简单循环会慢那么多——从“快10倍”到“慢2倍”是一个很大的差距。
或许对熟悉 Python 及其性能特性的开发者来说这是“显而易见”的,但许多人并不了解。至少我并不了解。基于我的背景,我不会自动预期这种情况。
值得注意的是,Go 的正则表达式实现以速度缓慢著称。
>其次,我不得不问,为什么有人会认为正则表达式——一种专门用于搜索字符串的工具——会比其他工具更慢?当然它会是最快的!(至少在Python这样的语言中。)
灵活地搜索字符串。
为什么你认为我们无法以非灵活的方式实现更快的搜索?
借用亚瑟·邓特的话说,“这一定是对‘最快’这个词的一种奇怪的新用法,我之前从未见过。”
在任何合理的架构(配备某种SIMD的英特尔或AMD处理器)上,检测字符串中元音的最快方法是使用3-4条指令,这些指令一次处理16/32/64(取决于SIMD长度)个字节。显然,访问这些指令需要使用一个暴露SIMD功能的Python库。
撇开SIMD不谈,一个大小为256的扁平字节数组将比位图更高效,因为在数组中查找字节总是比在位图中查找位更快,而且数组的大小微不足道。
几年前我读到一篇题为《适用于子串搜索的SIMD友好算法》的文章。其中“通用SIMD”部分的示例简洁易懂。我对其进行了修改,以在Zig*中实现LZ77滑动窗口算法。
http://0x80.pl/notesen/2016-11-28-simd-strfind.html
* 或者说,我尽了最大努力。我对这个项目感到疲惫,因为我一直在 DEFLATE 实现和定制方案之间来回切换。SIMD 部分非常困难,一旦我让它“运行起来”,我就觉得从这个项目中得到了我需要的一切,于是放弃了。
https://github.com/rendello/compressor/blob/dev/src/str_matc…
假设使用8位字符。声明一个预先填充为全部为False的256个元素数组,仅五个(或六个)元音字符例外。此数组在代码中预先定义,运行时不进行初始化。
现在,对于输入字符串中的每个字符c,只需进行数组索引检查,判断其是否为真(元音字符)。这避免了使用五个条件语句或遍历字符串’aeiou’的循环。元音字符的判断时间复杂度为常数,与字符值无关。
在Python中这将非常慢,因为你的热循环中会包含大量Python代码。
如果字符串中包含任何非 ASCII 字符,它甚至会比 TFA 更糟糕。
这甚至不包括像“fly”和“naïve”这样的字符串。;)
是的,应该叫“如何在字符串中检测 aeiou”。
嗯……对“naïve”有效。甚至可以重复使用
我对“fly”有什么理解上的疏漏吗
文章认为aeiou是所有元音,却忽略了y。
y在英语中被视为元音吗?在我母语中它不是。
有时是。
这实际上是我点击进入这篇文章的原因之一——我原本以为它会探讨在搜索过程中判断’y’是否为元音的复杂性,结果却是一篇关于Python文本搜索的平淡无奇的文章。
你可以在这里查看英语中’Y’何时被视为元音的技术规则:
https://www.merriam-webster.com/grammar/why-y-is-sometimes-a…
如果满足以下条件,Y就被视为元音:
单词中没有其他元音:gym, my。
字母位于单词或音节的末尾:candy, deny, bicycle, acrylic。
字母位于音节的中间:system, borborygmus。
我不确定这些规则;有例外情况。钇(Yttrium)。世界树(Yggdrasil)。可能还有其他例子,但这些是我能想到的。
我认为定义Y是否为元音的最佳方式是当它不是辅音时。基本上,如果你发音时Y代表“yes”这个词中的发音,它就是辅音。否则,它就是元音。(至少,我目前想不出例外情况。)
哇,你怎么编码这个?!
嘿,好问题。我可能会使用类似本帖中讨论的启发式方法,并希望它能奏效。:D
这取决于单词,甚至可能因方言而异。字符与元音之间并不存在一一对应的关系。元音本质上是语音概念,而非字母概念。
这也是为什么Unicode没有“元音”字符属性的原因。否则你可以使用正则表达式如`p{Vowel}`。
是的,这是事实。许多人似乎将单词视为书面文字而非口头语言,因此他们专注于分析单词中的字符而非其发音。
我的一位语言学教授曾说过类似“书写依赖于口语”的话。
Y和W有时被用作元音。它们从技术上讲是辅音,但在某些情况下会发元音音。
英语中的规则不是“所有真实单词都包含元音”,而是“所有单词都包含元音音”。
除了那些不包含元音的单词,因为英语是一门非常复杂的语言。
嗯……
美国英语中的元音列表是“A E I O U 和有时 Y”,这是教给小学生的。例如,在 Ypsilanti 中,Y 就是元音。
字母不是元音;元音是发音。字母Y有时代表元音发音,有时代表辅音发音。
同上,i是元音,y是辅音。
TIL:当字母y构成双元音(即两个元音音素在同一个音节中结合形成一个发音,例如“toy”中的“oy”、“day”中的“ay”和“monkey”中的“ey”)时,它也被视为元音。通常,当y位于单词或音节的开头时,它代表辅音,例如“yard”、“lawyer”或“beyond”。
在英语中,Y是元音还是辅音几乎无法预测。
对于较早的英语单词,另一位网友提到的确定Y是元音的复杂规则确实存在,但正如另一位网友所指出的,英语还包含了从其他语言借用的单词,这些语言对Y的拼写规则不同。
在起源上,Y是元音,而非辅音。它被添加到拉丁字母表中,用于书写德语中的“ü”、法语中的“u”或斯堪的纳维亚语言中的“y”所代表的前元音。
遗憾的是,在英语以及一些跟随英语的其他语言中,Y 被重新分配用于书写辅音“i”。这导致了不同语言拼写规则不匹配所引发的诸多问题。与较早用法最一致的规则本应是使用J来表示辅音“i”,如同德语及其他受其影响的语言所做的那样。然而,在许多罗曼语族语言中,辅音“i”的发音随时间演变,导致字母J产生了其他3种音素值,例如英语中的发音(即古法语)、法语/葡萄牙语中的发音以及西班牙语中的发音。
因此,无论是Y还是J,欧洲语言之间的发音差异都非常大,而使用这些字母的许多借用词在不同语言间流通,使得拼写规则变得极为复杂。
感谢您的详细解释,真是有趣的内容!
https://www.youtube.com/watch?v=1_it0G2KcrM
事物不必复杂或美观才能快速或优秀。对于UTF-8或ASCII(英语)字符串:
检查辅音几乎是最简单的操作。英语文本中约50-70%的字符是辅音。通过检查一个位,可以在整个字符串中省去这么多检查。这在某种程度上也适用于任何文本编码;这种技巧源于字母表本身的特性。巧合的是,所有英语元音(包括Y和W)在字母表中的索引都是奇数。
字符并非魔法!它们只是数字。你可以像对其他基本类型一样,对它们进行数学运算和二进制操作。与其思考如何在字符串中查找字母,有时通过提问“如何在数字数组中查找一组数字中的一个”能得到更好的答案。在我看来,许多程序员认为这些是完全独立的问题。但作为嵌入式程序员,我认为字符始终仅占8位宽。对我来说,字符串问题本质上是数值问题。
虽然我不希望阻止人们探索问题空间,但请理解,ASCII 问题空间已被研究得非常透彻。许多问题,如“这个字符串是否包含元音”,几十年来已被优化解决。你的探索应包括研究 20 世纪我们如何解决这些问题,因为这些解决方案很可能仍然极具相关性。
“字符只是数字”这种观点的问题在于,它们不仅仅是数字……随着Unicode的出现,它们变成了“数字序列”……因此,字节在作为序列的一部分时与单独存在时可能具有不同含义。
不过,既然它们是数字,我们应该使用最高效的检查方法……这些方法很可能是针对你硬件的向量化SIMD汇编指令。而我尚未看到有人提及这一点。
没错,就是这样。向量化SIMD彻底解决了这个问题,这是我自2006年以来一直在研究的领域,当时它也并非全新概念。紧随其后的是高度优化的(流水线化和分支较少)表或位向量查找。任何涉及大量控制流的操作,如祖父母帖子中所提到的,无论是否使用位操作技巧,都会因分支的本质不可预测性(受输入影响)而变得异常缓慢。
等待几个后续问题:
“每个程序员都应了解的元音知识”
“你与元音的关系”
“元音带来的影响”
“我们正在招聘!元音(YC 26)”
最后但同样重要的是:
“我不会与之合作的事物:元音”
“程序员关于元音的误解”
需要添加一个布隆过滤器
哈哈。我发现在这篇博客上花时间寻找亚马逊联盟链接真是太有趣了。
如果你解决“如何快速完成X”的问题时,首先想到的是编写一些Python代码,那你已经没有认真对待这个任务了。
我认为用算法复杂度来定义“快”是合理的。
你能详细说明或展示更好的方法吗?
大约快了77000倍
在SIMD中实现此功能的常规方法是通过vpermb(lut, str) == str,或可能稍快的vpshufb(str>>1, lut) == str。
若需忽略大小写,可使用str|0x32。
此方法有效是因为元音的最低五位,具体而言是第二至第五位,是唯一的。
查找表(LUT)除元音对应的索引外均为零,这些索引包含其自身值:lut[vowel&31]=vowel 或 lut[(vowel&31)>>1]=vowel
> 查找表(LUT)除元音对应的索引外均为零,这些索引包含其自身值
因此,在与原始字符串的比较中,元音得到 true,辅音得到 false。那么,如果所有字符都是元音,“==” 是否会返回 true?
我使用 C 运算符作为快捷方式来表示 SIMD 操作。因此,== 操作是按元素比较,并返回输入向量中元音的掩码。
我好奇ASCII码中是否存在可利用的元音位掩码模式,于是厚着脸皮问了ChatGPT,它给出了一个不错的见解:
– 设置第5位为高位可强制输入字母为小写
– 使用`& 31`掩码可获得输入字母的0-25索引
然后你可以使用 `bt` 指令(在 x86_64 架构中)对 a、e、i、o、u(转换为小写后)的位集进行位测试,并返回是否匹配,这一切只需一条指令。
它给出了这个,我觉得挺不错的:https://godbolt.org/z/KjMdz99be
我确信还有其他酷炫的方法可以使用 AVX2 或 AVX-512 同时测试多个元音,但我还没研究到那一步。我只是觉得这个位测试技巧相当不错。
聊天记录在此(最初几次尝试失败得很惨,因为AT&T语法错误和偏移量错误,但总体还不错)https://chatgpt.com/share/684c8b39-a9c4-8012-8bb6-74e1f8b6d0…
请参阅我的另一条评论。
你可以对ASCII、UTF-8(以及大多数其他)编码方案进行非常简单的二进制检查。所有元音字母(包括W和Y)的最低位都包含一个1。然后通过比较第1至第4位,你可以进行一个简单的大小写不敏感的比较。通过检查第5位来检测大小写。0表示大写,1表示小写。
这在处理外语脚本时可行吗?显然无法应用于希腊语、阿拉伯语、韩语、中文、日语及印度语言。
再次强调,这并非关于检测元音;而是精确检测字母a、e、i、o、u的大写与小写形式。
语言不是问题;ø 和 é 在本文中不被视为“元音”(y 也不被视为元音)。
当然,只有 ASCII,没有人需要更多。ø 和 é 不被视为“元音”,哈哈!
Rust、Go、C?
或者如果你不想使用静态编译的类型化语言,也可以选择 Lua?
说实话,任何主流语言(以及大多数非主流语言)在这方面都比 Python 更好。Python 确实很有用,但它并不以性能合理著称。
[已删除]
这条评论似乎有些不必要地刻薄