Coursera Algorithm Part I を受講し終えた

Algorithms, Part I | Coursera を受講していて，先日無事に完了した．全体的に課題がかなり歯ごたえがあって，よい勉強になった．この講義は，全体的に応用を強く意識した説明がなされる．そのため，応用指向の人(わたしとか)に興味が持てる構成となっており，幅広い Software engineer の皆様にお勧めできる内容だと感じた．

講義中で一番面白いと感じたトピックは， Left-leaning Red-black tree の話である．Left-leaning Red-black tree は本講義のビデオに出てくる Robert Sedgewick 先生の発明で，より simple に Red-black tree を実装できるというもの．Red-black tree は非常に便利データ構造で，Self-balancing binary tree の中でも性能が安定している(insert, delete, search が log(n) で実行可能な)データ構造である．その性能の安定性から，ファイルシステムで利用されている他，C++ STL，Java Collection など標準ライブラリにも幅広く利用されている．その Red-black tree が simple に書けるのはとても魅了的だと思った．というのも，Red-black tree の self-balancing の部分は特に複雑で，正しく実装するのは大変だからだ ．ところが，少し調べたところLeft-Leaning Red-Black Trees Considered Harmfulという記事が見つかった．この記事では，Left-leaning Red-black tree の性能上の弱点や，利点として主張されている simplicity について疑わしいという主張がなされている．なかなか美味しい話はないものだ．

この手の「有用だが正確に作成することが難しいアルゴリズム・データ構造の単純化」や単純化による副作用の研究は，(分散合意アルゴリズムでいうところの Paxos made simple，Raft にあたると思うのだけど)非常に重要なので，もっと進むとよいと思った．アルゴリズムの実用性を上げる上で重要であるし，一昔前のquick sort の性能解析の話などを彷彿とさせるので熱い．