namazu-dev(ring)

[Satoru Takabayashi <satoru-t@xxxxxxxxxxxxxxxxxx>]

開発当初から、NMZ.{i,ii,w,wi} を作成する処理の効率の悪さが気
になっていました。が、この部分の処理をいじるのは厄介なので、
長い間、放置してきました (悪い習慣だ…)。 2.0 を機会に改善し
ようと思います。(それほど難しくない)

現在の実装

  * 文書をどんどん読み込んでいって、$ON_MEMORY_MAX (OMM) の
    値 (標準では 5 MB) を越えた時点で NMZ.{i,ii,w,wi} を作業
    ファイルに書き出す
  * もし、すでに作業ファイルが存在するときはマージする

       初回 ooooo (長さOMM)
        2回 oooooooooo
        3回 ooooooooooooooo
        4回 oooooooooooooooooooo
         :
    n/OMM回 ooooooooooooooooooooooooo...oo (長さn)

  * 効率が悪い:  O(n^2) のアルゴリズム

改善案

  * 文書をどんどん読み込んでいって、$ON_MEMORY_MAX の値 (標
    準では 5 MB) を越えた時点で NMZ.{i,ii,w,wi} を作業ファイ
    ルに書き出す
  * もし、すでに作業ファイルが存在するときは単純に連結し、連
    結地点を配列に記録しておく
    - それぞれ別個のファイルにした方が単純だが、数が多くなる
      とマージするときにファイルの open/close の管理が面倒
  * 最後にまとめてマージする (k-way merging)

       初回 ooooo (長さOMM)
	2回 ooooo
	3回 ooooo
	4回 ooooo
	 :  
    n/OMM回 ooooo
       最後 ooooooooooooooooooooooooo...oo (長さn)

  * 効率が良い: O(n * log n) のアルゴリズム

-- Satoru Takabayashi