Je recherche une liste liée et une mise en œuvre des algorithmes connexes pour Python. Tout le monde, je demande simplement vous recommande d'utiliser des listes de Python intégrées, mais les mesures de performance indiquent que l'insertion et la suppression de la liste sont un goulot d'étranglement pour notre application. Il est trivial d'implémenter une liste liée simple, mais je me demande s'il existe une bibliothèque mature qui inclut certaines opérations telles que Tri, fusionner, épissure, recherche, limite inférieure / supérieure, etc.
Je sais que c'est une dupe, mais la recherche de la liste de Python sur tout moteur de recherche donne des résultats prévisibles de mauvaises pauvres, avec la plupart des gens qui disent que les listes liées sont inutiles à Python (PFFT!).
PS: J'ai besoin d'insérer et de retirer de n'importe où dans la liste, pas seulement des extrémités.
OK, vous avez demandé cela: J'ai besoin de maintenir une liste ordonnée de plusieurs centaines de milliers d'entrées. Je vais itérair sur la liste en avant (un par un), en utilisant un visiteur à chaque entrée, à partir du début ou d'une position trouvée par une recherche binaire. Lorsqu'une entrée correspondant à un prédicat est trouvée, il est supprimé de la liste, puis une autre recherche binaire est effectuée sur un sous-ensemble de la liste à partir de la position précédente de la saisie supprimée, jusqu'à ce qu'une position déterminée de manière statistique à l'avance. Ignorant la condition d'erreur, l'entrée modifiée peut être utilisée pour créer une autre liste liée qui est épissée dans la nouvelle position trouvée à travers la deuxième recherche binaire. L'itération se poursuit de la position où l'entrée a été supprimée. À l'occasion, plusieurs milliers d'entrées commandées contiguës peuvent être ajoutées / supprimées de n'importe quel endroit de la liste. Parfois, plusieurs milliers d'entrées non contiguës doivent être recherchées et éliminées progressivement.
La liste de Python n'est inhibérable que le coût de l'insertion / retrait est prohibitif et que les gains mineurs à la vitesse de la recherche binaire ne sont totalement pas pertinents pour le coût total. Nos tests confirment ce .
Si j'ai négligé tout détail peut-être que je peux vous envoyer une copie de la convention de non-divulgation de mon entreprise et que je peux vous contacter en privé avec vous à ce sujet. sarcasm.end () .
10 Réponses :
Voici un Blog Post partage de votre douleur. Il comprend une implémentation d'une liste liée et une comparaison de performance.
Bon début, cependant, ce n'est pas O (1) insertion / retrait. :-P mais peut-être que cela conviendra bien aux objectifs de l'OP.
Malheureusement non. Je l'ai trouvé aussi, et c'est une forte amélioration, mais ... comme à côté, c'est très bizzare comment tout le monde que je demande me dit ce dont j'ai vraiment besoin est XYZ, quand je suis assez expérimenté pour savoir que j'ai juste besoin d'une liste liée ! BTW qui ne vous vise pas, l'aide est appréciée, je viens de vous éventer.
@known: Mais il suffit de mettre en œuvre une liste liée à Python est facile. Vraiment. Avez-vous regardé ce poteau de blog? Le gars implémente-le. Avez-vous besoin d'une solution python python ou d'extension C?
Je sais que c'est simple, mais j'aimerais éviter d'écrire des algorithmes de zéro. Cela étant dit, je suis assez démissionné de faire cela, je ne pense pas que je trouve ce que je cherche. BTW, Great Pygame Tutorials Eli, j'utilise votre code pour enseigner à ma cousine une programmation de jeu!
DEQUE classe est 0 (1) Pour l'insertion et la suppression au début et à la fin de la liste.
Il y a une liste à une seule liaison Voici Cette recette est une implémentation C très concise C de (en lecture seule) LISP- comme des consignes - juste une voiture, un CDR et des inconvénients; Encore une fois, pas un type riche, plutôt minime (et de l'utiliser pour les données mutables, par opposition à des approches fonctionnelles pures, vous auriez besoin d'ajouter SetCar et SetCDR au moins). Il peut s'agir d'un meilleur point de départ pour vous simplement parce que les Cons-cellules sont si notorieusement flexibles et familiers.
Certaines des opérations dont vous avez besoin seront probablement meilleures faites par les primitives existantes de Python. Par exemple, pour le tri, il est difficile de voir comment rouler votre propre tri peut battre les performances de la Plus généralement, je vous suggère avec soin
"mature" ou riche - il suffit de faire une file d'attente FIFO donc c'est assez minimal.
de Python (LinkedList) (si longtemps que vous effectuez la liste linkedlist Un python itéroureux de sorte qu'il joue bien avec le reste de la langue et de la bibliothèque ;-), en tenant compte de la puissance du Timsort algorithme implémenté dans le runtime Python.
Timeiit Toutes les choses en cours pour déterminer le montant de l'approche codée C qui vous achète vraiment (par rapport au codé c-codé trivial exemplaire par la recette Dans le livre de recettes imprimé dont l'URL que je donne au début de cette réponse) - qui dépendra essentiellement de la taille et de la nature des listes de votre application, vous êtes donc le mieux placé pour organiser ces points de repère bien sûr.
Les listes Python sont O (1) pour les opérations à la fin de la liste . Si vous effectuez tout votre insertion de mode semi-séquentielle - par analogie à C, gardez un seul pointeur au milieu de la liste comme un "curseur" de TRES - Vous pouvez vous épargner beaucoup d'effort en utilisant simplement deux listes Python. Une liste pour ce qui est avant le curseur, un pour ce qui est après; Le déplacement du curseur consiste à tirer le point suivant d'une liste et à l'ajouter à l'autre. Cela vous donne une insertion arbitraire O (1) à l'emplacement du curseur avec un effort beaucoup moins moins d'effort et de la réinvention de la roue que de faire une nouvelle structure de données, vous permettant de réutiliser beaucoup de fonctions de la liste existantes.
Pour l'affaire entièrement générale permettant à plusieurs références dans la liste, vous êtes probablement bloqué en faisant une liste liée de quelque sorte.
edit: Vous ne pensez pas sérieusement à faire une "recherche binaire" sur une liste liée, êtes-vous? La recherche binaire n'a même pas de sens sur une structure de données intrinsèquement séquentielle ...
Quoi qu'il en soit, si vous acceptez une recherche de temps linéaire et vos insertions préserveront toujours la commande de liste sans le tri de la récidive, une simple liste liée peut être tout ce dont vous avez besoin. Si vous recherchez autant que vous recherchez, vous devez considérer quelque chose avec une indexation rapide et si le recours peut être nécessaire, quelque chose comme un arbre serait mieux.
Insérer / supprime au début de la liste ne sont pas O (1) mais O (n).
Mais ils sont O (1) au fin de la liste, ce que j'ai dit exactement. Notez que la liste représentant ce qui vient après que le curseur serait dans l'ordre inversé, si cela n'était pas évident.
S'il vous plaît lire la modification. Oui, je fais une recherche binaire sur une liste liée, cela arrive tout le temps et est parfaitement acceptable lorsque les coûts sont compris. Je devrais mentionner que la recherche est sur un sous-ensemble de la liste prédéterminée statistiquement et non la liste complète.
"Je vais itération sur la liste en avant (un par un), à l'aide d'un visiteur à chaque entrée, à partir du début ou d'une position trouvée par une recherche binaire. Lorsqu'une entrée correspondant à un prédicat est trouvée, il est trouvé qu'il est supprimé de la Liste, puis, une autre recherche binaire est effectuée sur un sous-ensemble de la liste à partir de la position précédente de la saisie supprimée "
On dirait que la liste liée est absolument la mauvaise structure de données pour cela - une recherche binaire nécessitera un accès aléatoire à la liste, ce qui signifie une itération répétée à travers les éléments. Ceci est susceptible d'être plus lent sur une liste liée que l'insertion et la suppression d'éléments dans une liste Python.
Il ressemble à la structure de données que vous voulez est un Skip List . Google jette plusieurs implémentations, mais je ne peux pas commenter leur complétude ou leur qualité.
Une autre structure de données pouvant être appropriée est un arbre binaire fileté . Ceci est comme un arbre binaire régulier, mais chaque nœud de feuille pointe vers le sous-arbre suivant / précédent, il peut donc être itéré à la fois comme une liste liée. La mise en œuvre dans Python est laissée comme un exercice pour le lecteur (ou Google).
En réalité, il n'est pas plus lent, la recherche binaire est effectuée sur un sous-ensemble de la liste, prédéterminée statistiquement et nos tests ont indiqué que la recherche n'est pas un goulot d'étranglement, mais l'insertion et la suppression sont.
Il est introuvable que tout le monde exige que la justification nécessite une liste liée. Les listes liées sont l'une des structures de données les plus élémentaires pour une raison: elles ont des propriétés que les autres structures de données majeures manquent, et si vous avez besoin de ces propriétés, vous avez besoin d'une liste liée ou d'un de ses proches parents. Si vous ne comprenez pas pourquoi les listes liées sont une structure de données importante qui ne peut toujours pas être remplacée par une deque ou un arborescence binaire, vous n'auriez pas dû réussir votre classe «Intro to Structures de données».
Voici une mise en œuvre rapide , Soutenir les trucs habituels: Insertion de temps constant à tout moment donné d'une référence au nœud, divisant la liste dans deux listes et insérez une liste au milieu d'une autre liste (épissure). Les interfaces Génériques Python sont prises en charge: poussez, pop, pousseft, plongée, étendue, itération ordinaire, itération sur une tranche (getiter).
Je viens d'écrire cela, donc c'est doctaté mais pas testé de la production; Il y a probablement toujours des bugs.
Merci beaucoup, ressemble à celui que j'ai écrit la nuit dernière. Ne me faites pas commencer sur toute la religion de Python, je suis exaspéré par les appels constants de la justification pour une question extrêmement simple. Merci encore pour la réponse raisonnée et réfléchie, malheureusement une chose rare ces jours-ci.
Et, bien sûr, c'est pourquoi ce type manquant de la bibliothèque standard est un tel problème: tout le monde finit par avoir à rouler le leur, qui est une perte de temps et entraîne des interfaces différentes et incompatibles. Une liste liée n'est pas un type de données obscuchy, spécialisé; Ses structures de données 101. Les arbres binaires sont un écart tout aussi important dans la bibliothèque standard de Python.
Il est probable que les gens interrogent la motivation car, après avoir passé "Intro aux structures de données", il est assez inhabituel de en réalité besoin d'une liste liée spécifiquement pour ses caractéristiques de performance. La grande majorité du temps, si les données sont suffisamment grandes pour s'inquiéter de la complexité du temps, le tri, l'indexation ou la recherche seront nécessaires, et des listes liées sont spectaculairement mauvais du tout. Sans contexte, insister sur une liste liée semble suspicieusement une erreur de conception, en particulier lorsque les demandes de clarification sont remplies d'une hostilité injustifiée.
Ouais, je l'obtiens, mais en face de la conversation face à la conversation si je devais répondre à une question avec «pourquoi, je pense que ce dont vous avez vraiment besoin est XYZ», cela partirait comme impoli. Je prends la responsabilité de mon attitude tempérée et hostile, mais je ne pense pas que cela soit entièrement injustifié compte tenu de la plupart des réponses qui remettent en question ma motivation au lieu de donner une tentative honnête à une réponse appropriée. Je peux gérer un peu d'interrogation, mais certaines personnes préfèrent interroger de manière agressive plutôt que de réagir de manière significative.
La double vérification est une chose (beaucoup de débutants posent des questions au niveau de "mon script Python est lent, y a-t-il un programme pour raccourcir tous mes noms de variables?"), Mais certaines personnes fonctionnent sous la croyance que personne ne pouvait jamais éventuellement éventuellement Vraiment Vous voulez quelque chose qu'ils ne sont pas utilisés eux-mêmes et s'ils le demandent, ils doivent évidemment se tromper.
Voici une idée qui nécessiterait un peu de codage, mais peut vous donner une performance extrêmement meilleure. Il peut ou non être approprié pour votre cas d'utilisation.
Vous pouvez épisser une nouvelle liste dans votre liste en remplaçant un seul élément. Pour insérer la liste [6, 7, 8] dans [1, 2, 3, 4, 5] à l'index 2, vous vous retrouveriez avec p>
[1, 2, [3, 6, 7 , 8], 4, 5] p>
en ne modifiant pas la longueur de la liste de la grande (ici 5 éléments), vous n'aurez pas les problèmes de vitesse que vous avez actuellement. P>
Vous pouvez «supprimer» un élément de la liste de la même manière, en le remplaçant par une liste vide. P>
[1, 2, [], 4, 5] P>
P> À itérer sur cette liste mixte est simple. P>
def IterateNestedList(xs):
for x in xs:
if isinstance(x, list):
for y in IterateNestedList(x): yield y
else: yield x
Pour les grandes données, gardez une liste triée. Ne pas insérer mais appendez de nouveaux articles à la fin, puis triez-le. Ne supprimez pas l'élément mais remplacez-le par une valeur spéciale, triez-les à la fin, puis faites tomber. Pour la recherche, une liste triée a également une performance très rapide avec la méthode de bisection. En ce qui concerne les petites données, itérer une liste ancienne, filtrer et construire une nouvelle méthode de compréhensions de liste, est toujours la voie rapide.
Pour moi, quelles sont les grandes données? Il devrait être plus de 1000000 articles ...
J'ai récemment eu la nécessité d'une liste circulaire et doublement liée. Comme je suis très familier avec la liste liée de Linux Kernel. J'ai écrit une liste liée à CopyCAT à Python. Il fournit O (1) insertion aléatoire et suppression. Il est beaucoup plus rapide que la liste de Python lorsque vous effectuez une insertion et une suppression aléatoires sur une grande liste. Le code est ici: https://github.com/ningke/pylnklist . J'ai également écrit un peu d'introduction ici: http: / /710003.Blogspot.com/2012/06/copycat-linked-list-in-python.html
Que diriez-vous d'utiliser l'une des structures de données fournissant un accès de données triées? Binary (AVL Arbres, Avl, Red-Black), par exemple? Ces garanties O (log (n)) complexité d'insertion. Pas O (1), mais mieux que ce que vous avez.
Voulez-vous insérer / supprimer des éléments dans O (1) uniquement au début / à la fin de la liste ou à n'importe quelle position dans la liste?
Faites-vous la liste d'insertion et de retrait des lieux autres que la fin de la liste? Ajouter est O (1), l'insertion n'est pas. Si vous insérez et enlevez des objets dans des endroits arbitraires, est-ce vraiment une liste
? Ou est-ce undict clé par des entiers?@Gumbo: Je ne pense pas que les listes de base de Python sont des Driques, ce n'est donc pas O (1) pour des insertions / déménagements au début de la liste.
J'insère n'importe où, à tout moment, il doit donc être une liste liée. J'ai passé beaucoup de temps à regarder et il semble que je puisse juste avoir à écrire le mien. Je vais l'écrire lors de mes temps libres pour que je puisse l'ouvrir, avant de le faire fonctionner.
"Insérez n'importe où, à tout moment, il doit donc être une liste liée" FALSE. Insérez n'importe où, à tout moment pourrait certainement être un
dict . Quelle condition d'exigence avez-vous ce mandat une liste? S'il vous plaît mettre à jour la question; S'il vous plaît ne pas ajouter de commentaires à une question que vous possédez.@ S.Lott: L'insertion et l'élimination sont O (1) à tout moment de la liste si vous êtes déjà là (c'est-à-dire avancer le long d'un élément à la fois en utilisant une sorte d'itérateur). Ce n'est que si vous voulez d'abord trouver un objet à supprimer par une clé ou d'insérer à un emplacement aléatoire, que ces opérations deviennent O (n).
@OP: La partie délicate de la rédaction de votre propre bibliothèque de liste liée est que vous devez créer une interface d'itération (puisque je ne pense pas que les listes de Python l'ont par défaut). :-)
@uknown: Il s'agit d'une exigence non déterminée de débordement de pile, qu'aucune question simple oui / aucune question ne peut être répondue sans que quelqu'un examine votre code. Vous ne pouvez pas demander "une bibliothèque existent à faire x" sans que quelqu'un veuille savoir pourquoi vous voudriez faire x, quand ils n'ont personnellement jamais. Désolé, c'est les règles, cela ira plus facilement sur votre tension artérielle si vous essayez de l'interpréter comme curiosité. Évidemment, S.Lott ne peut pas répondre à votre question - s'il savait une implémentation de la liste liée à Python, il ne trouverait pas la question surprenante que personne devrait vouloir utiliser une liste liée de préférence à une table de hachage.
@OP avant de devenir défensive, veuillez considérer que les gens ici essaient d'aider. S. Lott ne traîne pas quiconque; Il a donné beaucoup de bons conseils à beaucoup de gens (moi-même inclus) qui ont pensé qu'ils savaient mieux. Le problème est le problème: tout ce que vous avez dit jusqu'à présent indique que vous ne comprenez pas les structures de données et qu'il essaie de déterminer doucement pourquoi vous pensez avoir besoin d'une liste liée. Une implémentation de la liste liée de base n'a pas d'accès aléatoire avec O (1) insert.
@David: Je sais que j'ai réagi de réagir, mais j'ai réagi à toutes les personnes qui essaient de me dire quelles sont mes exigences. Je sais ce dont j'ai besoin et je connais très bien les structures de données, très bien, après avoir travaillé sur des logiciels à forte intensité de calcul pendant de nombreuses années. Je ne comprends pas comment j'ai donné l'impression d'ignorer, s'il vous plaît éclairer moi. Ai-je dit quelque chose de stupide? Pour ce que ça vaut, désolé d'être impoli.
@Op, il n'est certainement pas clair. Prenez une liste liée non augmentée. Je ne peux pas insérer dans O (1), dans n'importe quelle langue, à moins que je n'ai déjà de référence au nœud avant ou après que l'insert soit effectué. Votre cas d'utilisation est-il un cas dans lequel vous aurez toujours une telle référence? Si tel est le cas, alors il existe peut-être une implémentation de la liste liée naïve que quelqu'un peut vous indiquer. Sinon, la structure de données a besoin d'une augmentation sérieuse et nous ne savons pas quel type est nécessaire. Comme écrit, une liste liée à la liste liée à O (1) un type d'insertion aléatoire ressemble à vous demander un cercle carré.
@uknown (Google): "Mes exigences sont qu'il s'agit d'une liste liée". Pourquoi? Quelle caractéristique spécifique d'une liste liée avez-vous réellement besoin? À quelle fréquence en avez-vous besoin? Pourquoi un
dict est-il approprié? Quelle caractéristique d'undict est si répréhensible? Y a-t-il un moyen de fournir toute preuve que vous besoin une liste? Ou serait undict faire?L'une des faiblesses de Python est le manque de types de données fondamentaux: listes liées et arbres binaires, en particulier. Faire de la mise en œuvre manuellement de ces choses de base - et tout le monde se retrouve avec sa propre mise en œuvre et son apogique - dans un langage de script de haut niveau comme Python est absurde. Les gens semblent défendre presque religieusement python à ce sujet, affirmant que personne ne pouvait avoir besoin de ces types de données et que des tableaux et des tables de hachage devraient suffire à tout le monde. Cela aussi est absurde.
@uknown (Google): Une façon dont vous avez donné l'impression d'être ignorante consiste à utiliser le terme "recherche binaire" lorsque nous appellerions la plupart d'entre nous appeleraient la recherche linéaire ou séquentielle. Et ce faisant si belligérante n'aide pas votre cas.
Il stipule spécifiquement (au secondaire du dernier paragraphe) qu'il utilise actuellement des recherches binaires, puisqu'il utilise actuellement un tableau, et que, selon ses tests, ils ne contribuent pas beaucoup. Je pense qu'il signifie une recherche binaire, pas la recherche linéaire. Le fait que vous n'aimez pas que le gars n'ait probablement pas affecter votre impression de ses connaissances: je peux voir comment votre belligérance vous ferait raisonnablement de ne pas vouloir aider à fournir une réponse, mais pas comment cela pourrait vous faire raisonnablement penser qu'il soit ignorant.