2

我在另一个人的代码中看到了第二个,我想这种长度比较是为了提高代码效率。它用于具有特定字典的脚本语言的解析器:单词长度为 4 到 24 个字母,平均为 7-8 个小写字母,字母表包括 26 个拉丁字母加上“@”、“$”和“_”。

长度比较用于转义 == 运算符处理 STL 字符串,这显然比简单的整数比较需要更多时间。但同时给定字典中的首字母分布比单词大小的分布更宽,因此比较字符串的两个首字母通常比字符串的大小更经常不同。这使得长度比较变得不必要。

我已经进行了一些测试,这就是我发现的:在测试两个随机字符串比较数百万次时,第二种方法要快得多,所以长度比较似乎很有帮助。但是在一个工作项目中,它在调试模式下运行得更慢,而在发布模式下运行速度不够快。

所以,我的问题是:为什么长度比较可以加快比较速度,为什么可以减慢速度?

UPD:我也不喜欢第二种方式,但我想这样做是有原因的,我想知道这是什么原因。

UPD2:说真的,问题不在于如何做到最好。在这种情况下,我什至不再使用 STL 字符串。难怪长度比较是不必要的和错误的等等。奇怪的是 - 它确实倾向于在某个测试中稍微好一点。这怎么可能?

4

9 回答 9

32

如果这很重要,请假设您的图书馆已经这样做了。除非它真的很重要,否则不要以这种方式弄乱你的代码进行微优化。

于 2008-10-09T09:18:00.617 回答
12

短路何时有益

只有在以下情况下,短路优化才有帮助:

  • 与完整测试的成本相比,比较的成本较低
  • 比较通常会导致短路

在数学上,让 S 是短路条件的成本,F 是完全条件的成本,P 是发生短路的情况的百分比(完全条件不是必需的)。

原案(无短路)的平均成本为 F

短路优化的平均成本为 S + F * (1-P)

因此,如果优化要产生任何好处,则必须应用以下内容:

S + F * (1-P) < F

IE

S < F*P

字符串比较成本

你还写道:

这显然比简单的整数比较需要更多时间。

这一点都不明显。字符串比较在找到第一个差异时终止,因此根据您处理的字符串,在绝大多数情况下,它可能会在第一个或第二个字符处终止。此外,只要两个字符串中都有足够的数据,通过首先比较 DWORDS(一次 4 个字符),甚至可以针对较长的字符串优化比较。

你的情况

随机测试数据和脚本解析之间的主要区别在于真实数据远非随机。解析器很可能是确定性的,一旦匹配,它就不再进行比较。甚至脚本数据也不是随机的——某些关键字可能比其他关键字使用得更多。如果解析器的构造方式是它首先检查最常用的关键字,那么可能需要完成大量比较,因为当字符串匹配时总是需要完成完全比较。

于 2008-10-09T11:17:25.447 回答
5

一般来说,你应该把它留给 STL 而不必担心。

但是,如果这是您需要优化的区域(我对此表示严重怀疑),并且如果您了解字符串的字母分布/长度分布,则可以从字符串派生一个新类,并重载 == 运算符以执行以最有效的方式为您的应用程序进行相等性测试。(长度优先,第一个字符优先,向前,向后,等等)。

这比在你的代码中分散“优化”要好。

于 2008-10-09T09:29:43.150 回答
4

在您的随机测试中,字符串可能已经足够长以显示增益,而在您的实际情况下,您可能会处理较短的字符串,并且两个比较的常数因子不会被不执行测试的字符串比较部分的任何增益所抵消。

于 2008-10-09T09:19:06.510 回答
4

std::string operator== 的实现无法知道首先检查长度还是开始检查字符是否会更快。显然检查长度对于相同长度的字符串是一种浪费。因此,不同的 STL 实现可能会执行不同的操作。

仅将显式长度检查作为最终优化(明确注释为这样),并且仅当您的分析器确认好处时。

于 2008-10-09T09:22:07.940 回答
1

长度比较对我来说没有任何意义..使用比较运算符就足够了

于 2008-10-09T09:39:05.707 回答
0

触发你的 STL 实现。没关系

于 2008-10-09T09:15:48.063 回答
0

长度比较是为了尝试一些短路优化。

我假设长度比较比完整字符串比较快,所以如果这可以消除 99% 的不匹配,它会比每次进行完整字符串比较更快。

代码将执行长度比较,它会失败,然后它会忽略完整的字符串比较并跳过代码。

于 2008-10-09T10:51:16.217 回答
0

std::string 的长度很可能是 std::string 对象的成员。相比之下,第一个字符很可能在堆上。这意味着比较字符串长度可以提高引用的局部性。当然,通过短字符串优化,这变得更加复杂 -Lhs[0]可能在堆上而Rhs[0]在堆栈上。

于 2008-10-14T11:51:05.473 回答