


Deque en Python : implémentation de files d'attente et de piles efficaces
deque en Python est un deque de bas niveau hautement optimisé, utile pour implémenter des files d'attente et des piles Pythoniques élégantes et efficaces, qui sont les types de données basés sur des listes les plus courants en informatique.
Dans cet article, M. Yun Duo apprendra ce qui suit avec vous :
- Commencer à utiliser deque
- Faire apparaître et ajouter des éléments efficacement
- Accéder à n'importe quel élément de deque
- Créer une file d'attente efficace avec deque
Commencez à utiliser deque
Les opérations d'ajout d'éléments à l'extrémité droite d'une liste Python et d'affichage d'éléments sont généralement très efficaces. Si la complexité temporelle est exprimée en Big O, alors on peut dire qu'ils sont O(1). Lorsque Python doit réallouer de la mémoire pour augmenter la liste sous-jacente afin d'accepter de nouveaux éléments, ces opérations ralentiront et la complexité temporelle peut devenir O(n).
De plus, les opérations d'ajout et d'affichage d'éléments à l'extrémité gauche de la liste Python sont également très inefficaces, avec une complexité temporelle de O(n).
Étant donné que les listes fournissent les opérations .append() et .pop(), elles peuvent être utilisées comme piles et files d'attente. Les problèmes de performances liés aux opérations d'ajout et d'affichage aux extrémités gauche et droite de la liste affecteront grandement les performances globales de l'application.
Le deque de Python a été le premier type de données ajouté au module de collections dans Python 2.4. Ce type de données est spécifiquement conçu pour surmonter les problèmes d'efficacité de .append() et .pop() dans les listes Python.
Les Deques sont des types de données de type séquence conçus comme une généralisation des piles et des files d'attente, ils prennent en charge des opérations d'ajout et de pop rapides et efficaces en mémoire aux deux extrémités de la structure de données.
Les opérations d'ajout et de pop aux deux extrémités d'un objet deque sont stables et tout aussi efficaces car le deque est implémenté sous la forme d'une liste doublement chaînée. De plus, les opérations d'ajout et de pop sur deque sont également sécurisées pour les threads et économes en mémoire. Ces fonctionnalités rendent deque particulièrement utile pour créer des piles et des files d'attente personnalisées en Python.
Si vous devez enregistrer la dernière liste d'éléments vus, vous pouvez également utiliser deque, car la longueur maximale de deque peut être limitée. Si nous faisons cela, une fois le deque plein, il supprimera automatiquement les éléments à une extrémité lorsque nous ajouterons de nouveaux éléments à l’autre extrémité.
Ce qui suit est un résumé des principales fonctionnalités de deque :
- Stocke les éléments de tout type de données
- est un type de données mutable
- Prend en charge les opérations des membres avec l'opérateur in
- Prend en charge les index, tels que a_deque[i]
- Non Prend en charge le découpage, tel que a_deque[0:2]
- Prend en charge les fonctions intégrées qui opèrent sur des séquences et des objets itérables, tels que len(), sorted(), reversed(), etc.
- Ne prend pas en charge le tri sur place
- Prend en charge l'itération normale et l'itération inverse
- prend en charge l'utilisation de pickle
- garantissant des opérations de pop et d'ajout rapides, efficaces en mémoire et sécurisées pour les threads aux deux extrémités
La création d'instances deque est relativement simple. Importez simplement deque depuis la collection et appelez-le avec un itérateur facultatif comme argument.
>>> from collections import deque >>> # 创建一个空的 deque >>> deque() deque([]) >>> # 使用不同的迭代器来创建 deque >>> deque((1, 2, 3, 4)) deque([1, 2, 3, 4]) >>> deque([1, 2, 3, 4]) deque([1, 2, 3, 4]) >>> deque(range(1, 5)) deque([1, 2, 3, 4]) >>> deque("abcd") deque(['a', 'b', 'c', 'd']) >>> numbers = {"one": 1, "two": 2, "three": 3, "four": 4} >>> deque(numbers.keys()) deque(['one', 'two', 'three', 'four']) >>> deque(numbers.values()) deque([1, 2, 3, 4]) >>> deque(numbers.items()) deque([('one', 1), ('two', 2), ('three', 3), ('four', 4)])
Si vous instanciez un deque sans fournir itérable comme paramètre, vous obtiendrez un deque vide. Si un itérable est fourni et saisi, le deque initialise une nouvelle instance avec ses données. L'initialisation se déroule de gauche à droite en utilisant deque.append().
L'initialiseur Deque nécessite les deux paramètres facultatifs suivants.
- iterable est un itérateur qui fournit des données d'initialisation.
- maxlen est un entier, spécifiant la longueur maximale de deque.
Comme mentionné précédemment, si vous ne fournissez pas d'itérable, vous obtiendrez un deque vide. Si vous fournissez une valeur pour maxlen, alors votre deque ne stockera que les éléments jusqu'à maxlen.
Enfin, vous pouvez également utiliser des objets itérables non ordonnés, tels que des collections, pour initialiser deque. Dans ces cas, il n’y aura pas d’ordre prédéfini des éléments dans le deque final.
Afficher et ajouter efficacement des éléments
La différence la plus importante entre Deque et List est que le premier peut effectuer des opérations d'ajout et d'affichage efficaces aux deux extrémités de la séquence. La classe Deque implémente les méthodes spécialisées .popleft() et .appendleft() pour opérer directement sur l'extrémité gauche de la séquence.
>>> from collections import deque >>> numbers = deque([1, 2, 3, 4]) >>> numbers.popleft() 1 >>> numbers.popleft() 2 >>> numbers deque([3, 4]) >>> numbers.appendleft(2) >>> numbers.appendleft(1) >>> numbers deque([1, 2, 3, 4])
Ici, utilisez .popleft() et .appendleft() pour apparaître et ajouter respectivement la valeur d'extrémité gauche des nombres. Ces méthodes sont conçues pour deque, et list n'a pas de telle méthode.
Deque fournit également des méthodes .append() et .pop() comme list pour opérer à l'extrémité droite de la séquence. Cependant, le comportement de .pop() est différent.
>>> from collections import deque >>> numbers = deque([1, 2, 3, 4]) >>> numbers.pop() 4 >>> numbers.pop(0) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: pop() takes no arguments (1 given)
Ici, .pop() supprime et renvoie le dernier élément du conteneur deque. Cette méthode n'accepte pas d'index comme paramètre, elle ne peut donc pas être utilisée pour supprimer des éléments arbitraires du deque. Vous ne pouvez l'utiliser que pour supprimer et renvoyer l'élément le plus à droite.
Nous pensons que deque est une liste doublement chaînée. Par conséquent, chaque élément d'un conteneur deque donné contient une référence (pointeur) vers l'élément précédent et suivant de la séquence.
Les listes chaînées doubles rendent l'opération d'ajout et d'extraction d'éléments des deux extrémités simple et efficace, car seuls les pointeurs doivent être mis à jour, par conséquent, les deux opérations ont des performances similaires, les deux sont O(1). Ils sont également prévisibles en termes de performances car il n'est pas nécessaire de réallouer de la mémoire ni de déplacer les éléments existants pour en accepter de nouveaux.
从常规 Python 列表的左端追加和弹出元素需要移动所有元素,这最终是一个 O(n) 操作。此外,将元素添加到列表的右端通常需要Python重新分配内存,并将当前项复制到新的内存位置,之后,它可以添加新项。这个过程需要更长的时间来完成,并且追加操作从 O(1)传递到 O(n)。
考虑以下关于在序列左端添加项的性能测试,deque vs list。
# time_append.py from collections import deque from time import perf_counter TIMES = 10_000 a_list = [] a_deque = deque() def average_time(func, times): total = 0.0 for i in range(times): start = perf_counter() func(i) total += (perf_counter() - start) * 1e9 return total / times list_time = average_time(lambda i: a_list.insert(0, i), TIMES) deque_time = average_time(lambda i: a_deque.appendleft(i), TIMES) gain = list_time / deque_time print(f"list.insert(){list_time:.6} ns") print(f"deque.appendleft() {deque_time:.6} ns({gain:.6}x faster)")
在这个脚本中,average_time() 计算了执行一个给定次数的函数(func)的平均时间。如果我们在命令行中运行该脚本,那么我们会得到以下输出。
$ python time_append.py list.insert()3735.08 ns deque.appendleft() 238.889 ns(15.6352x faster)
在这个例子中,deque 上的 .appendleft() 要比 list 上的 .insert() 快几倍。注意 deque.appendleft() 执行时间是常量O(1)。但列表左端的 list.insert() 执行时间取决于要处理的项的数量O(n)。
在这个例子中,如果增加 TIMES 的值,那么 list.insert() 会有更高的时间测量值,而 deque.appendleft() 会得到稳定(常数)的结果。如果对 deque 和 list 的 pop 操作进行类似的性能测试,那么可以展开下面的练习块。
Exercise:测试 deque.popleft() 与 list.pop(0) 的性能
可以将上面的脚本修改为时间deque.popleft()与list.pop(0)操作并估计它们的性能。
Solution:测试 deque.popleft() 与 list.pop(0) 的性能
# time_pop.py from collections import deque from time import perf_counter TIMES = 10_000 a_list = [1] * TIMES a_deque = deque(a_list) def average_time(func, times): total = 0.0 for _ in range(times): start = perf_counter() func() total += (perf_counter() - start) * 1e9 return total / times list_time = average_time(lambda: a_list.pop(0), TIMES) deque_time = average_time(lambda: a_deque.popleft(), TIMES) gain = list_time / deque_time print(f"list.pop(0) {list_time:.6} ns") print(f"deque.popleft() {deque_time:.6} ns({gain:.6}x faster)")
list.pop(0) 2002.08 ns deque.popleft() 326.454 ns(6.13282x faster) 同样,它deque比list从底层序列的左端删除元素要快。 尝试更改TIMES的值,看看会发生什么
Deque 数据类型的设计是为了保证在序列的两端进行有效的追加和弹出操作。它是处理需要在 Python 中实现队列和堆栈数据结构的问题的理想选择。
访问Deque中的任意元素
Python 的 deque 返回可变的序列,其工作方式与列表相当类似。除了可以有效地从其末端追加和弹出元素外,deque 还提供了一组类似列表的方法和其他类似序列的操作,以处理任意位置的元素。下面是其中的一些。
选项 | 描述 |
.insert(i, value) | 在索引为i的deque容器中插入一个名为value的元素。 |
.remove (value) | 删除第一个出现的 value ,如果 value 不存在则引发ValueError |
a_deque[i] | 从一个deque容器中检索索引为 i 的项。 |
del a_deque[i] | Supprime l'élément d'index i du conteneur deque. |
我们可以使用这些方法和技术来处理 deque 对象内部任何位置的元素。下面是如何做到这一点的。
>>> from collections import deque >>> letters = deque("abde") >>> letters.insert(2, "c") >>> letters deque(['a', 'b', 'c', 'd', 'e']) >>> letters.remove("d") >>> letters deque(['a', 'b', 'c', 'e']) >>> letters[1] 'b' >>> del letters[2] >>> letters deque(['a', 'b', 'e'])
在这里,首先将"c"插入到位置 2的letters中。然后使用 .remove() 从deque容器中移除"d"。Deque 还允许索引来访问元素,在这里使用它来访问索引1处的b。最后,你可以使用 del 关键字从 deque 中删除任何存在的项。请注意, .remove() 允许按值删除项,而del则按索引删除项。
尽管 deque 对象支持索引,但它们不支持切片,即不能像常规列表一样使用切片语法, [start:stop:step] 从现有的 deque 中提取:
>>> from collections import deque >>> numbers = deque([1, 2, 3, 4, 5]) >>> numbers[1:3] Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: sequence index must be integer, not 'slice'
Deque支持索引,却不支持分片。通常来说在一个链表上执行切片非常低效。
虽然 deque 与 list 非常相似,但 list 是基于数组的,而 deque 是基于双链表的。
Deque 基于双链表,在访问、插入和删除任意元素都是无效操作。如果需要执行这些操作,则解释器必须在deque中进行迭代,直到找到想要的元素。因而他们的时间复杂度是O(n)而不是O(1)。
下面演示了在处理任意元素时 deques 和 list 的行为。
# time_random_access.py from collections import deque from time import perf_counter TIMES = 10_000 a_list = [1] * TIMES a_deque = deque(a_list) def average_time(func, times): total = 0.0 for _ in range(times): start = perf_counter() func() total += (perf_counter() - start) * 1e6 return total / times def time_it(sequence): middle = len(sequence) // 2 sequence.insert(middle, "middle") sequence[middle] sequence.remove("middle") del sequence[middle] list_time = average_time(lambda: time_it(a_list), TIMES) deque_time = average_time(lambda: time_it(a_deque), TIMES) gain = deque_time / list_time print(f"list{list_time:.6} μs ({gain:.6}x faster)") print(f"deque {deque_time:.6} μs")
这个脚本对插入、删除和访问一个 deque 和一个 list 中间的元素进行计时。如果运行这个脚本,得到如下所示的输出:
$ python time_random_access.py list63.8658 μs (1.44517x faster) deque 92.2968 μs
Deque并不像列表那样是随机访问的数据结构。因此,从 deque 的中间访问元素的效率要比在列表上做同样的事情低。这说明 deque 并不总是比列表更有效率。
Python 的 deque 对序列两端的操作进行了优化,所以它们在这方面一直比 list 好。另一方面,列表更适合于随机访问和固定长度的操作。下面是 deque 和 list 在性能上的一些区别。
运作 | | | ||||||||||||||
通过索引访问任意的元素 | O(n) | O(1) | ||||||||||||||
在左端弹出和追加元素 | O(1) | |||||||||||||||
O (1) | O (1) + ré-affecté | |||||||||||||||
O(n) | O(n) |
Method | Support | |
| 长度的 | |
| 带有 | |
| 常规迭代 | |
| 反向迭代 | |
| ||
.__contains__() | 带有 |
.__reversed__()
🎜🎜.__repr__()
🎜🎜🎜🎜字符串表示形式🎜🎜🎜🎜🎜理想情况下,.__repr__()返回一个字符串,代表一个有效的 Python 表达式。可以用这个表达式以相同的值重新创建这个对象。
然而,在上面的例子中,目的是使用方法的返回值在 interactive shell 上优雅地显示对象。可以通过接受初始化可迭代对象作为.__init__() 的参数并从中构建实例,从而从这个特定的字符串表示形式构建 Queue 实例。
有了这些补充,Queue 类就完成了。要在我们的代码中使用这个类,我们可以做如下事情。
>>> from custom_queue import Queue >>> numbers = Queue() >>> numbers Queue([]) >>> # Enqueue items >>> for number in range(1, 5): ... numbers.enqueue(number) ... >>> numbers Queue([1, 2, 3, 4]) >>> # Support len() >>> len(numbers) 4 >>> # Support membership tests >>> 2 in numbers True >>> 10 in numbers False >>> # Normal iteration >>> for number in numbers: ... print(f"Number: {number}") ... 1 2 3 4
总结
队列和堆栈是编程中常用的 抽象数据类型。它们通常需要在底层数据结构的两端进行有效的 pop 和 append 操作。Python 的 collections 模块提供了一种叫做 deque 的数据类型,它是专门为两端的快速和节省内存的追加和弹出操作而设计的。
有了deque,我们可以用优雅、高效和Pythonic的方式在低层次上编写我们自己的队列和堆栈。
总结下本文所学内容:
- 如何在代码中创建和使用Python的deque
- 如何有效地从deque的两端追加和弹出项目
- 如何使用deque来构建高效的队列和堆栈
- 什么时候值得使用deque而不是list
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!

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Utiliser la plupart des éditeurs de texte pour ouvrir des fichiers XML; Si vous avez besoin d'un affichage d'arbre plus intuitif, vous pouvez utiliser un éditeur XML, tel que Oxygen XML Editor ou XMLSPY; Si vous traitez les données XML dans un programme, vous devez utiliser un langage de programmation (tel que Python) et des bibliothèques XML (telles que XML.ETREE.ElementTree) pour analyser.

