为什么现代 CPU 每秒数亿次计算，但是程序仍旧很卡?

为什么现代 CPU 每秒数亿次计算，但是程序仍旧很卡?

我一直以来的一个观点：没有接受过良好数学（或者说理科）教育的人，是很难想象数量级的复杂度的概念的，而这个题目就是这样一个典型的范例。

我用一个典型的场景来描述算力提升但是算法不优化的场景

想象一下这个场景：某网站有一万名用户，你是其中之一。访问网站需要登录，而基础的算法是扫描所有的用户信息，然后看看里面有没有和你信息符合的。

1.扫描1万名用户需要1秒的时间，所以你登录需要1秒。而登录1秒是你可以接受的访问时间。

2. 网站的用户数量开始增长了，从1万上升到了10万，提升了一个数量级。登录依然需要扫描全部用户，所以需要10秒。这时你登录就需要10秒了。这已经是一个不太能接受的时间了，勉强还能忍。

3. 网站用户数量再次增长了一个数量级，到达100万人了，现在你登录网站需要100秒，也就是1分40秒。这真的不能忍了

于是，摆在网站面前有两条路：优化算力和优化算法。

4.1 网站选择了优化算力，算力提升了10倍，耗时1天，耗资10倍。于是你登录又变成了10秒。

4.2 网站选择了优化算法，耗时1周，登录的耗时从线性降低到了对数级，你的登录从100秒变成了6.64秒

网站用户再次增长了一个数量级，提升到了1000万人。

5.1 优化算力的路线上，你登录时间又变成了100秒，这次算力很难再优化了，因为快买不起了

5.2 优化算法的路线上，你的登录时间变成了9.97秒，再次逼近10秒大观

6.1 算力路线再次优化了算力，耗时1天，耗资10倍，提升了3倍，你的登录时间变了33秒，聊胜于无

6.2 算法路线再次优化了算法，耗时1月，数量下降到了准常量级，你的登录时间重新变成了1秒

网站用户上升到1亿了

7.1 算力路线已经升无可升了

7.2 算法路线的登录时间依然是1秒。

现代CPU的计算次数确实很可观，但是在疯长的数据规模面前并无卵用，真正能有效提升速度的其实是算法而非算力。

然而实际中，大多数场景算法的复杂度极限收敛在O(N*logN)的级别，部分收敛在O(N)，这限制了整体的速度。

以下是四位网友对此的看法

网友一：举个不合适的例子，10条数据用TXT文件记录就够了，100条数据用Excel记录很快，1000条用Excel就开始卡了，10K条记录用Excel就会卡的难以忍受，必须用MySQL了，1M条以上的数据用SQL也不行了，必须要开发专用的数据库，像淘宝，12306这种高并发的超大型数据库，优化是非常难的，必须开发各种专用算法，才能保证用户访问不会超时丢包，背后是大量的程序员的心血。1000条数据和1亿条数据，完全不是一个概念。

网友二：我们上课的时候讲过，现代算法的进化速度甚至一度超过了摩尔定律，也就是现在的算法配上二十年前的算力要快过现代的算力加二十年前的算法[捂脸]讲道理第一次知道的时候挺震感的。

网友三：这确实是一种情况，还有另一个原因：越来越便捷的开发工具把程序员都惯坏了，没多少人愿意考虑运行效率，更别提优化算法了。

网友四：我觉得用户增加十倍，会导致扫描时间增加10倍，还会导致同时访问的人数增加10倍，所以登录时间会增加100倍[惊喜]