PHP データ構造における DS 拡張例の分析

以下のエディターは、PHP のデータ構造に関する決まり文句を提供します: DS 拡張機能。編集者はこれがとても良いと思ったので、参考として共有します。エディターに従って見てみましょう

このデータ構造拡張機能をインストールして使用できるのは PHP7 以降のみです。インストールは比較的簡単です:

1. コマンド pecl install ds

を実行します。 php.ini ds.so

3. PHP を再起動するか、reloadConfigure

Collection インターフェイス: このライブラリ内のすべてのデータ構造に共通の関数を備えた基本インターフェイスが含まれています。すべての構造が走査可能であり、カウント可能であり、json_encode() を使用して json に変換できることを保証します。

Ds\Collection implements Traversable , Countable , JsonSerializable {
/* 方法 */
abstract public void clear ( void )
abstract public Ds\Collection copy ( void )
abstract public bool isEmpty ( void )
abstract public array toArray ( void )
}

ハッシュ可能なインターフェース：オブジェクトをキーとして使用できるようにします。

Ds\Hashable {
/* 方法 */
abstract public bool equals ( object $obj )
abstract public mixed hash ( void )
}

シーケンスインターフェース：A シーケンス同等の A 1 次元の数値キー配列。いくつかの特性が例外します:

値は常に [0, 1, 2, …, size - 1] としてインデックス付けされます。

値へのアクセスのみが許可されます。 [0, size - 1] の範囲のインデックスで指定します。

使用例:

配列をリストとして使用する場合 (キーは関係ありません)。

SplDoublyLinkedList および SplFixedArray のより効率的な代替手段。

Vector クラス: Vector は、自動的に拡大および縮小する連続バッファ内の値のシーケンスです。これは最も効率的なシーケンシャル構造であり、値のインデックスはバッファ内のインデックスに直接マップされ、成長係数は特定の倍数や指数に束縛されません。これには次の利点と欠点があります:

配列構文 (角括弧) をサポートします。

同じ数の値に対して、割り当てられたメモリを自動的に解放します。

容量。 2の累乗である必要はありません。

get()、set()、push()、pop()はすべてO(1)です。

ただし、shift()、unshift()、insert()およびRemove( ) はすべて O(n) です。

Ds\Vector::allocate — Allocates enough memory for a required capacity.
Ds\Vector::apply — Updates all values by applying a callback function to each value.
Ds\Vector::capacity — Returns the current capacity.
Ds\Vector::clear — Removes all values.
Ds\Vector::construct — Creates a new instance.
Ds\Vector::contains — Determines if the vector contains given values.
Ds\Vector::copy — Returns a shallow copy of the vector.
Ds\Vector::count — Returns the number of values in the collection.
Ds\Vector::filter — Creates a new vector using a callable to determine which values to include.
Ds\Vector::find — Attempts to find a value's index.
Ds\Vector::first — Returns the first value in the vector.
Ds\Vector::get — Returns the value at a given index.
Ds\Vector::insert — Inserts values at a given index.
Ds\Vector::isEmpty — Returns whether the vector is empty
Ds\Vector::join — Joins all values together as a string.
Ds\Vector::jsonSerialize — Returns a representation that can be converted to JSON.
Ds\Vector::last — Returns the last value.
Ds\Vector::map — Returns the result of applying a callback to each value.
Ds\Vector::merge — Returns the result of adding all given values to the vector.
Ds\Vector::pop — Removes and returns the last value.
Ds\Vector::push — Adds values to the end of the vector.
Ds\Vector::reduce — Reduces the vector to a single value using a callback function.
Ds\Vector::remove — Removes and returns a value by index.
Ds\Vector::reverse — Reverses the vector in-place.
Ds\Vector::reversed — Returns a reversed copy.
Ds\Vector::rotate — Rotates the vector by a given number of rotations.
Ds\Vector::set — Updates a value at a given index.
Ds\Vector::shift — Removes and returns the first value.
Ds\Vector::slice — Returns a sub-vector of a given range.
Ds\Vector::sort — Sorts the vector in-place.
Ds\Vector::sorted — Returns a sorted copy.
Ds\Vector::sum — Returns the sum of all values in the vector.
Ds\Vector::toArray — Converts the vector to an array.
Ds\Vector::unshift — Adds values to the front of the vector.

