孜孜不倦的程序员

计算机科学

Ted Neward
Joe Hummel Hummel

下载代码示例

多年来，我就听到同事自称为“计算机科学家”。我也听到过这样的说法：“冠以‘科学’名号的任何研究领域都不是真正意义上的科学。”在我这个领域中，肯定有大批的人没接受过计算机科学方面的正规培训，并且还有大批人对大学和学院专业机构所做的工作很不屑，并且带有某种偏见。上次声称描述某一类型系统的一大堆希腊符号帮助您使业务线应用程序正常运行是什么时候？

我知道许多十分聪明的人，由于其拥有的博士学位等，计算机科学家的名号对他们而言真的是实至名归，Joe Hummel 就是其中之一。我邀请他和我一起撰写这个专栏，来探讨计算科学。我认为以某些较为简单的计算机科学部分开始，再看一下理解这些部分背后所蕴涵的理论是如何使您作为孜孜不倦的程序员的生活实际过得稍微容易些的，这样道来可能会更令人感兴趣。

对于本专栏，我们将探讨经典的“Big O”（大 O），希望找到一致的方法来描述简单的概念： 为执行某一给定的程序，计算机将需要多少资源（时间、内存、电能等）？这一判定称作算法分析，目标是将您选择的算法归入特定的数学类别中。为什么会这样呢？是为了您可以选择针对某一情况的最佳方法。有许多类别，每个连续类别都表示资源消耗量中的突变。我们将要针对执行时间，并且仅限前三个类别： O(1)、O(lgN) 和 O(N)。一如既往，N 表示算法所处理的数据项的数目。有关我们所讨论的全部内容的执行摘要，请参见图 1，它着重强调了每个类别随着 N 增长而预期的执行时间。

图 1 随着处理的项数 (N) 增长的执行时间

N 阶算法写作 O(N)，发音是“Big O of N”，也称作“线性”。假定 N 个数据项，O(N) 算法将取 N 个时间步长的阶。对数 N 阶算法写作 O(lgN)，发音是“Big O of log N”，称作“对数”。假定 N 个数据项，O(lgN) 算法将取 log2(N) 个时间步长的阶（少了很多）。最后，1 阶算法写作 O(1)，发音是“Big O of 1”，称作“常量”。对于 N 个数据项，O(1) 算法将取固定数目的时间步长（仍更少）。花一点时间再看一下图1。这个图形还可以传达出什么含义？例如，注意到在 N 加倍时，线性算法将用两倍的时间。

让我们看一下在真实世界中应用它的例子，在真实世界中，懂一点有关算法分析的知识就可能会产生巨大的影响。假定向您提供了一个日志文件，用来在可疑 IP 地址列表中搜索匹配项。这简单得很：

List<string> suspicious = BuildList(); /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);         /* step 1 */
  if (suspicious.Contains(ipaddr))     /* step 2 */
    matches++;                         /* step 3 */
}

我们如何对此方法的时间复杂度进行分类？ 假定日志文件中有 M 行和 N 个可疑 IP 地址。 生成由 N 个元素构成的一个未排序的列表（步长 0）将产生一个一次性的系统开销 O(N)。 该循环将执行 M 迭代，因此，该循环的系统开销是 O(M * 一次迭代的系统开销)。 每个迭代都执行以下三个基本步骤：

1. 对行进行分析
2. 搜索列表
3. 如果找到了某一匹配项则将匹配数增 1

进行分析

算法分析的智能方面是学习什么要计入在内，什么不计入。 例如，尽管对某一行进行分析（可能是应用正则表达式或将该行拆分成多个标记）可能产生较高的系统开销，但相对于数据而言，所用的时间量是固定的。 换言之，对某一行进行分析所需的时间保持完全不变，无论在该文件中是有 M 行还是 2M 行。 无论是有 N 个还是 2N 个可疑 IP 地址，该时间也不会变化。 因此，我们说步长 1 和步长 3 用了 c（固定）时间。 但是，搜索列表的步长 2 确实会相对于可疑 IP 地址的数目进行更改：

if (suspicious.Contains(ipaddr))

Contains 方法执行线性搜索，从第一个元素开始搜索，直到找到了某一匹配项或者到达了列表的末尾。 （我们是如何知道这一点的？ 通过以下三种方法中的一种： 我们对其进行了测试、我们查看了源代码或者 MSDN 库文档说明了此情况。）

对于随机数据，平均来说，我们将搜索列表的一半，并且要求 N/2 个步长。 大多数情况这一点是成立的，但在此特定情况下，一个更强的理由是日志文件中的大多数 IP 地址是值得信任的，因为我们的 Web 服务器不是银行或总统候选人的网站。 这意味着，大部分的搜索都会在找完整个列表后没有找到一个匹配，并且要求 N 个步长，而不是有某个给定客户端不受信任的成败均等机会。

