Maison  >  Article  >  développement back-end  >  Utilisation des structures de données PHP7.2

Utilisation des structures de données PHP7.2

不言
不言original
2018-07-06 15:11:121934parcourir

Cet article présente principalement l'utilisation des structures de données PHP7.2, qui ont une certaine valeur de référence. Maintenant, je le partage avec tout le monde. Les amis dans le besoin peuvent s'y référer

L'utilisation des structures de données PHP7.2.

1. Installation

pecl install ds
brew install homebrew/php/php71-ds

Actuellement, PHP7.2 ne prend pas en charge l'installation à l'aide de Brew.

2. La structure de données originale de PHP Array

À l'ère de PHP5.x, Array est le seul type de données qui représente une collection en PHP, c'est à la fois une liste. et une carte. Il est tout.

<?php $a = array(1,2,3,4);
$b = array(&#39;a&#39;=>1,'b'=>2,'c'=>3);

Ce type de données est pratique pour les développeurs, mais PHPer ignorera les avantages des structures de données, en particulier lorsque l'apprentissage d'autres langages pose problème.

Après la mise à niveau de PHP vers 7, Array a également été optimisé, mais sa structure n'a pas changé, "optimisée pour tout ; optimisée pour rien" avec marge d'amélioration. Donc, si nous pouvons optimiser les performances en introduisant des structures de données plus pratiques, et en même temps écrire du code sera plus pratique, alors pourquoi pas ?

"Qu'en est-il de la structure de données SPL ?"
Malheureusement, ils le sont terribles. Ils offraient certains avantages avant PHP 7, mais ont depuis été négligés au point de n'avoir aucune valeur pratique.

"Pourquoi ne pouvons-nous pas les réparer et les améliorer ?"
Nous pourrions, mais je crois. leur conception et leur mise en œuvre sont si médiocres qu'il serait préférable de les remplacer par quelque chose de tout nouveau.

« La conception des structures de données SPL est terrible - Anthony Ferrara

<.>Le tableau de PHP peut devenir nul lors de l'accès à une clé inexistante, et aucune erreur fatale ne se produira, mais il y aura un E_NOTICE. Ce E_NOTICE sera intercepté par la fonction enregistrée par set_error_handler. De toute évidence, ce type de code impur et cette surcharge de performances inutile peuvent être complètement évités.

  • Général PHPer n'utilisera pas array_key_exists et sinon, le gérer sera un peu gênant.
<?php $a = [];
$a[&#39;a&#39;]; // PHP Notice:  Undefined offset

Parfois, les performances deviendront très mauvaises lors de l'utilisation d'Array. Le tableau est essentiellement une carte. Décaler un élément changera la clé de chaque élément. Il s'agit d'une opération O(n). De plus, Array de PHP enregistre sa valeur (y compris la clé et son hachage) dans un bucket, nous devons donc vérifier chaque bucket et mettre à jour le hachage.

  • PHP termine en interne l'opération array_unshift en créant un nouveau tableau, et les problèmes de performances peuvent être imaginés.

  • DataStructures, une extension de PHP7, un remplacement du tableau (Array).

Github

 : https://github.com/php-ds

Espace de noms :Ds

Interface Classe : Collection, Sequence, Hashable

Classe d'implémentation (classe finale) : Vector, Deque, Map, Set, Stack, Queue, PriorityQueue, Pair

Classe d'interface

Utilisation des structures de données PHP7.2

Collection est une interface de base qui définit les opérations de base d'une collection de données (la collection fait ici référence à Collection, pas à Set). exemple, foreach, echo, count, print_r, var_dump, serialize, json_encode et clone etc.

  • La séquence est l'interface de base d'une structure de données de type tableau et définit de nombreuses méthodes importantes et pratiques, telles que contenir, mapper, filtrer, réduire, rechercher, premier, dernier, etc. Comme le montre la figure, Vector, Deque, Stack et Queue implémentent tous directement ou indirectement cette interface. Ses caractéristiques sont les suivantes :

  • La valeur sera toujours indexée [0, 1, 2, …, taille - 1]
    • La suppression ou l'insertion met à jour la position de toutes les valeurs consécutives.

    • autorise uniquement l'accès aux valeurs avec des index en [0, taille-1].

    • Hashable semble isolé dans le diagramme, mais est important pour les cartes et les ensembles. Si un objet implémente Hashable, il peut être utilisé comme clé de Map et élément de Set. De cette façon, Map et Set peuvent être utilisés aussi facilement que Java.
  • Classe d'implémentation

Vector devrait être l'une des structures de données les plus couramment utilisées. Vous pouvez le considérer comme Ruby's Array ou Python's List. L'index de la valeur de son élément est son index dans le tampon, c'est donc très efficace. Vous pouvez l'utiliser aussi longtemps que vous avez besoin d'utiliser un tableau et que vous n'avez pas besoin d'insérer, de supprimer, de décaler et d'annuler le décalage.

Description de la vidéo

  • La principale structure de données utilisée dans PhotoShop est Vector ---- Sean Parent
    • La complexité de l'insertion, de la suppression, du décalage et de l'annulation du décalage est O(n)

    • Faible utilisation de la mémoire

    • get, set, la complexité du push et du pop est O(1)

    • Avantages :

    • Inconvénients :

    • Deque (prononcé [dek]) est une "file d'attente à double extrémité". Un pointeur de tête est ajouté à la file d'attente, donc shift et unshift sont également complexes O(1). Mais la perte de performances n’est pas importante.

    Deux pointeurs sont utilisés pour garder une trace de la tête et de la queue, et les pointeurs peuvent être "enroulés" autour de la fin du tampon, ce qui évite d'avoir à déplacer d'autres valeurs pour faire de la place. Cela rend les changements de vitesse très rapides - Vector ne peut pas rivaliser avec cela. Description de la vidéo

    • La complexité de l'insertion et de la suppression est O(n).

    • La capacité du tampon doit être de 2 à la nième puissance.

    • Faible utilisation de la mémoire.

    • La complexité de get, set, push, pop, shift et unshift est O(1).

    • Avantages :

    • Inconvénients :

    • La pile est une structure "LIFO", selon Le principe du « dernier entré, premier sorti » permet d'accéder, de parcourir et de détruire les valeurs en haut de la structure. DsStack utilise en interne l'implémentation de DsVector.

    • La file d'attente est une structure "FIFO" qui permet l'accès, le parcours et la destruction des valeurs en haut de la structure selon le principe "premier entré, premier sorti". DsQueue utilise en interne l'implémentation de DsDeque.

    • PriorityQueue (Priority Queue) est très similaire à Queue, les valeurs sont poussées dans la file d'attente en fonction de la priorité attribuée, et la valeur avec la priorité la plus élevée est toujours au début de la file d'attente. Le parcours de PriorityQueue est destructeur et équivaut à des opérations pop continues jusqu'à ce que la file d'attente soit vide. Utilisez l'implémentation max-heap.

    • Hashable , une interface qui permet d'utiliser des objets comme clés. Remarque : ce n'est pas le cas hashTable. Hashable n'introduit que deux méthodes : le hachage et l'égalité. Les structures de données qui prennent en charge l'interface Hashable sont Map et Set.

    • Map, une collection continue de paires clé-valeur. C'est cohérent avec l'utilisation de array. La clé peut être de n'importe quel type, mais elle doit être unique. Si la même clé est ajoutée à la carte, celle d'origine sera remplacée. Comme pour le tableau, l'ordre d'insertion est conservé.

      • Lorsque la clé est un objet, elle ne peut pas être convertie en tableau.

      • L'efficacité et l'utilisation de la mémoire sont presque les mêmes que celles du tableau

      • Lorsque la taille de la carte tombe à un petit taille suffisante, elle sera automatiquement libérée de la mémoire allouée.

      • la clé et la valeur peuvent être de n'importe quel type, même des objets.

      • La complexité de put, get, Remove et hasKey est O(1)

      • Avantages :

      • Inconvénients :

    • Set est une collection non ordonnée de valeurs uniques. Map utilise l'implémentation de set en interne, et ils sont tous basés sur la même structure interne de Array, ce qui signifie que le tri de Set a une complexité de O(n*log n).

      • Ne prend pas en charge push, pop, insert, shift, unshift

      • Si la valeur est supprimée avant l'indexation, la complexité sera être De O(1) à O(n)

      • L'addition, la suppression et la référence sont toutes de complexité O(1)

      • L'utilisation de l'interface Hashable

      • prend en charge tout type de valeur.

      • Avantages :

      • Inconvénients :

    Ici Pour clarifier, la valeur dans Array elle-même n'a pas d'index, donc lors de l'utilisation de in_array(), il s'agit d'une recherche linéaire avec une complexité de O(n).
    Si vous souhaitez créer un tableau de valeurs uniques, vous pouvez utiliser array_unique() Puisque array_unique() cible la valeur plutôt que la clé, chaque membre du tableau sera recherché dans une ligne limitée et la complexité deviendra O(n². ).

    Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !

    Recommandations associées :

    Comment compiler et installer Redis et Swoole étendus en 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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn