著者

田村 知博 高野 保真 岩崎 英哉

雑誌

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

巻号頁・発行日

vol.1, no.2, pp.28-41, 2008-09-26

---

実行効率の良い探索プログラムを書くためには,結果に寄与しない計算を除去する枝刈りが有効であるが,一般に,簡潔なプログラム構造を保ったまま枝刈りの記述をすることは難しい.この問題点を解決するために,Improving Sequence(IS)というデータ構造を用いる手法が提案され,有効性が確認されている.ISとは,ある全的に定義された推移的な二項関係に従い,要求駆動によって単調に最終結果へ近づいていく近似値の列のことである.ISを用いたプログラムでは,枝刈りをするか否かの判断に近似値を用いることができる.従来の純関数型言語上のISの実装はライブラリによるものだったので,近似値の数に比例したヒープ領域を必要とし,効率があまり良くないという問題点があった.この問題点を解決するため,本論文では,ISの近似値が持つ単調性に着目し,また,近似値が枝刈りの判断にのみ用いられ,中間データとしての役割しか持たないことを前提として,純関数型言語において,定数領域しかヒープを消費しないISの実装を提案する.提案手法の効果を確認するため,Glasgow Haskell Compilerに実装を施し,ナップサック問題など,いくつかのプログラムで実験を行った.その結果,問題によってばらつきはあるものの,メモリ消費量において3%~75%程度の減少が見られ,安定的に改善できることが確認できた.また,メモリ消費量を削減することで,多くの場合に実行時間を改善できることも確認できた.