因为在计算事物的阶时将删除常量，所以搜索在这两种情况下均为 O(N)，并且对于循环将生成复杂度 O(M * N)。 而这将生成以下项的整体算法复杂度：

= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)

这样，我们的解决方案的版本 1 要求 O(MN) 步长。

“数据，数据，还是数据！ 无木不成林！”

要问自己的第一个问题是： “我们是否需要更好的算法？”在几百万（可能是数十亿）行中，M 通常较大。 对此，您没有太多可以做的，因为您必须接触每一行以便搜索它。 如果 N（即可疑 IP 地址的数目）较小（如 N < 100），则您的工作将会完成。 使用当今的快速计算机，在 M 个时间步长和 100M 个时间步长之间只有很小的可测量差异。 但是，随着 N 变得更大（例如 N >> 100，或者显著大于 100），则值得考虑其他搜索算法。

不过，如果您的硬件预算真的很宽裕，就另当别论了。 （有时候，即便如此也不然。）

一个更高效的算法是二进制搜索，它先跳到中间，然后根据您在查找的元素是小于中间元素还是大于中间元素，搜索左侧或右侧。 通过每次将搜索空间减半，该算法体现了 O(lgN) 行为。 这实际意味着什么？ 假定 N=1,000 个元素，最糟的情况下，二进制搜索将取 10 个时间步长的阶 (210 ≈ 1,000)，而线性搜索将取 1,000。 对于 N = 1 百万，差别甚至更显著 — 20 个时间步长的阶对 1 百万。 进行权衡的主要方面是二进制搜索要求数据排序。 下面是为使用二进制搜索而重新编写的日志文件搜索程序：

List<string> suspicious = BuildList();      /* step 0 */
suspicious.Sort();                          /* step 0.5 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);               /* step 1 */
  if (suspicious.BinarySearch(ipaddr) >= 0)  /* step 2 */
    matches++;                               /* step 3 */
}

对可疑列表（步长 0.5）进行排序意味着一次性的 O(NlgN) 的系统开销，而每次迭代的系统开销从 O(N) 减小到 O(lgN)，假定更高效的二进制搜索（步长 2）。 这将生成以下项的整体算法复杂度：

= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)

在我们的情形中，M >> N，N 在加到 M 上时更像一个小常量，因此，我们的解决方案的版本 2 要求大约 O(MlgN) 时间。 那么？ 对于 N = 1,000 个可疑 IP 地址，我们只将执行时间从 1,000M 个时间步长的阶减小到 10M，快了 100 倍。 在搜索时间中反复节约的时间量大大抵消了额外的大约 10,000 个时间步长 (O(NlgN)) 的排序时间。

执行哈希计算

如果您了解正搜索的数据的情况，则可以（并且应该）生成一个哈希表。 哈希将平均搜索时间减少到 O(1) — 不能做得比这再好了。 它通过创建单个值到表中存储的元素的映射来实现搜索时间的减少，而该值是由哈希函数生成的。 针对哈希的主要要求是存在很好的哈希函数，它可以跨某一范围内的整数映射搜索数据，并且只有很少的冲突（重复映射）。 我们的修订后的日志文件程序（版本 3）利用了 Microsoft .NET Framework 中对有效字符串哈希的内置支持：

Dictionary<string, int> suspicious = BuildHashTable();  /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);                          /* step 1 */
  if (suspicious.ContainsKey(ipaddr))                   /* step 2 */
    matches++;                                          /* step 3 */
}

生成哈希表（步长 0）将产生一个一次性的先期系统开销 O(N)。 这将生成以下项的整体算法复杂度：

= O(build + loop)
= O(N + M * 1)
= O(N + M)

假定我们的情况是 M >> N，版本 3 是我们最快的解决方案，大约是 O(M) 时间。 对于 N = 1,000 个可疑 IP 地址，我们刚按另一个因子 10 减小了执行时间，这比我们的原始版本快 1,000 倍。 此方法的亮点是，对于甚至更大的值 N（即 10,000，甚至是 100,000），对于 M 个时间步长的阶，执行时间相同。

那么，有什么注意事项呢？ 对于版本 2 和二进制搜索而言，需要注意的事项比较简单： 必须首先对 IP 地址的列表进行排序。 在具有哈希的这个版本中，有三个要考虑的问题： 创建一个有效的哈希函数、先期构建成本以及更大的内存量。 哈希函数是其中的关键。 一个有效的哈希函数可以将数据分布到表中并且具有最少的冲突，还可以消除额外的在表中搜索初始哈希的需要。 此类函数按数据提供 O(1) 的先期关键成本或 O(N)，与线性搜索相同。 但是，此类效力通常涉及 10% 左右的负载因子，这意味着数据仅占用表的 10%。 因此，哈希要求比线性和二进制搜索大 10 倍的内存量，尽管通常这仍是 O(N)，与其他方法类似。

