Dans la question D de "At Coder Beginner Contest 158" qui s'est tenue l'autre jour, une bonne question a été posée lors de l'utilisation de deque, donc je voudrais résumer comment l'utiliser en Python.
D - String Formation https://atcoder.jp/contests/abc158/tasks/abc158_d
Un type de type de données de conteneur Python. Les données peuvent être ajoutées au prix de O (1) pour le début et la fin. S'il s'agit d'une liste normale, elle peut être implémentée au prix de O (n) lors de l'ajout au début.
Ceci est utile lorsque vous souhaitez ajouter des données non seulement à la fin, mais également au début.
Utilisez la méthode "append" comme vous le feriez pour une liste.
Utilisez la méthode «ajouter à gauche». List utilise la méthode "insérer".
from collections import deque
d = deque('a')
d.append('b')
d.appendleft('c')
print(d)
# -> deque(['c', 'a', 'b'])
print(''.join(d))
# -> cab
Faites une copie superficielle du deque. Voir ci-dessous pour les copies superficielles.
copie --- Copie superficielle et opérations de copie profonde https://docs.python.org/ja/3/library/copy.html
from collections import deque
d1 = deque([1, 2, 3, 4, 5])
d2 = d1.copy()
print(d1)
# -> deque([1, 2, 3, 4, 5])
print(d2)
# -> deque([1, 2, 3, 4, 5])
d1.append(6)
print(d1)
# -> deque([1, 2, 3, 4, 5, 6])
print(d2)
# -> deque([1, 2, 3, 4, 5])
Comptez le nombre de valeurs égales aux arguments dans deque.
Renvoie la position d'une valeur égale à l'argument dans deque. S'il n'est pas trouvé, déclenchez une ValueError.
Supprime l'élément à droite de pop: deque et le renvoie. Supprime l'élément sur le côté gauche de popleft: deque et le renvoie.
Supprimez la première valeur égale à l'argument de deque. S'il n'est pas trouvé, déclenchez une ValueError.
Inversez l'ordre des éléments dans deque.
from collections import deque
d = deque([1, 2, 3, 4, 5])
d.insert(2, 5)
print(d)
# -> deque([1, 2, 5, 3, 4, 5])
print(d.count(5))
# -> 2
print(d.index(2))
# -> 1
print(d.index(5))
# -> 2
print(d.index(5, 4, 6))
# -> 5
print(d.pop())
# -> 5
print(d)
# -> deque([1, 2, 5, 3, 4])
print(d.popleft())
# -> 1
print(d)
# -> deque([2, 5, 3, 4])
d.remove(5)
print(d)
# -> deque([2, 3, 4])
d.reverse()
print(d)
# -> deque([4, 3, 2])
Ajoutez un élément interactif à droite.
Ajoutez un élément interactif à gauche.
Déplace l'élément vers la droite de la valeur de l'argument. Les éléments au-delà de la fin se déplacent vers le début. Si vous spécifiez un nombre négatif, il se déplace vers la gauche.
from collections import deque
d = deque([1, 2, 3, 4, 5])
li = [6,7,8,9]
d.extend(li)
print(d)
# -> deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
d.extendleft(li)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.rotate(1)
print(d)
# -> deque([9, 9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8])
d.rotate(-1)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])
d.clear()
print(d)
# -> deque([])
Spécifiez le nombre maximum d'éléments de deque. Si vous ajoutez plus que le nombre maximum d'éléments, l'élément du côté opposé sera supprimé.
from collections import deque
li = [1, 2, 3, 4, 5]
d = deque(li, 3)
print(d)
# ->deque([3, 4, 5], maxlen=3)
d2 = deque([], 3)
for i in range(10):
d2.append(i)
print(d2)
# -> deque([7, 8, 9], maxlen=3)
(Je le fais avec le sentiment de l'essayer) La performance a été comparée en ajoutant simplement la valeur à droite si elle était paire et à gauche si elle était impaire 1 000 000 fois. La liste était d'environ 147 secondes et deque était d'environ 0,3 seconde.
from collections import deque
import time
start = time.time()
li = []
for i in range(1000000):
if i % 2 == 0:
li.append(i)
else:
li.insert(0, i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 147.49888038635254
start = time.time()
d = deque([])
for i in range(1000000):
if i % 2 == 0:
d.append(i)
else:
d.appendleft(i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 0.3092050552368164
Je ne connaissais pas le deque du concours, j'ai donc créé une liste avec deux fois le nombre maximum d'éléments et ajouté le premier élément au milieu pour y faire face. Je pense que ce serait plus facile à résoudre si je connaissais deque, donc je voulais bien apprendre la structure des données.
Même si je comprends la quantité de calcul, je pensais qu'il n'y aurait aucune différence lors de la comparaison des temps de traitement.
collections --- Type de données de conteneur https://docs.python.org/ja/3/library/collections.html#collections.deque
Type de données collections.deque qui peut être utilisé comme "file d'attente des deux extrémités" en Python https://kakakakakku.hatenablog.com/entry/2019/01/04/214907
[Python] Mesure et affiche le temps nécessaire au traitement https://qiita.com/fantm21/items/3dc7fbf4e935311488bc
Recommended Posts