Python個人的メモその2：データ構造編～あなたの目的に狙いを決めて～

はじめに

Python個人的メモその1：入力編～標準入力とファイルからの入力～では最も重要となる入力を扱いました．
では，その次に重要なものとは?
出力ですかね? いやいやデータ構造の方が重要でしょうが！！！！(出力は後にまとめます)

ここでいうデータ構造とは，リストやdictなど，複数の値を一括で管理するようなものを指します．

リスト

最もオーソドックスなデータ構造と言えるでしょう．他の言語で言うと「要素数可変な配列」といったところです．
初期化は，[]かlist()です．どっちでもよいですがlist()の方がパッと見て分かりやすいようなそうでもないような気がします．
複数の値が連続して入っており，0からカウントを始め，頭からi番目の要素はリスト名[i]でアクセスします．
後ろに要素を追加したい時はリスト名.append(新要素)とします．要素数はlen(配列名)です．

list_sample

l = [1,2,3,4]
print(l[2])  #3
l.append(5)
print(l)  #[1,2,3,4,5]
print(len(l))  #5

やらない方がいいこと

低速なのでやらない方がいいことがあります．

リスト同士の連結をforとappendでやる

リスト名.extend(追加したいリスト)があるのでこちらを使いましょう．

extend_list

l1=[1,2,3]
l2=[4,5,6]
l3=[7,8,9]
#NG
for val in l2:
    l1.append(val)
print(l1)  #[1,2,3,4,5,6]

#OK
l1.extend(l3)
print(l1)  #[1,2,3,4,5,6,7,8,9]

先頭にアクセスして何かやる

一番後方に何か操作を加えるのは問題ないのですが，先頭に対してそれをやるのはあまりにも遅すぎるのでやらない方がいいです．
例：先頭への挿入(リスト名.insert(入れる場所, 入れる要素))

access_left

l=[1,2,3]
#先頭への挿入だがこれはとても遅い
for i in range(100000):
    l.insert(0,'3')

ある要素がリスト内に存在するか確認する

線形探索(O(n))なので遅いです．
後述するsetや辞書型においてはO(1)で行えるため絶対にそちらでやるべきです．

check_existence

l=[1,2,3,4]
print(3 in l)  #True

deque

リストとほぼ同じ扱い方をしますが，こちらは先頭からの取り出し・削除を高速にできます．
つまり，両端から追加・削除が必要な場合に使います．
また，初期化時にmaxlenを用いると，保持する要素数を制限でき，新たに要素を追加し制限を超過した際，追加した側とは反対側の要素から順に勝手に削除してくれます．

deque_sample

from collections import deque
d=deque(maxlen=2)
#右側追加
d.append(3)
#左側追加
d.appendleft(5)

print(d)  #deque([5,3])
d.append(7)
print(d)  #deque([3,7])　右から入れたので左端が押し出された

left = d.popleft()
print(left)  #3

便利なdequeですが dequeに対して直接はスライスが出来ない ので注意．
最も簡単な解決法は，listに包んでやることですかね．
スライス後のリストをdequeとして扱いたい場合はさらにdequeで包みます．

deque_slice

dq=deque([1,2,3,4,5])
print(list(dq)[1:3])  #[2,3]
left = deque(list(dq)[1:3]).popleft()
print(left)  #2

heapq

ソート用の値「キー」と保存しておきたいデータをセットで入れておきます．
内部ではヒープ構造(今回は説明を省きます)によって常に最小のキーを持つデータが先頭に来るようになっているので，popでいつでも最小値を取り出せます．しかしそれ以外のデータの順序は不明なので注意が必要．

heapq_sample

import heapq                        
hq = []
key = h(x) #キーはソートに用いるので整数がオーソドックスかと                             
heapq.heappush(hq, (key, x))     
min_key, y = heapq.heappop(hq)#キー，データの順            

defaultdict

アクセス用のキーと，それに対応するデータをセットで入れておける構造です．
例えば，人の名前をキー，その人の電話番号を値としてphone_numという名前で管理しておくと，
Aさんの電話番号を知りたいときphone_num["A"]でアクセスできるわけです．
ここまではdictという機能でもできますが，dictは都度キーに対して初期化が必要になります．存在しないキーに対するアクセスはエラーになります．つまり，Bさんの電話番号を登録していない(Bというキーが存在していない)のに
phone_num["B"]にアクセスしてはいけないのです．
defaultdictでは初期化処理を予め決めておくことで，これを防ぐことができます．
例えばデータの型をstrとしてdefaultdictを用いるのであればこのようになります．

defaultdict_sample

from collections import defaultdict
dd=defaultdict(str)
dd["aaa"] = "rrr"
#とりあえず存在するキーに対してアクセス
dd["aaa"] += "444"
print(dd["aaa"]) #"rrr444"

#存在しないキーにアクセス 
dd["eee"] += "111"
print(dd["eee"]) # "111"

#ちなみにキーの削除は以下
del dd["eee"]
print(dd["eee"]) # ""

ちなみにデータを入れた順序は保証されません．

set(集合)

set型という，集合を取り扱える型があります．
例えばA,Bという集合に対する和(AまたはBに属する)，差(Aに属するがBに属さない)，積(AにもBにも属する)や，
片方が片方の部分集合か，などの演算ができます．
また，リストとは異なり要素は重複しません．つまり，同じ要素が2つ以上存在する場合，1つを除いて勝手に削除します．
さらに，データを入れた順序は保証されません．
データは変更可能ですが変更不能のものがいい場合，frozensetという型もあります．

set_sample

s={}#set()でも可
s.add(3)
s.add(3)
s.add(2)
s.add(5)
print(s)  #{2,3,5}
#積集合
print(s & {1,3})  #{3} 
#削除
s.remove(3)
print(s)  #{2,5}
#すべて削除
s.clear()

要素が重複しないという特徴を使って，入力文字列中に使われている文字の種類をソート済みリストとして抽出することができます．

set_sorted

#sortedはソート済みのリストを返す
print(sorted(set('hello, world')))  #[' ', ',', 'd', 'e', 'h', 'l', 'o', 'r', 'w']

また，前述したように要素の検索(ex. a in b)がリストよりも高速です．もちろん辞書も同程度に速いですがリスト→setは[]を{}に変えるだけなのでやりやすいのはこちらかと．

おわりに

よく使うPythonのデータ構造はこのあたりかな，という感じです．
あとは木構造とかグラフ構造がデフォルトであればなあと使ってて思います．
一応ライブラリはありますが，自分で実装しなければいけない場面は多々あると思うので省略します．