Une application qui convertit le XML directement en PDF ne peut être trouvée car ce sont deux formats fondamentalement différents. XML est utilisé pour stocker des données, tandis que PDF est utilisé pour afficher des documents. Pour terminer la transformation, vous pouvez utiliser des langages de programmation et des bibliothèques telles que Python et ReportLab pour analyser les données XML et générer des documents PDF.

La vitesse du XML mobile à PDF dépend des facteurs suivants: la complexité de la structure XML. Méthode de conversion de configuration du matériel mobile (bibliothèque, algorithme) Méthodes d'optimisation de la qualité du code (sélectionnez des bibliothèques efficaces, optimiser les algorithmes, les données de cache et utiliser le multi-threading). Dans l'ensemble, il n'y a pas de réponse absolue et elle doit être optimisée en fonction de la situation spécifique.

Les outils de mise en forme XML peuvent taper le code en fonction des règles pour améliorer la lisibilité et la compréhension. Lors de la sélection d'un outil, faites attention aux capacités de personnalisation, en gérant des circonstances spéciales, des performances et de la facilité d'utilisation. Les types d'outils couramment utilisés incluent des outils en ligne, des plug-ins IDE et des outils de ligne de commande.

Il n'y a pas d'outil XML à PDF simple et direct sur mobile. Le processus de visualisation des données requis implique une compréhension et un rendu complexes des données, et la plupart des outils dits "gratuits" sur le marché ont une mauvaise expérience. Il est recommandé d'utiliser des outils côté informatique ou d'utiliser des services cloud, ou de développer vous-même des applications pour obtenir des effets de conversion plus fiables.

