Analyse d'exemples d'extensions DS dans la structure de données PHP

L'éditeur suivant vous apportera une présentation 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.

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 reloadconfiguration

.

Interface de collection : Une interface de base qui contient 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 Séquence :

Une Séquence équivaut à un tableau de clés numériques unidimensionnelles, à l'exception de quelques caractéristiques :Valeurs sera toujours indexé comme [0, 1, 2, …, taille - 1].

Autorisé uniquement à accéder 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 de vecteur :

Un vecteur est une séquence de valeurs dans un tampon continu qui grandit et diminue 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", également utilisée dans DsQueue, comporte 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ée.

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

Set Class :

Séquence de valeurs uniques. 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 front end 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 :

PrioritéUne file d'attente 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, avec le priorité la plus élevée La valeur est toujours en début de 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 maximum.

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!