ホームページ  >  記事  >  バックエンド開発  >  PHPのデータ構造:DS拡張機能の詳細説明

PHPのデータ構造:DS拡張機能の詳細説明

小云云
小云云オリジナル
2018-02-07 09:50:352597ブラウズ

この記事では主に、PHP のデータ構造である DS 拡張機能に関するありふれた話をお届けします。編集者はこれが非常に良いものだと思ったので、皆さんの参考として今から共有します。編集者をフォローして見てみましょう。皆さんのお役に立てれば幸いです。

このデータ構造拡張機能をインストールして使用するには、PHP 7 以降が必要です。インストールは比較的簡単です:

1. PHP に extension=ds.so を追加します。 .ini

3. PHP を再起動するか、設定を再ロードします

コレクション インターフェイス:

このライブラリ内のすべてのデータ構造に共通の関数が含まれる基本インターフェイス。すべての構造が走査可能であり、カウント可能であり、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 )
}

ハッシュ可能なインターフェイス:

これにより、オブジェクトをキーとして使用できます。インターフェイス: シーケンスは、一次元の数値キー配列。ただし、いくつかの特性を除きます:
値には常に [0, 1, 2, …, size - 1] としてインデックスが付けられます。

インデックスによる値へのアクセスのみが許可されます。 [0, size - 1] の範囲内。

ユースケース:

配列をリストとして使用する場合 (キーには関係ない)。

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

Vectorクラス:

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

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

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

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

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

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

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

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\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.

クラスを設定: 一意の値のシーケンス。この実装は DsMap と同じハッシュ テーブルを使用します。値はキーとして使用され、マップされた値は無視されます。

値はオブジェクトを含む任意の型にすることができます。構文 (角括弧)。挿入順序は保持されます。

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

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

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

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

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

Queue クラス:

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

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 )
}

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


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 )
}

関連推奨事項:

PHP はスタック データ構造とブラケット マッチングを実装します

PHPスタックデータ構造とブラケットマッチングアルゴリズムを例付きで説明

PHPデータ構造の逐次リンクリストと連鎖線形表現の例

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

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。