Convertir XML en PDF avec une qualité de haute qualité sur votre téléphone mobile nécessite: analyser le XML dans le cloud et générer des PDF à l'aide d'une plate-forme informatique sans serveur. Choisissez un analyseur XML efficace et une bibliothèque de génération PDF. Gérer correctement les erreurs. Faites une utilisation complète de la puissance de cloud computing pour éviter les tâches lourdes sur votre téléphone. Ajustez la complexité en fonction des exigences, notamment le traitement des structures XML complexes, la génération de PDF de plusieurs pages et l'ajout d'images. Imprimez les informations du journal pour aider à déboguer. Optimiser les performances, sélectionner des analyseurs efficaces et des bibliothèques PDF et peut utiliser une programmation asynchrone ou des données XML prétraitées. Assurez-vous une bonne qualité de code et maintenabilité.

Il est impossible de terminer la conversion XML à PDF directement sur votre téléphone avec une seule application. Il est nécessaire d'utiliser les services cloud, qui peuvent être réalisés via deux étapes: 1. Convertir XML en PDF dans le cloud, 2. Accédez ou téléchargez le fichier PDF converti sur le téléphone mobile.

Il n'est pas facile de convertir XML en PDF directement sur votre téléphone, mais il peut être réalisé à l'aide des services cloud. Il est recommandé d'utiliser une application mobile légère pour télécharger des fichiers XML et recevoir des PDF générés, et de les convertir avec des API Cloud. Les API Cloud utilisent des services informatiques sans serveur et le choix de la bonne plate-forme est crucial. La complexité, la gestion des erreurs, la sécurité et les stratégies d'optimisation doivent être prises en compte lors de la gestion de l'analyse XML et de la génération de PDF. L'ensemble du processus nécessite que l'application frontale et l'API back-end fonctionnent ensemble, et il nécessite une certaine compréhension d'une variété de technologies.
