我将讲述一个发生在我身上的案例。
我想为使用前向动态编程(维特比算法)的 x264 实现一种新的帧类型决策算法。但它会变得复杂、凌乱、丑陋等等。我真的不想这样做。我试图将这个项目抵押到 Google Summer of Code 上,但由于某种糟糕的运气,我们让一个学生简单地放弃了他的项目……就是选择那个项目的学生。
所以经过两个月的抱怨和回避之后,我终于开始研究算法了。这就是我的做法。
首先,我与另一位开发人员进行了交谈,他显然已经对如何做到这一点有了一些想法。我们讨论过,他向我解释,直到我从算法的角度完全理解了这个过程。这是任何此类项目的第一步:充分了解其背后的算法,以便您可以对整个事物进行伪代码。
然后,我和我的另一位同事交谈。我们走到一块白板上,我把它画出来,直到他也理解为止。通过向别人解释它,我获得了自己的理解。这是第二步:向其他人解释算法,以便他们可以对其进行伪编码。这是对编程过程的模拟,因为编程是向计算机“解释”算法的一种形式。
然后,我编写了一个简单的 Java 原型,它使用任意假值作为成本函数,并且仅用于测试 Viterbi 搜索。我完成了它,并通过详尽的搜索检查了它——它完全匹配。我的动态编程是正确的。这是第三步:在最简单的环境中编写最简单的算法形式。
然后我将它移植到 x264 的母语 C。它再次起作用了。这是第四步:将算法的简单形式移植到完整的环境中。
然后,最后,我用真实的成本函数替换了假成本函数。经过一些错误搜索和修复后,它起作用了。这是最后一步:将算法与环境完全集成。
这个过程只用了一周时间,但从项目开始时的我的角度来看,这完全是令人生畏的,我什至无法开始——然而把它分解成这样一个循序渐进的过程,我不仅能够完成它,而且比我预期的要快得多。
好处远远超出了 x264;我现在对维特比了解得如此透彻,以至于我现在可以向其他人解释……其他人也可以从中受益匪浅。例如,一个 ffmpeg 开发人员正在使用我的算法和代码的改编来优化解决一个稍微不同的问题:音频文件中的最佳标题放置。