Deque クラス:

DsQueue でも使用される「double-ended queue」の略語には、先頭と末尾の 2 つのポインターがあります。ポインタはバッファの末尾を「ラップアラウンド」できるため、スペースを空けるために他の値を移動する必要がなくなり、シフトとシフト解除が非常に高速になります。これには、DsVector には次のような利点があります。欠点: 配列構文 (角かっこ) をサポートします。

同じ数の値の配列よりも全体的なメモリの使用量が少なくなります。

サイズが十分に小さくなったら、割り当てられたメモリを自動的に解放します。

get()、set( )、push( )、pop()、shift()、および unshift() はすべて O(1) です。

ただし、Capacity は 2 のべき乗である必要があります。insert() と Remove() は O(n) です。

Map クラス:

配列とほぼ同じ、キーと値のペアの連続したコレクション。キーは任意のタイプにすることができますが、一意である必要があります。同じキーでマップに追加された場合、値は置き換えられます。これには次の利点と欠点があります:キーと値はオブジェクトを含む任意の型にできます。

配列構文 (角括弧) をサポートします。

挿入順序は保持されます。

パフォーマンスとメモリ効率は非常に似ています。配列。

サイズが十分に低くなると、割り当てられたメモリを自動的に解放します。

オブジェクトがキーとして使用されている場合は、配列に変換できません。

Pair クラス:

ペアは、DsMap によってペアリングに使用されます。値を持つキー

Ds\Pair implements JsonSerializable {
/* 方法 */
public construct ([ mixed $key [, mixed $value ]] )
}

クラスを設定:

一意の値のシーケンス。この実装は DsMap と同じハッシュ テーブルを使用します。値はキーとして使用され、マップされた値は無視されます。 値はオブジェクトを含む任意の型にすることができます。構文 (角括弧)。

挿入順序は保持されます。

サイズが十分に低下すると、割り当てられたメモリが自動的に解放されます。

add()、remove()、contains() はすべて O(1) です。

ただしPush()、pop()、insert()、shift()、または unshift() はサポートされません。アクセスされたインデックスの前にバッファー内に削除された値がある場合、get() は O(n) になります。 1) それ以外の場合:

スタック クラス: 構造の最上部でのみアクセスと反復を許可する「後入れ先出し」コレクション。

Ds\Stack implements Ds\Collection {
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\Stack copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ([ mixed $...values ] )
public array toArray ( void )
}

Queue クラス: 「先入れ先出し」コレクション。構造のフロントエンドでのアクセスと反復のみを許可します。

Ds\Queue implements Ds\Collection {
/* Constants */
const int MIN_CAPACITY = 8 ;
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\Queue copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ([ mixed $...values ] )
public array toArray ( void )
}

PriorityQueue クラス: Priority

キューはキューと非常によく似ていますが、値は指定された優先順位でキューにプッシュされ、最も高い優先度を持つ値が常にキューの先頭になります。同じ優先度を持つ要素は「先入れ」「先出し」の順序が維持されます。 PriorityQueue の反復は破壊的であり、キューが空になるまで継続的にポップ操作を行うことと同等です。最大ヒープを使用して実装されています。

Ds\PriorityQueue implements Ds\Collection {
/* Constants */
const int MIN_CAPACITY = 8 ;
/* 方法 */
public void allocate ( int $capacity )
public int capacity ( void )
public void clear ( void )
public Ds\PriorityQueue copy ( void )
public bool isEmpty ( void )
public mixed peek ( void )
public mixed pop ( void )
public void push ( mixed $value , int $priority )
public array toArray ( void )
}

以上がPHP データ構造における DS 拡張例の分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。