In der D-Frage von "At Coder Beginner Contest 158", die neulich stattfand, wurde eine gute Frage gestellt, wenn deque verwendet wird, daher möchte ich zusammenfassen, wie man es in Python verwendet.
D - String Formation https://atcoder.jp/contests/abc158/tasks/abc158_d
Ein Typ des Python-Container-Datentyps. Daten können auf Kosten von O (1) sowohl für den Anfang als auch für das Ende hinzugefügt werden. Wenn es sich um eine normale Liste handelt, kann sie auf Kosten von O (n) implementiert werden, wenn sie am Anfang hinzugefügt wird.
Dies ist nützlich, wenn Sie Daten nicht nur am Ende, sondern auch am Anfang hinzufügen möchten.
Verwenden Sie die Methode "Anhängen" wie eine Liste.
Verwenden Sie die Methode "Links anhängen". List verwendet die Methode "insert".
from collections import deque
d = deque('a')
d.append('b')
d.appendleft('c')
print(d)
# -> deque(['c', 'a', 'b'])
print(''.join(d))
# -> cab
Machen Sie eine flache Kopie der Deque. Siehe unten für flache Kopien.
Kopieren --- Flache Kopier- und Tiefkopiervorgänge 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])
Zählen Sie die Anzahl der Werte, die den Argumenten in deque entsprechen.
Gibt die Position eines Werts zurück, der dem Argument in deque entspricht. Wenn nicht gefunden, lösen Sie einen ValueError aus.
Löscht das Element rechts von pop: deque und gibt es zurück. Löscht das Element auf der linken Seite von popleft: deque und gibt es zurück.
Entfernen Sie den ersten Wert, der dem Argument in deque entspricht. Wenn nicht gefunden, lösen Sie einen ValueError aus.
Kehren Sie die Reihenfolge der Elemente in deque um.
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])
Fügen Sie rechts ein interaktives Element hinzu.
Fügen Sie links ein interaktives Element hinzu.
Verschiebt das Element um den Wert des Arguments nach rechts. Elemente jenseits des Endes bewegen sich zum Anfang. Wenn Sie eine negative Zahl angeben, wird diese nach links verschoben.
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([])
Geben Sie die maximale Anzahl von Deque-Elementen an. Wenn Sie mehr als die maximale Anzahl von Elementen hinzufügen, wird das Element auf der gegenüberliegenden Seite gelöscht.
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)
(Ich mache es mit dem Gefühl, es zu versuchen) Die Leistung wurde verglichen, indem einfach der Wert rechts addiert wurde, wenn er gerade war, und links, wenn er 1.000.000 Mal ungerade war. Die Liste war ungefähr 147 Sekunden und die Deque war ungefähr 0,3 Sekunden.
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
Ich kannte die Deque im Wettbewerb nicht, also habe ich eine Liste mit der doppelten maximalen Anzahl von Elementen erstellt und das erste Element in der Mitte hinzugefügt, um damit umzugehen. Ich denke, es wäre einfacher zu lösen, wenn ich deque kennen würde, also wollte ich die Datenstruktur gut lernen.
Selbst wenn ich den Rechenaufwand verstehe, dachte ich, dass es keinen Unterschied geben würde, wenn man die Verarbeitungszeiten tatsächlich vergleicht.
Sammlungen --- Container-Datentyp https://docs.python.org/ja/3/library/collections.html#collections.deque
Datentyp collection.deque, der in Python als "Warteschlange für beide Enden" verwendet werden kann https://kakakakakku.hatenablog.com/entry/2019/01/04/214907
[Python] Misst und zeigt die für die Verarbeitung erforderliche Zeit an https://qiita.com/fantm21/items/3dc7fbf4e935311488bc
Recommended Posts