WEKO3
-
RootNode
アイテム
純関数型言語の処理系における効率的な枝刈り機構の実装
https://ipsj.ixsq.nii.ac.jp/records/16435
https://ipsj.ixsq.nii.ac.jp/records/16435f4afb0c6-b7f6-4734-b425-49bda8d339f3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO0102004.pdf (583.5 kB)
|
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2008-09-26 | |||||||
| タイトル | ||||||||
| タイトル | 純関数型言語の処理系における効率的な枝刈り機構の実装 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Efficient Implementation of Pruning Mechanism in a Purely Functional Programming Language | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 通常論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 電気通信大学大学院電気通信学研究科情報工学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学大学院電気通信学研究科情報工学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学情報工学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Graduate School of Electro-Communications, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Graduate School of Electro-Communications, The University of Electro-Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, The University of Electro-Communications | ||||||||
| 著者名 |
田村, 知博
高野, 保真
岩崎, 英哉
× 田村, 知博 高野, 保真 岩崎, 英哉
|
|||||||
| 著者名(英) |
Tomohiro, Tamura
Yasunao, Takano
Hideya, Iwasaki
× Tomohiro, Tamura Yasunao, Takano Hideya, Iwasaki
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 実行効率の良い探索プログラムを書くためには，結果に寄与しない計算を除去する枝刈りが有効であるが，一般に，簡潔なプログラム構造を保ったまま枝刈りの記述をすることは難しい．この問題点を解決するために，Improving Sequence（IS）というデータ構造を用いる手法が提案され，有効性が確認されている．ISとは，ある全的に定義された推移的な二項関係に従い，要求駆動によって単調に最終結果へ近づいていく近似値の列のことである．ISを用いたプログラムでは，枝刈りをするか否かの判断に近似値を用いることができる．従来の純関数型言語上のISの実装はライブラリによるものだったので，近似値の数に比例したヒープ領域を必要とし，効率があまり良くないという問題点があった．この問題点を解決するため，本論文では，ISの近似値が持つ単調性に着目し，また，近似値が枝刈りの判断にのみ用いられ，中間データとしての役割しか持たないことを前提として，純関数型言語において，定数領域しかヒープを消費しないISの実装を提案する．提案手法の効果を確認するため，Glasgow Haskell Compilerに実装を施し，ナップサック問題など，いくつかのプログラムで実験を行った．その結果，問題によってばらつきはあるものの，メモリ消費量において3%～75%程度の減少が見られ，安定的に改善できることが確認できた．また，メモリ消費量を削減することで，多くの場合に実行時間を改善できることも確認できた． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Pruning unnecessary computations increases the efficiency of search programs. However, in general, it is hard to write a program that performs pruning while retaining program clarity. A mechanism called Improving Sequence (IS for short) helps the programmers write clear program for pruning computations. An IS is a sequence of approximations that are gradually improved based on a binary relation and approach the final value. Each approximation value can be used to decide whether further computations beyond the approximation can be pruned or not. Existing implementation of an IS on a purely functional language is library-based one, thus much heap space that is proportional to the number of approximations is consumed. To solve this problem, this paper proposes an efficient implementation of an IS that consumes only the constant space within the heap space. The proposed implementation is based on the observation that the approximations with an IS is monotonic and each approximation is used only in the judgment of pruning. We implemented the proposed idea in the Glasgow Haskell Compiler, and made some experiments by running some search programs that use ISes. The results show that the amount of memory consumption is reduced by 3-75%, depending on the program, and the execution time is also reduced in many cases. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464814 | |||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 1, 号 2, p. 28-41, 発行日 2008-09-26 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7802 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
