CACM の10月号に面白いデータを見つけました．

D. H. Ackley, “Beyond efficiency,” CACM 56(10), pp. 38-40, 2013.

仮にあなたの計算機の信頼性が著しく劣っていたとして，比較命令を実行すると10%の割り合いで間違えるとしよう．そのとき，いろんなアルゴリズムは結果の正確さについてどの程度の耐性があるだろうか？で，数字列を正準化するいくつかの方法を比較してみたら，クイックソート < マージソート ≪ バブルソートということでバブルソートが圧勝ということです．

クイックソートとマージソートは正準化の高速アルゴリズムで，バブルソートは遅い手法としての地位を確立（？）しています．速さは，如何に比較の回数を削減するかとか，一回の比較あたりでどれだけ遠く離れだ数同士を交換するかに由来しています．

でも，正確に動作すると思っていた比較演算がある日，突如，狂ったらどうなるか？高速アルゴリズムの場合，無駄を取り除いたシステムの場合，最適化されたわずかな判断に間違いが入り込み，それが（遠く離れた数の交換という）大きな判断ミスを招いてしまいます．効率の悪いアルゴリズムの場合は，無骨に小さな処理を繰り返すために，大きな判断ミスが起きにくいということなのでしょう．

エラーへの対応は冗長化に頼るしかないのですが，アルゴリズムの効率の悪さというのは，ある意味，冗長化を内包していると見做せるのかもしれません．