amebloのシステムについて考える。第二回

前回の記事に対してトラックバックをいただきました。

更新データのソート

これも踏まえて前回のものに一部加筆したいと思います。

＞もし静的だったとしても、誰かが記事を投げた瞬間その人をお気に入りに入れている人のすべての記事の該当部分を書き換える必要がありそうです。動的+キャッシュ等の技を駆使していないと難しいかも。

の部分についてですがページ自体は動的に生成（以下のお気に入りリストを取り込む処理）して、お気に入りリストの部分は予め計算したものを使えば、ページの表示にはソートの計算が必要ないですね。上の記事にもありますが、もっと言えばフレームで分ければ（そもそも別htmlファイルを使って一画面構成することにすれば）すべて静的ページでOKですね。

「予め計算」の部分については、一人が更新するたびにそれをお気に入りに入れているすべての人について「予め計算」を行えば良く、上の記事でも触れられている通り、上手くやれば一人当たりの「予め計算」の計算量はO(1)になります。というわけで、計算量としては

ページの表示:O(1)
ページの更新:O(n) nはそのblogをお気に入りに入れているblogの数

まで減らすことも可能ですね。これなら全く問題ないですね。
blogは「ページの表示」の割合のほうが圧倒的に高いのでこの方法がbestと言えるでしょう。amebloはどうなっているんでしょうね。

この調子だと第三回やれそうです。いろいろ思いついてきました。
（卒業論文を書かなければならないので前途多難ですが）