algorithm - 为什么比较是任何合理实现中的主要成本？

Question

我正在阅读一本关于算法的教科书。教科书上说比较操作是任何合理实现中的主导成本。为什么是这样？是什么让它这么慢？

Answer 1

我猜您已经习惯了教科书示例，例如对整数数组进行排序等，其中比较成本较低。好吧，欢迎来到现实世界，这里的事情有点复杂。在许多情况下，比较操作不仅仅是一个“if”，它通常是一个相当复杂的回调函数。它从计算要比较的实际键作为对象的函数开始。一个简单的例子是不区分大小写地比较字符串。在这里，您首先必须规范化每个字符串的大小写。然后你必须逐个字符地比较字符串。这需要大量工作，比交换两个 char* 要多得多。或者想想比较树:在一次比较操作中，您可能必须遵循两棵树的许多分支。

即使你有一个比较本身非常简单的数据结构，它后面也总是有一个条件跳转。条件跳转很昂贵，假设硬件无法轻易预测结果，它们在现代处理器中大约需要 15..25 个时钟周期。这是很长的时间，通常 CPU 可以在一个时钟周期内完成一项操作。