差分リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
「並行論理プログラミング」の記事における「差分リスト」の解説
データの並びを2つのリストの差分で表現する差分リストの考え方は論理プログラミング全般で用いられるテクニックであり、並行にリストを構築していく場合にも有効に利用できる。差分リストでは、例えば [a,b|X]と Xの2つの差分で [a,b]を表現する。差分リストを用いると、2つの差分リスト [a,b|X]、Xと [c,d|Y]、Yの連結は、X=[c,d|Y]とした差分リスト [a,b,c,d|Y]、Yとして簡単に求まる。差分リストの長所は以下の2点である。 リストの連結が定数時間でできる リストの連結に副作用を用いない 通常のリストを副作用なしで連結すると(例えばLISPでのAPPEND関数の動作)、リストのコピーが必要なため先頭のリスト長に比例した時間が掛かる。通常のリストを副作用を用いて直接書き換えると(例えばC言語などでの線形リスト処理)、定数時間で連結することが可能だが、リストを読み書きする他の並行プロセスがある場合に複雑な同期処理が必要になり、効率的な並行処理ができない。論理プログラミングで使われる差分リストではこれらの問題が生じない。並行論理プログラミングでは、多数のプロセスで部分的なリストを並行して構築し、1つのリストにまとめたい場合に差分リストが使われる。
※この「差分リスト」の解説は、「並行論理プログラミング」の解説の一部です。
「差分リスト」を含む「並行論理プログラミング」の記事については、「並行論理プログラミング」の概要を参照ください。
ウィキペディア小見出し辞書の「差分リスト」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 差分リストのページへのリンク
