データ型と編集操作に対して一般的な漸増計算法 A Datatype- and Editing-Operation-Generic Incremental Computation

この論文にアクセスする

この論文をさがす

抄録

漸増計算とは,以前処理したデータとわずかに異なるデータに対する計算を以前の計算で得られた情報を用い高速に行う手法である.漸増計算により,たとえば,エディタでの構文色分けなどを文書の編集と並行して行うことができる.本発表では,リストの処理に対する漸増計算手法(Jeuring, 1991)を様々なデータ構造の処理へと一般化する.しかし,リストでは現れないような複雑な編集操作が自然に現れうるため,この拡張は非自明である.そこで,短絡融合を利用することで,このような複雑な編集操作をも扱うことができる手法を与える.先行研究と同様,適当な仮定のもとで,提案手法での漸増計算のコストは編集に要するコストに比例する.しかも,提案手法は単純なリストや木構造だけでなく,リスト2本で実装したキューやスプレー木なども取り扱うことができる.Incremental computing efficiently calculates the result for data that is slightly different from some previously processed. It is useful for several situations including syntax coloring in editors. In this presentation, we generalize an incremental computing method for list operations (Jeuring, 1991) to other datatypes. The generalization is nontrivial because other datatypes support far more complex editing operations than those for lists. We solve this issue by borrowing an idea from shortcut fusion. As the same as the preceding method, ours can calculate the result for the edited structure in time proportional to the cost of the edit operation. Moreover, our method can deal with not only simple lists and trees but also nontrivial structures including queues implemented by pairs of lists and splay trees.

収録刊行物

  • 情報処理学会論文誌プログラミング(PRO)

    情報処理学会論文誌プログラミング(PRO) 8(3), 34-34, 2015-09-21

各種コード

  • NII論文ID(NAID)
    170000147544
  • NII書誌ID(NCID)
    AA11464814
  • 本文言語コード
    JPN
  • 資料種別
    Article
  • ISSN
    1882-7802
  • データ提供元
    IPSJ 
ページトップへ