再说一下，为什么我们要做这样做？

毕竟，这个伪数学可能会给非计算机专业的毕业生这样的印象，我们做了许多的理论操作，并且尽管我们认为找到了有效的解决方案，但在这个过程中我们删除了许多常量。 这会产生一个很有价值的问题： “我们的理论分析是否真的值得付诸实践？”这个问题提得很好，特别是在您考虑本文的最终目标的时候，即鼓励您使用算法分析（如果您尚未使用）在动手编写代码前评估有吸引力的方法。

经常我会在办公桌旁看到工程师们数小时争论不休，有时候甚至会争上几天，辩论方法 A 是否优于方法 B。 这些家伙很少会停下话题，快速执行一下算法分析。

因此，现在让我们进行分析、执行一些测试并且看看实际会发生什么。 为此，我生成了一个具有 M 项的随机日志文件，然后对由 N 个 IP 地址构成的随机生成的列表搜索这些文件。 （完整的源文件和输入文件在 bit.ly/srchlogfiles 上提供。）

重新梳理一下，假定 M >> N，我们导出了如图 2 中所示的算法复杂度。

图 2 算法复杂度（假定 M >> N）

对于我们的测试，我们将 M 设置为 1 百万，并且每个测试都将 N 加倍： 128、256、512，依此类推。 通过将 N 加倍，可强调搜索算法的性能特性。 如果我们的分析是精确的，则在每次 N 加倍时，执行时间都应该更改，如图 3 中所示。

图 3 在 N 加倍时预测的执行时间更改

换言之，版本 1 应在时间上加倍 (2t)，版本 2 应该再加上 M 时间步长 (t + M)，版本 3 应该不占用额外时间 (t)。 图 4 显示实际记录的时间（以秒为单位）。

图 4 实际执行时间（以秒为单位）

如图 4 中所示，版本 1（基于线性搜索）在 N 加倍时在时间上也加倍了。 在大多数情况下，这可能不是什么好事。

版本 2（基于二进制搜索）的运行速度比版本 1 快多了，并且增长速度慢得多。 增长速率更难于量化，因为它依赖于时间 TM 来执行 M 个操作，时间往往在 0.1 到 0.3 秒之间。 根据我们的分析，版本 2 应该随着 N 加倍按固定速率 TM 增长，但情况似乎不是这样；这可能是由于随着 N 增长而增加的缓存压力（并因此缺少缓存）导致的。

最终，图 4 确认版本 3 实际上是最快的算法，基本上就是相同的执行时间，而与 N 无关（尽管还不是很稳定）。

寻求平衡

从实用主义者的角度来说，还不清楚从版本 2 到版本 3 的性能提升是否值得做一点努力，尽管时间节约了超过 1 秒。 可能的节省并不真的带来很大变化，除非我们开始看到确实很大的 M 或 N 值（请记住，哈希可能会要求 10 倍以上的内存来存储 IP 地址）。 最后一点也因此应运而生： 知道何时停止寻求优化。 程序员找到绝对最快的算法来执行某种类型的运算可能是令人兴奋和有吸引力的，但是，除非该运算对于用户来说非同小可，否则，在最后关头把时间用在尝试优化上常常可能比把时间用在别的事情上值得的多。 显然，从版本 1 到版本 2 的提升是值得花时间的（节省大约 10,000%），但程序员必须通盘考虑，以便寻求平衡。 有时候，理论必须为实践让路，但在其他时候，理论可帮助确定在哪里应该付诸实践。

祝您工作愉快！

Ted Neward 是 Neudesic LLC. 的体系结构顾问。 他曾写过 100 多篇文章，独自撰写或与人合著过十几本书，包括《Professional F# 2.0》（Wrox，2010 年）。 他是 C# 领域最优秀的专家之一，在全球各种会议上演讲。 他定期担任顾问和导师，如果您有兴趣请他参与您的团队工作，请通过 ted@tedneward.com 或 Ted.Neward@neudesic.com 与他联系，或通过 blogs.tedneward.com 访问其博客。

Joe Hummel 是一位私人顾问，是 Pluralsight LLC 技术团队的一员、MVP-Training.net 的培训师以及加利福尼亚大学欧文分校计算机科学系的访问学者。 他在加利福尼亚大学欧文分校获得了高性能计算领域的博士学位，并且对并行处理方面很有兴趣。 他住在芝加哥地区，如果他不去航海，您应该可以从 joe@joehummel.net 与他联络。