Explication détaillée de l'extension DS de la structure des données en PHP

L'éditeur suivant vous proposera un article sur l'extension DS de structure de données en PHP. L'éditeur pense que c'est plutôt bien, alors je vais le partager avec vous maintenant et le donner comme référence. Suivons l'éditeur pour y jeter un œil.

Seul PHP 7 ou supérieur peut installer et utiliser cette extension de structure de données :

.

1. Exécutez 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 une interface de base avec des fonctions communes pour toutes les structures de données de cette bibliothèque. 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 d'utiliser des objets 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 à une séquence unidimensionnelle Un tableau de touches numériques, à l'exception de quelques caractéristiques :Les valeurs seront toujours indexées comme [0, 1, 2, …, taille - 1].

Autorisé uniquement à accédez aux valeurs par index dans la plage [0, taille - 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 : Un vecteur 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 des tableaux (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 de file d'attente :

collection "premier entré, premier sorti", permettant l'accès et l'itération uniquement sur le front-end du 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 avec une priorité spécifiée Dans la file d'attente, la valeur ayant la priorité la plus élevée est toujours en tête de la file d'attente et l'ordre « premier entré, premier sorti » des éléments ayant 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 max.

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 :

Algorithmes couramment utilisés en PHP et

structures de données

bases de PHP, un tableau et structure de données

Python intégréstructure de donnéesexplication détaillée

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!