在Perl中检查$string是否以$needle开头的最有效方法是什么？

Question

在perl中，给定两个字符串变量$string和$needle，最有效的方法是什么来检查$string是否以$needle开头。

• $string =~ /^\Q$needle\E/ 是我能想到的最接近完成所需功能但效率最低（远低于其他尝试的解决方案）的匹配。
• index($string, $needle) == 0 可以工作并且相对高效一些，但在其他位置不必要地搜索针（如果未在开头找到）。
• substr($string, 0, length($needle)) eq $needle 应该很简单且高效，但在我的几次测试中大多数情况下都不比前一个更高效。

在perl中是否有通用的方式可以实现此操作，而我不知道或者有没有优化上述任何一种解决方案的方法？

（在我的特定用例中，$string和$needle每次运行都会不同，因此无法预编译正则表达式）。

---

如何测量给定解决方案的性能的示例（在这里使用POSIX sh）：

string='somewhat not so longish string' needle='somew'
time perl -e '
  ($n,$string,$needle) = @ARGV;
  for ($i=0;$i<$n;$i++) {

    index($string, $needle) == 0

  }' 10000000 "$string" "$needle"

使用这些值，index() 在此系统中使用 perl 5.14.2 比 substr()+eq 表现更好，但在以下情况下：

string="aaaaabaaaaabaaaaabaaaaabaaaaabaaaaab" needle="aaaaaa"

那是反过来的。

- Stephane Chazelas

---

不同版本的Perl会产生影响，我建议添加您用于反馈或重复使用的基准代码。 - Ashley

@Ashley，好的，已更新。 - Stephane Chazelas

也许你会写 String::MoreUtils::XS？ - pilcrow

你是否对脚本进行了分析，以确认确实需要进行这种微小的优化？ - Ron Bergin

请使用Benchmark模块来进行Perl的基准测试，而不是使用/usr/bin/time，因为它可能无法提供公正的比较。 - ThisSuitIsBlackNot

如果你有兴趣的话，我可以用Raku来发布一个解决方案。[不过，我谦虚地请求你先更新你的问题标题，包括Raku、Ruby等内容。] - undefined

Answer 1

rindex $string, $substring, 0

在位置 <=0 上查找 $string 中的 $substring，只有当 $substring 是 $string 的前缀时才可能。例如：

> rindex "abc", "a", 0
0
> rindex "abc", "b", 0
-1

- Gregory Kalabin

---

非常感谢。这是我不知道但一直在寻找的功能。对于问题中的两个测试用例，我得到了类似的时间，并且比其他方法都要快。 - Stephane Chazelas

Answer 2

这到底有多重要？我进行了一些基准测试，index 方法平均每次迭代需要 0.68 微秒；正则表达式方法需要 1.14 微秒；substr 方法需要 0.16 微秒。即使是最坏情况下的场景（两个长度为2250的字符串相等），index 需要 2.4 微秒，正则表达式需要 5.7 微秒，而substr 只需要 0.5 微秒。

我的建议是编写一个库程序：

sub begins_with
{
    return substr($_[0], 0, length($_[1])) eq $_[1];
}

请注意：原文中包含代码和网址链接，请在翻译过程中保留这些元素。

更新：基于我上面描述的“最坏情况”的批评，我运行了一组新的基准测试，使用一个由20,000个随机生成字符构成的字符串进行比较，将其与本身进行比较，以及与仅在最后一个字节上不同的字符串进行比较。

对于这样长的字符串，正则表达式解决方案是最差的（20,000个字符的正则表达式太可怕了）：匹配成功需要105微秒，匹配失败需要100微秒。

index和substr的解决方案仍然非常快。 对于成功/失败，index分别为11.83μs / 11.86μs，而substr分别为4.09μs / 4.15μs。 将代码移动到单独的函数中会增加约0.222±0.05μs。

基准测试代码可在以下链接找到：http://codepaste.net/2k1y8e

我不知道@Stephane的数据特征，但我的建议仍然有效。

- Sue D. Nymme

---

为了论证，你可以假设字符串匹配是我的代码的关键点，并且所有其他可能的优化都已经完成。在这方面，使用函数只会降低性能。但主要是，我提出这个问题的希望是，在perl中有更好/规范的方法来解决这个问题。 - Stephane Chazelas

不要无用的，@ikegami。我的基准测试案例一半匹配成功，一半匹配失败。 - Sue D. Nymme

@SueD.Nymme：你发布的答案措辞意味着最坏情况测试仅匹配字符串。很明显，index 的最坏情况是一个极长的干草堆根本不包含针，所以它必须一直检查到结束。尽管如此，我同意你的结论：只需使用 substr，因为我们已经证明它在常见情况下并不慢。它应该有一个更好的最坏情况，这对于抵抗 DOS 攻击（或意外减速）非常重要。 - Peter Cordes

你可以尝试重现我的基准测试结果，而不是简单地将其驳回。 - Sue D. Nymme

“这有多重要？”足以让OP提出问题并让您编写基准测试。那个开放性的问题除了为了指责OP而没有其他作用，并且与答案的其余部分相矛盾。编写库例程的建议独立于问题，并且实际上支持问题，因为库例程应该努力高效。最有效的实现是rindex（$ _ [0]，$ _ [1]，0）== 0，这种不寻常的rindex用法可以与解释它的注释一起隐藏在库例程中。 - Jim Balter