共連れ

2009/06/12

ビューとドキュメントの分割に手を付けたのは良いのだが、それをやるためにはどうしてもドキュメント部分の内部構造に大幅に手を入れなければならないようだ。

当面の所は既存ロジックを極力残したまま分割だけを先にやってしまおうと考えていたのだが、やはりどうにも構造がクソで流用するのも難しいと判断したのだ。

そういうことで、ここ数日は文字列操作の要となるデータ構造をどうするかということについて死ぬほど考えていた。

データとして保持しなければならないのは、文字そのものと文字の色、文字の幅である。色は構文強調表示で必要となり、文字の幅はプロポーショナルフォントを取り扱う上で必要となる。でもって、下記の操作に対して最悪でもlog(n)の計算量で処理を完了するようにしなければならない。
 ・文字列の追加
 ・文字列の削除
 ・文字の検索

ここで文字の検索といっているのは、何らかの方法で指定された位置に存在する、とある一文字が格納されているメモリアドレスを求める事を言っている。でもって「何らかの方法」というのには下記のような方法が考えられる。
 ・(行折り返しを考慮しない)行番号と、行頭からの文字数
 ・(行折り返しを考慮した)行番号と、行頭からの文字数

先頭から数えた文字数を用いて、配列のようにアドレッシングを行う可能性は低そうである。どちらかといえば、「画面上のココ」という指定をされて、その文字がメモリ空間中のどこに存在するのかを求める事の方が重要であると思われる。

また、表示や編集の処理を考えた場合、アドレッシングを方法を相互変換する機能も必要になるのは明白である。すなわち、
 ・文字を示すメモリアドレスから、行折り返しを考慮しない行番号と、行頭からの文字数を求める
 ・文字を示すメモリアドレスから、行折り返しを考慮した行番号と、行頭からの文字数を求める
 ・行折り返しを考慮しない行番号と行頭からの文字数から、行折り返しを考慮した行番号と行頭からの文字数を求める
 ・行折り返しを考慮した行番号と行頭からの文字数から、行折り返しを考慮しない行番号と行頭からの文字数を求める
という処理である。

上記の処理はいずれも、一見すると難しいような気もするが、計算量を考慮しない限りそれ程難易度の高いものではない。例えば、文字列を単純に配列に格納して、必要な都度文字列の先頭から総ナメにして要求された値を算出するようにしてやれば、よほどの馬鹿でもない限り実装することは可能なはずである。

だが、問題はこれらの処理を、文字数に対してlog(n)の計算量で解かなければならない所に存在する。

現在で主筆で使用しているロジックは、与えられた文字列を改行コードで区切って部分文字列を構築し、それら部分文字列を指し示すポインタを、単純な配列に入れて管理している。

だから、それこそ何の考えもなしに単一の配列に押し込んでいるよりかは幾分マシだとは言え、本質的には計算量はnに比例する。だから、余り大きなファイルを開くと性能が著しく劣化する。更に、一行の長さがあまりに長くなると、それこそ応答が返ってこないという事態になりかねないため、一行の最大長を10KBにするという制約を設けている。よって、これらの問題をここで一気に解消したいと考えている。

では、どういうデータ構造にすればいいのか。というか、計算量がlog(n)などという、言ってみればデータ量が増えれば増えるほど一文字当たりの計算量が減少するなどという、ご都合主義的な方法が存在するのだろうか?

答えから言えば、方法は存在する。存在するからこそ、こうして俺はゴタクを並べてblogを書いている。

方法としては、B+木を用いればいいはずである。無論「一意に識別できる値を使ってレコードを識別する」という処理ではないため、アルゴリズムは多少変則的なものになるが、それでも不可能ではない。というか、以前、こういった問題について考えたことがあり、その結果をこのページに記述している。要は、これと同じ事をしてやればいいはずなのである。

とは言っても、やはりそれが難しい。

とりあえずは、具体的なデータ構造や値の検索・更新の方法について、ある程度の目処が立ったところではあるが、実装はまだ全く手が着いていない。このままでは第21版の公開は、かなり遠い未来のこととなるであろう。