競プロでちょいハマったPythonのスタックとキューについて - 5月 27, 2018 こんにちは、ぐぐりら(@guglilac)です。 ## 前置き この前の記事で書いたように、先日競技プログラミングを始めました。 僕はC++はかけないので、とりあえず一番手に馴染んでいるPythonを使って解いています。 競技プログラミングでは基本のデータ構造のスタックとキューについて、とりあえずリストを使って書いてみたら少しハマってしまいました。 Pythonには便利な機能がたくさんありますが、内部のアルゴリズムまで把握して使わないと計算時間を大きく消費してしまいますね。 ## ハマった内容 Pythonではリストがスタックとキューの代わりになります。 制限時間がそんなにタイトじゃなければこれでいいはず。 ```python:stack.py stack=[1,2,3,4] #push stack.append(5) #stack=[1,2,3,4,5] #pop stack.pop() #stack=[1,2,3,4] ``` ```python:queue.py queue=[1,2,3,4] #enqueue queue.append(5) #queue=[1,2,3,4,5] #dequeue queue.pop(0) #queue=[1,2,3,4] ``` このうち、`append(5)`と`pop()`はO(1)だけれど、`pop(0)`はO(n)(先頭の要素を削除した後、配列を一つずつ前にずらしている) なので、計算量が大きくなってしまいます。 このように、pythonのリストを使ってスタックとキューを作ると、スタックは問題ないが、キューの方は遅くなってしまう恐れがあります。 おとなしく、`collections.deque`をつかうと安全。 ```python:deque.py from collections import deque L=deque([1,2,3,4]) #push,enqueue L.append(5)#[1,2,3,4,5] #pop L.pop()#[1,2,3,4] #dequeue L.popleft()#[2,3,4] ``` ## まとめ * 内部のアルゴリズムも理解して正しく使おう! * 不安な時はライブラリを使おう! この記事をシェアする Twitter Facebook Google+ B!はてブ Pocket Feedly コメント
コメント
コメントを投稿