endo.dnaの文字数は7523060字。
これだけの文字数を、例えばC++ならナイーブにstd::stringに持たせると
多分酷い事に成る。
なんせ行われる操作の殆どが文字の切り出し(部分文字列の取得)と連結だらけですもの。
取りあえずstd::stringは主な操作にどれくらいのオーダーがかかるのか、というのを
sgi stlのドキュメントを読んで考えてみる。
Note that the C++ standard does not specify the complexity of basic_string operations.
In this implementation, basic_string has performance characteristics very similar to those of vector: access to a single character is O(1), while copy and concatenation are O(N).
ランダムアクセスはO(1)の定数時間で出来るらしいが、コピーと結合はO(N)掛かるとの事。
しかもこれ係数が分からん。
内部的にはvectorに似てるんですって。
substrとか何をしでかしてるのか分かりませんね。
で、ちょっと調べてみるとsubstrは内部的にコピーを行っているようなので、piece of adviceの最後に書かれていた
線形時間オーダーO(n)より良い計算量では無い。
だいたい内部構造がvectorとかいう時点で750万文字も持たせたくは無い。
さて、どうするか?
最終更新：2008年05月16日 17:51
