翻訳と辞書
Words near each other
・ 永続伝搬
・ 永続保菌者
・ 永続保菌者、慢性保菌者
・ 永続効果
・ 永続化
・ 永続平衡
・ 永続性
・ 永続性 (計算機科学)
・ 永続性、永久的、耐久性
・ 永続格納モジュール
永続的データ構造
・ 永続的識別子
・ 永続的貯蔵弾頭
・ 永続蛹
・ 永続革命
・ 永続革命論
・ 永美はるお
・ 永美ハルオ
・ 永翔級砲艦
・ 永興


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

永続的データ構造 : ミニ英和和英辞書
永続的データ構造[えいぞく]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

永続 : [えいぞく]
  1. (n,vs) permanence 2. continuation 
: [まと, てき]
 【名詞】 1. mark 2. target 
: [ちょうおん]
 (n) long vowel mark (usually only used in katakana)
構造 : [こうぞう]
 【名詞】 1. structure 2. construction 

永続的データ構造 ( リダイレクト:永続データ構造 ) : ウィキペディア日本語版
永続データ構造[えいぞくでーたこうぞう]
永続データ構造(えいぞくデータこうぞう、)は、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である。
== 概要 ==
全バージョンにアクセス可能で、最新版だけを変更可能なデータ構造を部分永続的(partially persistent)という。全バージョンにアクセスも更新も可能なデータ構造を完全永続的(fully persistent)という。最新版以外の2つのバージョンから新たなバージョンを作成/マージする操作があるなら、そのデータ構造を融合永続的(confluently persistent)という。永続的でないデータ構造は短命(ephemeral)であるという。
このようなデータ構造の分類は、特に論理プログラミング関数型プログラミングで典型的である。純粋関数プログラムでは全てのデータがイミュータブルであり、全てのデータ構造が自動的に完全永続的である。永続データ構造はデータをその場で更新する方法でも構築可能であり、一般に純粋関数での実装よりも記憶領域や時間を必要としない。
永続性は単純なコピーでも達成できるが、多くの操作はデータ構造のほんの一部しか変更しないので、時間と領域の効率が悪い。よりよい手法は、木構造を使ってバージョン間の類似性を表す方法である。しかし、バージョンが増えるにつれてバージョン間でどの部分が共通なのかを判断することが難しくなり、古いバージョンを捨てられるのが望ましい場合も多いため、ガベージコレクションが可能な環境が必要となる。
最も単純な永続データ構造は片方向連結リストや ''cons'' ベースのリストである(リスト上の次のオブジェクトへの参照のある単純なリスト)。このようなリストの尾部を共有し、変更部分だけを先頭のノードを新たに追加することで永続性を実現できる。尾部がコピーされることはなく、新しいリストと古いリストで共有される。尾部の内容がイミュータブルであれば、プログラムからはこの共有は見えない。
赤黒木キューのような多くの参照ベースのデータ構造は、容易に永続版にすることができる。配列の永続版として Phil Bagwell が 2002年に示した VList というデータ構造がある。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「永続データ構造」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Persistent data structure 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.