Data Structures

これまでもちょこちょこ出てきていたデータ型に関して勉強していきます。

More on Lists

リスト操作についてです。

API名	説明
append(x)	リストの末尾にxを追加
extend(L)	リストの末尾にL(リスト)を追加
insert(i, x)	リストのi番目にxを挿入
remove(x)	最初に現れるxを削除する
pop([i])	リストのi番目の要素を削除して返す、引数を省略したら最後の要素
index(x)	最初に現れるxのインデックスを取得
count(x)	リスト内にいくつxがあるか取得
sort()	リストをソートする (昇順)
reverse()	リストの要素を逆転する

実際に使ってみます。

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.25), a.count('x')  # 要素の数をカウント
2 1 0
>>> a.insert(2, -1)  # 要素を挿入
>>> a.append(333)  # 要素を末尾に追加
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)  # 要素の位置を取得
1
>>> a.remove(333)  # 要素を削除 (最初に現れた要素だけ)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()  # 要素を逆転
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.sort()  # 要素を昇順ソート
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]
>> a.pop()  # 末尾の要素を削除して取得
1234.5
>>> a
[-1, 1, 66.25, 333, 333]
>>> a.extend([1, 2, 3])  # 末尾にリスト内の要素を追加
>>> a
[-1, 1, 66.25, 333, 333, 1, 2, 3]

Using Lists as Stacks

Pythonのリストは特別なことをしなくてもスタックとして使えます。

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

popはそのままpop()を使います。pushはappend()を使います。

Using Lists as Queues

このリストをQueueとして使うのはあまり得策ではありません。リストはlast-in, first-outに特化しているため、first-in, first-outをやろうとすると効率が悪いのです。なので、collections.dequeというデータ型でリストをラップします。collections.dequeは先頭、末尾へのappend、pop操作が得意なのです (速い)。

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")
>>> queue.append("Graham")
>>> queue.popleft()
'Eric'
>>> queue.popleft()
'John'
>>> queue
deque(['Michael', 'Terry', 'Graham'])

popleft()がキューからのpop操作に当たります。

Functional Programming Tools

関数プログラミングでよく見かける (Haskellでも！) 関数を見ていきます。まずはfilter(function, sequence)から。これはsequenceリストの中でfunction(item)がTrueを返すもののみを集めてリストにしてくれる関数です。

>>> def f(x):
...     return x % 2 != 0 and x % 3 != 0
... 
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]

2と3で割り切れない数をフィルタする関数fを定義して、これを使って2〜24のリストをフィルタしています。

次にmap関数。これもよく見かけますね。

>>> def cube(x): return x * x * x
... 
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

map関数は関数 (第一引数) をリストの各要素に適用します。その結果を集めてリストを作ります。また複数のリストに対しても適用可能です。

>>> seq = range(8)
>>> seq
[0, 1, 2, 3, 4, 5, 6, 7]
>>> def add(x, y):
...     return x + y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]

もちろん関数はリストの数分引数が必要です。

次はreduce(function, sequence)関数です。まずは使い方を見てみます。

>>> def add(x, y):
...     return x + y
...
>>> reduce(add, range(1, 11))
55

何となく分かりますかね。第二引数のリストの先頭要素と次の要素に対してfunctionを適用します。次にその結果と次の要素に対してfunctionを適用…を繰り返します。

最初だけ二つの要素を足しているのが若干気持ち悪いと思った方、私もそうです。reduce関数には第三引数が指定出来、これが初期値になります。初期値がある場合は、最初に初期値とリストの先頭要素に対してfunctionを適用して、次にその結果と次の要素に対してfunctionが適用され…というようにすっきりします。

>>> def add(x, y):
...     return x + y
...
>>> reduce(add, range(1, 11))       # 1から10までを足す。初期値がないので最初は0番目と1番目を足す。
55
>>> reduce(add, [])                 # 初期値がないので何を返せばよいのか分からず例外発生
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: reduce() of empty sequence with no initial value
>>> reduce(add, range(1, 11), 0)    # 初期値があるので最初は初期値と0番目を足す
55
>>> reduce(add, [], 0)              # 初期値があるので初期値を返す
0

List Comprehensions

こちらはリストの中に式を入れてリストを自動生成する方法です。こういうの初めてです。

>>> freshfruit = ['  banana', '   loganberry   ', 'passion fruit   ']
>>> [weapon.strip() for weapon in freshfruit]        # 各要素の前後スペースを削除
['banana', 'loganberry', 'passion fruit']
>>> vec = [2, 4, 6]
>>> [3 * x for x in vec]                             # 各要素を三倍
[6, 12, 18]
>>> [3 * x for x in vec if x > 3]                    # 3より大きい要素だけをピックアップして三倍
[12, 18]
>>> [3 * x for x in vec if x < 2]                    # 2より小さい要素だけをピックアップして三倍
[]                                                   # ⇒ そんな要素はないので結果は[]
>>> [[x, x**2] for x in vec]                         # [各要素, 各要素の二乗]のリストでリストを作成
[[2, 4], [4, 16], [6, 36]]
>>> [(x, x**2) for x in vec]                         # (各要素, 各要素の二乗)のタプルでリストを作成
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x * y for x in vec1 for y in vec2]              # vec1, vec2の各要素を総当たりで掛ける
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x + y for x in vec1 for y in vec2]              # vec1, vec2の各要素を総当たりで足す
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec[i] * vec2[i] for i in range(len(vec1))]     # vec1, vec2の各要素を掛ける
[8, 12, -54]

結構柔軟で自由度が高そうです。mapやreduceを多用するのであれば、こちらの方が分かりやすいように感じます。でも次のようにネストするとよく分からなくなってきます。

>>> mat = [
...     [1, 2, 3],
...     [4, 5, 6],
...     [7, 8, 9]
...     ]
>>>
>>> print [[row[i] for row in mat] for i in [0, 1, 2]]
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

ネストしたリスト内表記は左から右に読んでいくと分かりやすいです。

for i in [0, 1, 2]:
    for row in mat:
        print row[i]

ちなみにこのように行列の行と列を逆転するには次の組み込み関数を使った方が楽です。

>>> zip(*mat)
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

これは*matでリストを展開しています。つまり三つのリストに展開されます。各リストの同じ添字の要素を集めてタプルを作ります。これをまとめてリストにしているわけです。

The del statement

delという構文 (？) ですが、何だか私にはちょっと違和感を感じる構文です。delは園なの通り削除 (delete) です。

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]

まずはリストの先頭を削除します。pop()と似たような感じですが、次からが違います。

>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

なるほど、リストの中のリスト (slices) を削除出来るわけですね。さらにこんなことが起きます。

>>> del a
>>> a
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'a' is not defined

リストを格納していた変数 (オブジェクトへの参照ラベル) すらも削除出来てしまうのです。そうなるともうアクセスすることはで来ません。う〜ん、あんまり使わないかなぁ。