算法学习的理想与现实差距

算法,以及数据结构,是计算机的世界里无处不在的东西:从一次简简单单的函数调用,到计算机网络的路由与载流均衡。在足够 theorical 的视角下,算法是一个逻辑模型,而具体代码是在某个程序设计语言下翻译的结果;也有比较激进的讨论会使用汇编作为统一的基准尽可能来避免实现的噪声,不过更一般的是通过伪代码来表达算法——顺序、循环、条件便已经足够强大。

我们对算法的一般印象是渐进复杂度分析,尤其是RAM模型下的渐进复杂度分析;这个简单却强大的模型有效指导了几十年来的算法设计,并在2010s之后的多核时代依然稳健,到今天也是本科教学的核心任务之一。不过纯粹的形式模型往往是现实的一个投影,是一种选择性的反映,作为逻辑模型的算法在现实中也面临着适用范围的审慎;比如渐进复杂度分析,反映的是理想模型下算法消耗时间的增长趋势,而在一些场景下它不完全地能够与实际吻合。

最直接的是设备IO。一次磁盘IO就可以带来完全不一样的算法设计:如果我们思考的模型是简单的一个计算单元、一个读写针头、一个无限的纸带,那么B树在整体上与二叉树(虽然一般带有平衡条件)不会有非常明显的性能优势,但是在数据库系统中,它比二叉树少上若干次查询,甚至根可以直接放在主存中,也天然支持区间,有极其巨大的优势。

另外一个值得考量的是缓存问题,L1缓存命中有着无比巨大的诱惑:比如相比于分离链表法散列表(也就是竞赛中会常用的拉链法),开放定址散列表由于没有那几次指针访问,在某些场景完全可能更快,尤其是线性探测,虽然聚集问题明显,但是又会带来CPU预取的优势。

其次是一些复杂的并发环境。或许在串行的模式下表现良好的算法与数据结构,在并发场景下加锁完全有可能有锁竞争,严重拖慢性能;内存顺序的合理搭配也会形成不小的挑战。那最逆天的是整无锁数据结构的花活的;并发编程本就非常模糊,实际上都是靠一系列原语做担保,所以对于 lock-free 的渴望理想是很美好的,操作则是十分骨感的。

更多的时候算法的性能并不是唯一的指标,维护一个动态发展的系统是远比做出一个原型要难得多的;正如《计算机程序的构造和解释》在第一版前言就直言:“程序必须写得能够供人们阅读,偶尔地去供机器执行。”有些时候为了优化一个算法,而导致整体可读性大大下降乃至别人几乎不可读,那么这个时候是需要根据团队状况和需求取舍的:我们不需要为了一点点任务而支付远超过它的成本。这种情况虽然很少见(因为大多数时候实际上都是在套前人的算法和算法设计思想用),但是对每一个优化都该时刻谨慎。

现实中的算法处理实际上并不如算法题那样来得理想化,我的优化目标也不一定是性能,正如实时系统是首先考虑用户体感而不是吞吐量,而且更广泛的时候是在面对取舍与权衡。可能在算法题中一题多解是一种锻炼思维的方式,但是在现实中选择哪一个解则是十足的挑战;这就带来了更深层次的问题:如果我们在架构视野上审视,核心要义并不在于一个理想化环境中识别出模式,然后选择会的算法解决。

每个领域都有千千万万适用于自己的算法,永远没有最强、最高效的算法之说;学习算法,不在于积累多少种不同的算法来解决多少类问题,而是在于把握算法设计模式:很多时候算法竞赛中的算法不一定是因为这个算法有多适合使用,而在于有多适合拿来做竞赛;好比红黑树,我自己平常绝对用得比动态规划多,每一次std::setstd::map的操作都是红黑树实现的。当一个标准成为优化目标的时候,就值得谨慎了;尤其是工业时代以来的标准化教育,实质就是设立一个标准器件,然后按照有多么接近标准器件来评估一个人——拼这种针对某一类任务泛化的能力,我不信能拼得过大语言模型。