大数据背景下，算法改进vs硬件迭代，哪种方式收益更高？MIT最新研究成果作出了这样的回答_

计算机出现之前，就有了算法。随着计算机的诞生，需要更多的算法来释放计算机强大的计算能力，算法是计算的核心，算法决定了计算机在解决问题时所采用的具体方式。

如果将计算机的存储器理解为一种空间上的有限资源，那么算法消耗的计算时间则应该理解为一种时间上的有限资源。有限资源意味着它们存在各自的上界，即不可能存在无限快的计算机，也不可能存在完全免费的存储器。

随着摩尔定律走向瓶颈，在面对大型问题时，仅依靠硬件迭代可能愈发难以满足海量的计算需求，选择在时间和空间方面有效的算法，或许是有效提升实际收益的明智之举。

那么，算法改进和硬件迭代相比，谁的收益更大？

（来源：Pixabay）

算法改进与硬件迭代，究竟哪一种方式收益更高？一直以来都是学术界和工业界关注的热点问题。来自麻省理工学院的相关人员前不久对这个问题作出了较为全面的回答。

为保证研究过程的严谨性，MIT 的研究人员全面分析了来自 57 部教科书和 1137 篇研究论文的相关数据，并撰文《How Fast Do Algorithms Improve?》，论文发表在 IEEE Proceedings 上，这是有史以来第一次对算法进展研究的综合分析。

图 | 相关论文（来源：IEEE Proceedings）

作者采用算法步骤分析的方式对算法展开研究，即在分析时间复杂度时保留常数项。对于给出明确算法步骤的参考论文，直接使用其结论。对于没有给出明确算法步骤的参考论文，使用 “伪代码” 进行重构。

研究内容主要包含以下几方面工作：首先，作者系统地回顾了各算法的提出时间、改进时间，以及算法改进的总体趋势；然后，作者针对不同的问题规模，对算法和硬件的改进率进行了对比分析；最后，作者利用算法和硬件改进率的对比分析结果，给出了问题规模及算法族跟改进率之间的相互关系。

算法回顾

依据待解决问题的类型进行划分，作者将算法划分为 113 个不同的算法族，对这些算法族的发展历程进行了回顾，对改进算法进行了跟踪分析，并重点关注那些有效提升性能的新算法。

这 113 个算法族包含了从 1940 年至今的大部分算法，每个算法族平均包含 8 种算法。判断一个算法是否为有效的改进算法，其主要依据为判断算法是否有效降低了所属算法族在最坏情况下的渐进时间复杂度。

基于这一标准，作者得到 276 种初始算法和后续改进算法，并且每一个初始算法平均有 1.44 个后续的改进算法。上述研究成果可在作者团队所创建的 “算法维基百科” 页面（Algorithm-Wiki.org）获取更为详细的信息。

如图所示，作者将算法族作为基本单元，对算法的提出和改进历程进行了归纳总结。其中，a）依据各算法族首次提出的时间，以十年为间隔，对算法族数目进行了统计；b）依据各算法族得到改进的时间，以十年为间隔，对算法族数目进行了统计；c）统计了所有算法族首次提出时间的渐进时间复杂度分布；d）表明通过算法改进，算法族的渐进时间复杂度在一年间得到降低的平均概率。

图 | 算法回顾。（a）每个十年提出的新算法族数量；（b）已有算法族在每个十年间得到改进的数量；（c）算法族首次被提出时的算法渐进时间复杂度；（d）同一时间复杂度的算法提升至另一个时间复杂度的年平均概率。注：在（c）和（d）中”>n3”表示渐进时间复杂度高于多项式时间复杂度，但低于指数级时间复杂度（来源：IEEE Proceedings）

如上图所示，算法族的改进速度在 1970’s 后有所放缓，作者认为其原因可能包括：

1）某些算法已达到理论最优，提升空间有限；

2）算法改进的边际收益正在减少，改进成本提高；

3）近似算法更受研究者关注（不排除算法改进困难迫使研究者探索近似解）

如图 c）可以看到，其中 31% 的算法为指数渐进时间复杂度。而在图 d）中正是将这些指数渐进时间复杂度的算法族改进到多项式时间复杂度更具深远的意义，这些改进使得某些大型问题得以求解。

对比分析

作者分析了算法族的性能随新算法的发现，在时间上呈现出的发展趋势。如图所示，统计了四个算法族随算法改进随时间呈现的性能变化，对于 n=100 万的问题规模，一些算法的改进效率已优于硬件提升的效率。并且算法改进和硬件迭代之间的一个明显差别是：摩尔定律使得硬件性能呈现平稳上升的趋势，而算法改进呈现明显的不确定性。

图 | 算法性能提升趋势。（a）四个算法族随算法改进随时间呈现的性能变化；（b）硬件迭代随时间产生的性能变化（来源：IEEE Proceedings）

如图，当扩展对 110 个算法族的分析时（如图（a）所示)，对于数千量级的问题而言，只有 18% 的算法改进相较于硬件迭代具有更强的性能提升。随着问题规模的不断增加，算法改进带来的性能提升就超过了硬件迭代。甚至有 14% 的算法族的改进率超过了 1000%，这部分性能的卓越提升大多受益于将指数渐进时间复杂度的算法改进至多项式渐进时间复杂度。当一个算法从指数渐进时间复杂度改进至多项式渐进时间复杂度时，它以任何硬件迭代都无法达到的方式改变了问题的可处理性。当问题增加至数十亿乃至数万亿的规模时，算法改进比硬件迭代平均每年带来的收益更高。