tugaa blog

MovableType3.0は英語圏向き？（修正版）

昨日のエントリ『MovableType3.0は英語圏向き？』
http://www.tugaa.net/blog/archives/000262.html
の内容に誤りがありました。

なお、上記エントリは(o)氏のエントリを基に書いたものですが、
こちらで検証せずに、そのままを書いてしまったものであり、
上記エントリの責任は当方にあります、訂正してお詫び申し上げます。

誤

エントリ数をNとすると、
一回のシーケンススキャン(SELECT COUNT(*))の処理時間はO(N)、
一回のmake_unique_basenameはこのシーケンススキャンを
O(N)回(※)行います。したがって、
エントリを1個追加するのに要する時間はO(N²)となります。
つまり、make_unique_basenameの処理に関してだけ言えば、
1000個目のエントリを作る際には、1個目を作る際の100万倍の時間がかかります。

正

エントリ数をNとすると、
一回のインデックススキャン(SELECT COUNT(*))の処理時間は最良でO(1)、
平均でO(log N)、一回のmake_unique_basenameはこのシーケンススキャンを
O(N)回(※)行います。したがって、
エントリを1個追加するのに要する時間はO(N log N)となります。
Acceptableかどうかはギリギリというところでしょう。
念のためこれはMySQL, PostgreSQLの場合であり、
BerkeleyDBではO(N²)になる可能性があります。

なお、(o)氏のOgawa::Memoranda　http://as-is.net/blog/
『MT3でなぜエントリの追加に時間がかかるようになるのか』
http://as-is.net/blog/archives/000910.html
において、より詳しい解説と、どうしてもO(N) にしたい場合の
コードが書かれていますので、 そちらも是非ご覧になって下さい。

Posted by tugaa | Comments (0) | Category( MovableType )
このエントリのTrackBack URL:

このエントリのPermalink: