Quel est le point de la classe SplDoublyLinkedList de PHP, et plus important encore, listes chaînées en général?
https://stackoverflow.com/questions/3963288
-
09-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En quête d'étendre mes prouesses de programmation, je l'ai fouilla toujours aussi légèrement dans La bibliothèque standard PHP . Cela a conduit à ma découverte de la classe SplDoublyLinkedList . A partir de là, je lis les descriptions des listes chaînées et doublement listes chaînées sur Wikipedia.
Je comprends comment ils fonctionnent ... Mais je ne peux pas imaginer une raison pour laquelle nous en avons besoin ou mieux encore un exemple concret de SplDoublyLinkedList puisque nous avons indexé et des tableaux associatifs en PHP.
Comment sont liés les listes normalement utilisés dans les entrées et sorties de PHP?
La solution
Les structures de données de SPL réduire la consommation de mémoire et améliorer les performances. De bonnes explications:
structures de données sont par nature indépendante de la langue et existe comme un ensemble de concepts logiques basés en mathématiques. Ces conteneurs utilisent des algorithmes différents selon le cas pour maximiser l'efficacité.
Par exemple, si vous n'avez pas besoin des capacités de carte de hachage d'un tableau associatif - qui est, si vous n'utilisez pas la clé du tableau dans un but spécifique et seulement besoin d'un tableau dénombrée - SplFixedArray (anciennement SplFastArray , actuellement en situation irrégulière) peut être un remplacement approprié. La seule réserve est que la taille du tableau est fixe, ce qui signifie que vous devez spécifier la taille lorsque vous instancier la classe et une erreur se produit si vous essayez de stocker plus de ce nombre d'éléments. Ceci est la raison pour laquelle, en moyenne, il est plus performant que les tableaux standards PHP.
Dans le code C qui fait l'interpréteur PHP, les tableaux sont mis en œuvre en tant que structure de données appelée une table de hachage ou d'une carte de hachage. Lorsque la valeur contenue dans un tableau est référencé par son index, PHP utilise une fonction de hachage pour convertir cet index dans une table de hachage unique représentant l'emplacement de la valeur correspondante dans la matrice.
Cette carte hachage permet la mise en œuvre des tableaux pour stocker un nombre arbitraire d'éléments et donner accès à tous ces éléments en utilisant simultanément sur les touches numériques ou chaîne. Les tableaux sont extrêmement rapides pour les capacités qu'ils fournissent et sont une excellente structure de données à usage général.
Dans la science informatique, une liste est définie comme une collection ordonnée de valeurs. Une liste liée est une structure de données dans laquelle chaque élément de la liste comprend une référence à une ou les deux des éléments de chaque côté de celui-ci à l'intérieur de la liste. Le terme « liste doublement chaînée » est utilisé pour désigner ce dernier cas. Dans le SPL, cela prend la forme de la SplDoublyLinkedList classe .... Il est logique de listes d'utilisation lorsque le nombre d'éléments à stocker ne sont pas connus à l'avance et les éléments ne doivent être accessibles par position séquentielle.
http://matthewturland.com / 2010/05/20 / nouveaux-spl-fonctionnalités-en-php-5-3 /
Autres conseils
Selon Wikipedia ,
Le principal avantage d'une liste chaînée sur un réseau classique est que le ordre des éléments liés peut être différent de l'ordre dans lequel les données les articles sont stockés dans la mémoire ou sur le disque. Pour cette raison, les listes chaînées permettent insertion et le retrait de noeuds à tout pointer dans la liste, avec une constante nombre d'opérations.
D'autre part, listes chaînées par eux-mêmes ne permettent pas l'accès aléatoire aux données, ou une forme quelconque de l'efficacité indexage. Ainsi, de nombreuses opérations de base - comme l'obtention du dernier noeud de la liste, ou de trouver un nœud contient une donnée donnée, ou localisation le lieu où un nouveau nœud doit être inséré - peut nécessiter la numérisation plus des éléments de la liste.
Pour répondre à votre question, je ne sais pas. :)
D'abord et avant tout, SplDoublyLinkedList sont des objets, en tant que tels
- ils peuvent être étendu, de sorte que vous pouvez remplacer leurs méthodes (vous pouvez par exemple Renvoyez toutes les chaînes en majuscule, etc.)
- les interfaces qu'ils mettent en œuvre peut être vérifiée comme dans
myfunc( SplDoublyLinkedList $var ) ... - ils sont passés comme référence par défaut
- etc.
En second lieu, SplDoublyLinkedList accepter itération modes, de sorte que vous pouvez supprimer vos articles sur la route, et la direction du commutateur sans réorganisant le tableau ou compliquer votre code:
SplDoublyLinkedList :: IT_MODE_LIFO (style Stack)
SplDoublyLinkedList :: IT_MODE_FIFO (style de file d'attente) Le comportement du itérateur (l'un ou l'autre)
SplDoublyLinkedList :: IT_MODE_DELETE (Les éléments sont supprimés par le itérateur)
SplDoublyLinkedList :: IT_MODE_KEEP (Les éléments sont traversés par l'itérateur)
La citation ci-dessus est de http://simpletechinfo.com/SplDoublyLinkedList qui contient des échantillons de code.
Il y a d'autres avantages (comme foreach ne pas avoir à faire une copie en mémoire de toutes les données, etc.)
Ils sont là parce que beaucoup de programmeurs comming d'autres langues sont utilisées pour les tableaux où ont une taille fixe et vous devez prendre soin de gestion de la mémoire.
Donc, pour PHP ils sont juste un autre outil. Ils sont mis en œuvre parce que de nombreux algorithmes et relais de modèle sur les listes et ils ne doivent pas être modifiés pour les tableaux PHP.
Comme d'autres l'ont mentionné, les listes sont une alternative aux réseaux fixes qui sont communs dans d'autres langues. Mais un aspect important qui est souvent négligé - vous pouvez insérer ou retirer un élément de n'importe où dans une liste très efficace
.Pourquoi serait-ce important? Disons que vous avez plusieurs éléments que vous souhaitez conserver triés dans un tableau, peut-être que vous ne devez pas les trier plus tard ou tout simplement pour réduire le temps de recherche. Dans ce cas, une liste peut être un outil très puissant. Surtout pour les jeux de données très volumineux.
Vous avez probablement raison, et il est tout simplement pas très utile.
Il existe de nombreuses utilisations de listes liées à la théorie (notamment les liens de danse). Mais la plupart d'entre eux implique soit le stockage et le clonage de ses itérateurs ailleurs, l'accès au contenu dans plus de deux directions, ou le fractionnement et la fusion des listes. SplDoublyLinkedList ne semblait pas avoir ceux-ci.
Si ce n'est pas pour les algorithmes, une utilisation est de permettre à un objet de supprimer la référence de lui-même dans une liste constante de temps, ce qui libère sa mémoire et sans brouiller la liste (par hachage ou échange avec le dernier élément) après l'insertion ou effacement. Mais cela nécessite le stockage d'un itérateur de la liste dans ces objets.
Sans ces fonctionnalités, ils se comportent comme deux Deques. Si vous ne devez accéder à des éléments en utilisant l'itérateur, ils sont comme deux piles. Une meilleure façon dans les cas de simples filetés simples, Bärring pas déjà enveloppé dans une classe, est juste d'utiliser deux piles (réseaux fixes, peut-être ou les deux extrémités du même tableau). Pop d'une pile et poussez-le à l'autre chaque fois que vous voulez que le iterator de se déplacer, et le haut d'une pile est l'élément en cours. Si vous avez également besoin d'accéder à la tête et la queue, vous devrez remplacer les piles avec Deques.
Mais si vous voulez mettre en œuvre des piles ou Deques eux-mêmes sans connaître la taille maximale, ou même d'affecter des noeuds de listes chaînées normales (dans une langue sans les bibliothèques comme en PHP), est la bonne voie à la chaîne des tableaux fixes ensemble , en utilisant des listes doublement chaînée sans ces caractéristiques. D'une certaine façon, vous aurez toujours besoin.
La documentation PHP lui-même, comme le Java un, suggère qu'ils sont censés être juste un deque supportant des fonctionnalités supplémentaires étranges, pas même deux Deques (je pense). Ne pas les utiliser si vous avez vraiment besoin des listes doublement chaînées.
