これが私に起こったケースの話をします。
私は、順方向動的計画法 (Viterbi アルゴリズム) を使用する x264 用の新しいフレームタイプ決定アルゴリズムを実装したいと考えていました。しかし、それは複雑で、厄介で、醜いものになるでしょう。そして、私は本当にそれをしたくありませんでした。私はプロジェクトを Google Summer of Code にポーンオフしようとしましたが、ある種のひどい不運のために、私たちが持っていた 1 人の学生が彼のプロジェクトを単に救済しました... そのプロジェクトを選んだ学生でした.
それで、それについて不平を言い、それをかわす2か月後、私はついにアルゴリズムに取り掛かるようになりました. そして、これが私がそれをした方法です。
最初に、私は他の開発者と話をしました。どうやらそれを行う方法についてすでにいくつかのアイデアを持っていたようです。私たちはそれについて話し合い、アルゴリズムの観点からプロセスを完全に理解するまで、彼は私に説明してくれました。これは、そのようなプロジェクトの最初のステップです。その背後にあるアルゴリズムをよく理解して、全体を疑似コード化できるようにします。
それから、私は私の別の同僚と話しました。私たちはホワイトボードに近づき、彼もそれを理解するまでスケッチしました. 誰かに説明することで、自分自身を理解することができました。これが 2 番目のステップです。他の人にアルゴリズムを説明して、疑似コードを作成できるようにします。これは、プログラミング プロセスのエミュレーションです。プログラミングは、アルゴリズムをコンピューターに「説明する」形式であるためです。
次に、コスト関数に任意の偽の値を使用し、Viterbi 検索をテストするためだけに使用される単純な Java プロトタイプを作成しました。私はそれを完成させ、徹底的な検索に照らしてチェックしました - それは完全に一致しました. 私の動的計画法は正しかった。これが 3 番目のステップです。可能な限り単純な環境で、可能な限り単純な形式のアルゴリズムを記述します。
次に、x264 のネイティブ言語である C に移植しました。それは再び働いた。これが 4 番目のステップです。単純な形式のアルゴリズムを完全な環境に移植します。
そして最後に、偽のコスト関数を本物のコスト関数に置き換えました。いくつかのバグハンティングと修正の後、それは機能しました。これが最終ステップです。アルゴリズムを環境に完全に統合します。
このプロセスにかかった時間はわずか 1 週間でしたが、プロジェクトを開始したときの私から見ると、非常に困難で、始めることさえできませんでした。やり遂げただけでなく、思っていたよりもずっと早くやり遂げることができました。
そのメリットは x264 をはるかに超えていました。私は今、ビタビを完全に理解しているので、他の人に説明することができます...そして、他の人はそれから大きな恩恵を受けることができます. たとえば、ffmpeg 開発者の 1 人は、私のアルゴリズムとコードの適応を使用して、多少異なる問題を最適に解決しています: オーディオ ファイルの最適なヘッダー配置です。