Structures de données en PHP : explication détaillée de l'extension DS

Cet article vous apporte principalement une discussion banale sur la structure des données en PHP : l'extension DS. L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Suivons l'éditeur pour y jeter un œil, j'espère que cela pourra aider tout le monde.

Seul PHP 7 ou supérieur peut installer et utiliser cette extension de structure de données. L'installation est relativement simple :

1. la commande pecl install ds

2. Ajoutez extension=ds.so dans php.ini

3. Redémarrez PHP ou rechargez la configuration

Interface de collection : contient cette bibliothèque L'interface de base pour les fonctions communes de toutes les structures de données dans . Il garantit que toutes les structures sont traversables, dénombrables et peuvent être converties en json à l'aide de json_encode().

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

Interface Hashable : qui permet aux objets d'être utilisées comme clés.

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

Interface de séquence : Une séquence est équivalente à un tableau de touches numériques unidimensionnelles, à l'exception de quelques caractéristiques :

Les valeurs seront toujours indexées comme [0, 1, 2, …, taille - 1].

Autorisé uniquement à accéder aux valeurs par index dans le range [ 0, size - 1].

Cas d'utilisation :

Partout où vous utiliseriez un tableau comme liste (ne concerne pas les clés).

Une alternative plus efficace à SplDoublyLinkedList et SplFixedArray.

Classe Vector : Vector est une séquence de valeurs dans un tampon continu qui grandit et rétrécit automatiquement. Il s'agit de la structure séquentielle la plus efficace, l'index de la valeur correspond directement à l'index dans le tampon et le facteur de croissance n'est pas lié à un multiple ou à un exposant spécifique. Il présente les avantages et les inconvénients suivants :

Prend en charge la syntaxe de tableau (crochets).

Utilise moins de mémoire globale qu'un tableau pour le même nombre de valeurs.

Libère automatiquement mémoire allouée lorsque sa taille diminue suffisamment.

La capacité ne doit pas nécessairement être une puissance de 2.

get(), set(), push(), pop() sont tous O (1 ).

Mais shift(), unshift(), insert() et remove() sont tous des 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.

Classe Deque : L'abréviation de "file d'attente double-ended", également utilisée dans DsQueue, a deux pointeurs, tête et queue. Les pointeurs peuvent « enrouler » la fin du tampon, ce qui évite d'avoir à déplacer d'autres valeurs pour libérer de l'espace. Cela rend le décalage et le décalage très rapides, ce avec quoi un DsVector ne peut pas rivaliser. Il présente les avantages suivants. et inconvénients :

Prend en charge la syntaxe des tableaux (crochets).

Utilise moins de mémoire globale qu'un tableau pour le même nombre de valeurs.

Libère automatiquement la mémoire allouée en fonction de sa taille tombe suffisamment bas.

get(), set(), push(), pop(), shift() et unshift() sont tous O(1).

Mais la capacité doit être une puissance de 2.insert() et remove() sont O(n).

Classe Map : Une collection continue de paires clé-valeur, presque identique à un tableau. Les clés peuvent être de n’importe quel type mais doivent être uniques. Si elle est ajoutée à la carte avec la même clé, la valeur sera remplacée. Il présente les avantages et les inconvénients suivants :

Les clés et les valeurs peuvent être de n'importe quel type, y compris les objets.

Prend en charge la syntaxe des tableaux (crochets).

L'ordre d'insertion est préservé.

Les performances et l'efficacité de la mémoire sont très similaires à celles d'un tableau.

Libère automatiquement la mémoire allouée lorsque sa taille diminue suffisamment.

Ne peut pas être convertie à un tableau lorsque des objets sont utilisés comme clés.

Classe de paire :Une paire est utilisée par DsMap pour associer des clés à des valeurs.

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

Définir la classe : Séquence de valeurs unique. Cette implémentation utilise la même table de hachage que DsMap, où les valeurs sont utilisées comme clés et la valeur mappée est ignorée. Elle présente les avantages et les inconvénients suivants :

Les valeurs peuvent être de n'importe quel type, y compris les objets.

Prend en charge la syntaxe des tableaux (crochets).

L'ordre d'insertion est conservé.

Libère automatiquement la mémoire allouée lorsque sa taille diminue suffisamment.

ajouter( ), remove() et contain() sont tous O(1).

mais ne prend pas en charge push(), pop(), insert(), shift() ou unshift() . get() est O (n) s'il y a des valeurs supprimées dans le tampon avant l'index accédé, O(1) sinon

Stack Class : « last ». collection "in, first out", autorise uniquement l'accès et l'itération en haut de la structure.

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

Classe Queue : collection "premier entré, premier sorti", permettant l'accès et l'itération uniquement sur le devant de la structure.

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

Classe PriorityQueue : Une file d'attente prioritaire est très similaire à une file d'attente, mais les valeurs sont poussées dans la file d'attente avec une priorité spécifiée , first La valeur avec la priorité la plus élevée est toujours en début de file d'attente, et l'ordre « premier entré, premier sorti » des éléments avec la même priorité est toujours conservé. L'itération sur une PriorityQueue est destructrice et équivaut à des opérations pop continues jusqu'à ce que la file d'attente soit vide. Implémenté à l'aide d'un tas maximum.

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

Recommandations associées :

PHP implémente la structure de données de pile et la correspondance entre crochets

Explication de la structure de données de la pile PHP et exemples d'algorithmes de correspondance entre crochets

Exemples de liste chaînée séquentielle et d'expression linéaire liée de la structure de données PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!