Peek (データ型演算)

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ

コンピュータ サイエンスではpeekは特定の抽象データ型、特にスタックキューなどの順次コレクションに対する操作であり、コレクションから要素を削除せずにコレクションの先頭 (「先頭」) の値を返します。したがって、「pop」や「dequeue」などの操作と同じ値を返しますが、データは変更しません。

"peek" という名前は、スタックに対する基本的な "push" および "pop" 操作に似ていますが、この操作の名前はデータ型と言語によって異なります。Peek は一般に、データの追加と削除の基本的な操作と比較して、重要でない操作と見なされているため、これらのデータ型の基本的な定義には含まれていません。ただし、これは便利な操作であり、一般に簡単に実装できるため、多くの場合、実践に含まれています。一部の定義では、peek は基本として含まれ、pop (またはアナログ) は peek に関して定義されています。抽象的な定義を参照してください

データ型

peek が頻繁に実装されるシーケンシャル タイプには、次のものがあります。

スタックなどのシングルエンド型は、通常、最後に変更された単一のピークのみを許可します。deques などの両端の型は、両端に 1 つずつ、合計 2 つのピークを許可します。

ピークの名前はさまざまです。スタックでは「ピーク」または「トップ」が一般的ですが、キューでは「フロント」が一般的です。deque の操作にはさまざまな名前があり、多くの場合、「前」と「後」または「最初」と「最後」です。「頂上、頂上」という意味で「ピーク」という名前も時折見られますが、これは動詞「ピーク」のスペルミスとしても発生します.

抽象的な定義

直感的に、peek は pop と同じ値を返しますが、データは変更しません。コレクションが空の場合の動作はさまざまです。ほとんどの場合、これは空のコレクションの pop と同じようにアンダーフロー エラーを引き起こしますが、一部の実装では代わりに (エラーなしで) 単に返す関数を提供し、本質的に実装します。if isempty then return, else peek.

この動作は、さまざまな方法で公理化できます。たとえば、スタックの一般的な VDM ( Vienna Development Method ) 記述では、top (peek) とremoveをアトミックとして定義します。ここで、topはトップ値を返し (スタックを変更せずに)、removeはスタックを変更します (値を返さずに)。[1]この場合、 popはtopremoveで定義されます。

あるいは、popが与えられた場合、操作ピークは次のように公理化できます。

ピーク( D ) =ポップ( D )
ピーク( D )、D = D

「ポップと同じ値を返す」ことを意味し、「基になるデータを変更しない」(ピーク後のデータの値はピーク前と同じ)。

実装

通常、Peek は、pop 操作の単純な変形によって、O(1) 時間と余分なスペースを必要としない単純なルーチンで非常に簡単に実装できます。ほとんどのシーケンシャル データ型は、末尾への参照を含むデータ構造によって実装されるため、peek はこれを逆参照することによって簡単に実装されます。ただし、場合によっては、より複雑になります。

スタックなどの一部のデータ型では、より基本的な操作に関してこれを複製できますが、キューなどの他のデータ型では複製できません。peek を他の操作で複製できる場合でも、ほとんどの場合、個別に実装する方が効率的です。これにより、データの変更が回避されます。また、"pop と同じ値を返すだけで構成されるため、簡単に実装できます。 " (または類似の操作) ですが、データは変更されません。

スタック、プライオリティ キュー、deque、および DEPQ タイプの場合、peek は pop と push の観点から実装できます (同じ側で実行された場合)。スタックと両端キューの場合、これらの操作はほとんどの実装で O(1) であり、(データのサイズが減少するため) メモリ割り当てを必要としないため、これは一般的に効率的です。両端キューの両端はそれぞれスタックとして機能します。ただし、プライオリティ キューと DEPQ の場合、デキューとエンキューには O(log n ) 時間がかかることが多く (たとえば、バイナリ ヒープとして実装されている場合)、「ピーク」の O(1) パフォーマンス (ここでは一般に「find-min」または「find-min」と呼ばれます) "find-max") は、プライオリティ キューの主要な望ましい特性であるため、ほとんどの場合、peek は個別に実装されます。

キューの場合、エンキューとデキューが両端で発生するため、基本的な操作の観点からピークを実装することはできず、個別に実装されることがよくあります。

peek が自明ではない 1 つのケースは、自己平衡二分探索木によって実装された順序付きリスト タイプ (つまり、順番にアクセスできる要素)ですこの場合、他の要素へのアクセスと同様に、find-min または find-max に O(log n ) の時間がかかります。最小値または最大値をキャッシュすることで、find-min または find-max に O(1) 時間かかるようにすることができますが、これにより、データ構造と、要素の追加または削除の操作にオーバーヘッドが追加されます。

参考文献

  1. ^ ジョーンズ: 「VDM を使用した体系的なソフトウェア開発」
  • ホロウィッツ、エリス: 「パスカルのデータ構造の基礎」、コンピューター サイエンス プレス、1984 年、p. 67