|
|
|
本文要分享的《每个程序员应该知道的97件事》里的第46件事：
了解你的限制
（Know Your Limits）
原文推荐：
笔者点评：这篇文章着实写得不错，所以先翻译原文，再进行一些补充。
（译文开始）
了解你的限制
"Man's got to know hislimitations." — Dirty Harry
你的资源是有限的。你只能有这么多时间和金钱来做你的工作，这里还包含那些用来保持你的知识、技能和工具能跟上时代所需要的时间和金钱。你工作只能做到这么努力、做得这么快、做得这么聪明、和做得这么久。你的工具只有这么强大。你用的机器只有这么好的性能。所以你必须尊重你所拥有的资源的限制。
如何尊重这些限制？了解你自己，了解你的团队成员，了解你的预算，了解你拥有的东西（know your stuffs）。特别是，作为一名软件工程师，要了解你用到的数据结构和算法的空间复杂度和时间复杂度，以及你的系统的体系结构和性能特性。你的工作是创造一个软件和系统的最优结合。
空间复杂度和时间复杂度可以以函数O(f(n))来表示，其中n表示输入的大小：当n逐渐增长到正无穷时，函数O(f(n))表示算法执行所需要的渐进的空间或时间。对于f(n)，重要复杂度的情况可分为ln(n)、n、nln(n)、ne和en。如下图所示，随着n的增大，O(ln(n))比O(n)和O(n ln(n))小得多，而后者比O(ne)和O(en)小得多。正如Sean Parent所说，对于任何可达的n，所有的复杂性的情况或接近常数、或接近线性，或接近无穷大。
复杂度分析是从一个抽象机器的角度上进行的，但是软件运行在真实的机器上。现代计算机系统是由物理机器和虚拟机器组成的层次结构，它包括语言运行时（language runtime）、操作系统、CPU、缓存存储（cache）、随机访问存储（RAM）、磁盘驱动器和网络。下表展示了一台典型的网络服务器在随机访问时间和存储容量上的限制。
注意，容量和速度有几个数量级的差异。缓冲和前瞻（cachingandlookahead）在我们的系统的每个级别上都被大量使用，以隐藏变化（to hide the variation），但它们只能在访问是可预测的时候下工作。当缓存频繁无法命中时，系统将会抖动（thrashing）。比如，随机地去检查硬盘驱动器上的每个字节可能需要32年。即使是随机地检查RAM中的每个字节也需要11分钟。随机访问是不可预测的。
那什么是可预测的？这取决于系统，但可以重新访问最近使用的记录和顺序访问记录通常就够好了（a win）。
算法和数据结构在使用缓存的效率上各不相同。例如:
线性搜索很好地利用了前瞻（lookahead）*，但是仍然需要O(n)次比较。
对有序的数组进行二分搜索只需要O(log(n))次比较。
用van Emde Boastree**搜索需要O(log(n))次比较，而且和缓存无关（cache-oblivious）。
如何选择？最后通过测量去分析比较。下表显示了通过这三种方法搜索64位整数数组所需的时间。在我的电脑上:
对于小数组，线性搜索是有竞争力的，但是对于大数组则指数级别的落后。
由于其可预测的访问模式，van Emde Boas tree轻松胜出。
"You pays yourmoney and you takes your choice." — Punch
*译者注：关于“线性搜索很好地利用了前瞻（Linear search makesgood use of lookahead）”，我没能直接联想到具体的算法。综合了搜索引擎力的中外材料，我认为前瞻（lookahead）是一种在广泛线性搜索场景下的一般优化策略，来优化特定情况下的搜索效率，然而它并不特指具体的某个算法。找到的一些论文和图或网络的搜索相关，但快速浏览下没怎么理解。如果你有更准确的认识，请评论交流。
**译者注2：我没了解过van Eme Boas tree，于是花了些时间学习了一下。令我惊讶的是，从微信搜一搜和百度搜索，我并没找到一篇文章能够通俗易懂地介绍这个算法；大部分文章只是摘抄了算法导论或某一两个人的学习记录。后来在Bing和Google上找到一些材料才让我大致理解这个算法，尤其是看了一些介绍算法的PPT之后（有大量图例更容易帮助理解）。欢迎评论交流
***译者注：图示源于原书的截图。
(译文结束)
(笔者文章开始)
我非常喜欢这篇文章的前两段，可惜后面的部分过于偏向算法复杂度了，而没有更深入地解释实际技术工作中更广泛的限制，比如文章说的“时间和金钱”、“工具”、“机器”性能、“团队成员”，等等。
算法复杂度固然重要，但是在现实工程工作中，对于大多数程序员，挑战往往是如何在受限的资源条件下设计并实现程序的算法，或者具体技术方案。
"Estimate to Avoid Surprises. --《Programatic Programmer》"
程序终究需要跑在一个真实的机器上，无论它直接跑在一个虚拟机上，或者以一个应用容器运行。那个机器的CPU处理能力（串行和并行）是有限的，内存是有限的，磁盘读写能力是有限的，网络带宽是有限的。
甚至我们不能假设机器能够永远运行着——它总有一天会关闭或重启，无论是有意为之还是受不可抗力影响。任何机器都有损坏的一天。现代互联网应用和服务的高可靠性是通过冗余的策略保证的，而不是通过极限单机性能保证的。
程序无法接受任意大小和规模的输入。即使可以，在真实的工程场景下，这种做法往往不现实，因为它不满足我们对运算完成时间的限制。虽然我们希望运算能处理越来越大量的数据，但是我们并不希望所需要的运算时间相应地线性增长。当然，通常保持线性增长到一定程度往往就收敛到性能上限了。
分治和并发，可以将繁重的运算任务或分解大量轻量的运算任务，有效地缓解了单例的运算压力，并通过规模化突破性能瓶颈。然而，有的时候我们还得考虑预算，而不能没有节制的规模化。预算的压力会让我们回头考虑提高单例的运算性能。
当然，能做多大程度的规模化往往还受限于框架、平台或基础设施。而且，如果我们再综合考虑程序所需的外部依赖服务的话，情况会加倍复杂。
即使我们想出了合乎运算资源和预算的限制的良好技术方案，能否有效实施，还得结合团队人力和技术知识储备进行考虑。我们不可能假设团队成员能够花几周甚至几周便能玩转一个新引入的技术。更别再提对工作完成时间的限制——可能deadline就在下周甚至明天。
要做出一个合理可行的技术方案，必须明确它的相关限制条件，否则一切的估计都不可信或充满风险。同时，考虑周全相关的限制亦帮助快速排除一些无效或不现实的技术选项，加速确定方案的议程。
了解你的限制，才能确保技术的实现能够落地。这是一个良好的技术思维，也是程序员面试中几乎肯定会考察的地方。“在理解题目的限制之前，别轻易动手写代码。”
对本文有任何想法，欢迎点击评论交流。 |
|
发表于 2021-1-5 22:59:27
