標準ライブラリ
ここでちょっと問題はひとやすみ
標準ライブラリでスタック、キュー、ベクタ、リストを使う方法が解説されてます
Pythonではどうなるのかな
スタック
C++のSTLにはsize、top、push、pop、emptyといった関数が
含まれている模様
サンプルを見ると、popは削除のみで値を取り出すのはtopを使えってことかな
何ていうんだっけ
関数は副作用なしで値を返すだけ、副作用はコマンドでコマンドは値を返さない、みたいなの
ググったらPythonチュートリアルで早速紹介されてるようだ
ということは逆に言うとStackクラスみたいなのはないってことだなきっと
スタックの一番上に要素を追加するには append() を使います。スタックの一番上から要素を取り出すには pop() をインデクスを指定せずに使います。
5.1.1. リストをスタックとして使う
あれ
考えてみたらappendって末尾にくっつけるやつだよな
普通のリストだとO(n)になってしまうよな
Pythonでリストって言ってるやつは双方向リストなのかな
・・・
ただの配列だった
そうだったか
確認してなかった
そりゃ末尾に追加だな
わざわざクラスで書くとこうかな
class Stack():
def __init__(self):
self.s = []
def top(self):
return self.s[-1]
def size(self):
return len(self.s)
def push(self, x):
self.s.append(x)
def pop(self):
return self.s.pop()
def empty(self):
return len(self.s) == 0もう一度調べてみたら双方向キューを実装したcollections.dequeっていうのがある
といってもスタックとして使うだけなら配列で十分
from collections import dequeして
self.s = []をself.s = deque()にするだけで動くことは動く
キュー
キューのクラスは書いたけどcollections.dequeで書き直してみよう
append、appendleft、pop、popleftとあって先頭も末尾も
自由にできるけど、左か右か、どっちを先頭とするべきかな
$ python3
>>> from collections import deque
>>> q = deque([1,2,3])
>>> q
deque([1, 2, 3])
>>> q.popleft()
1appendとpopleftを使うのが素直そうな感じ
class Queue():
def __init__(self):
self.q = deque()
def size(self):
return len(self.q)
def front(self):
return self.q[0]
def push(self, x):
self.q.append(x)
def pop(self):
return self.q.popleft()
def empty(self):
return len(self.q) == 0Pythonのグローバル変数は遅いらしい
最後の決め手はメインルーチンを_main関数にしたってとこなんだけど そんなんで速くなるの？
ALDS1_3_C: Doubly Linked List - kb84tkhrのブログ
詳しい人に聞いてみたところ、ローカル変数の方が速いよ、とのこと
たしかにmainに入れる前はグローバル変数だった
そういうことかなるほど
『失敗図鑑』
こんなムスメに「失敗しても大丈夫」と思わせるにはどうしたらいいか、と考える日々
で、育て方だったのか遺伝なのか、ウチの娘もそっくり同じ 勉強にしろ遊びにしろ、ちょっと難しいかも、と思うと手を付けようとしません あーここは自分に似たな、難しいことにも挑戦してほしいな、と思って 「失敗してもいいんだよ」くらいは言ってあげるんですが それくらいでは決心がゆらぐことはありません
失敗してみせる - kb84tkhrのブログ
そこへ『失敗図鑑』入りました、という連絡が図書館から届きました
ジャンルを指定して図書館から通知が届くように設定しています
便利な世の中になりました
