5. データ構造

この章では既に学んだことのいくつかをより詳しく説明するとともに、 いくつか新しいことを追加する。

 
5.1 もっとリストについて

リストというデータ型には、もういくつかのメソッドがある。 以下にリストオブジェクトのすべてのメソッドを挙げておく。

append( x)
項目をリストの末尾に追加する。 a[len(a):] = [x] と等価。

extend( L)
与えられたリストの項目すべての追加によってリストを拡張する。 a[len(a):] = L と等価。

insert( i, x)
与えられた位置に項目を挿入する。 第1引数を添字としてその前に項目を挿入する。 したがって a.insert(0, x) はリストの先頭に挿入する。 そして a.insert(len(a), x)a.append(x) と等価。

remove( x)
x を値とする最初の項目をリストから削除する。 該当する項目がなければエラーとなる。

pop( [i])
与えられた位置にある項目をリストから削除し、その項目を戻り値とする。 もし添字が指定されていなければ、 a.pop() はリスト末尾の項目をリストから削除し、その項目を戻り値とする。 (メソッドシグニチャ (method signature) 中の i を囲む角括弧は引数 が任意である事を示し、この位置に角括弧を記述する必要はない。 この表記は Python Library Reference の中で頻繁に利用される。)

index( x)
x を値とする最初の項目の、リストでの添字を返す。 該当する項目がなければエラーとなる。

count( x)
リストでの x の出現回数を返す。

sort( )
リストの項目を、その場で (in place)、ソートする。

reverse( )
リストの要素を、その場で、逆順にする。

以下はリストのメソッドの大半を使った例だ。

>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]

 
5.1.1 リストをスタックとして使う

リストメソッドは、 リストをスタック (stack) として使うことを非常に容易にしている。 スタックでは、 最後に追加された要素が最初に取り出される (``last-in, first-out'')。 スタックのトップに項目を追加するには append() を使う。 スタックのトップから項目を取り出すには pop() を添字指定なしで使う。 例えば、

>>> 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]

 
5.1.2 リストをキューとして使う

リストをキュー (queue) として使うことも手軽にできる。 キューでは、 最初に追加された要素が最初に取り出される (``first-in, first-out'')。 キューの末尾に項目を追加するには append() を使う。 キューの先頭から項目を取り出すには pop()0 を添字として 使う。例えば、

>>> queue = ["Eric", "John", "Michael"]
>>> queue.append("Terry")           # Terry が到着 (arrive) する
>>> queue.append("Graham")          # Graham が到着する
>>> queue.pop(0)
'Eric'
>>> queue.pop(0)
'John'
>>> queue
['Michael', 'Terry', 'Graham']

 
5.1.3 関数型プログラミングの道具

filter()map()reduce() という リストで使うと非常に便利な三つの組込み関数がある。

"filter(関数, シーケンス)" は、 シーケンスから 関数(項目) が真である項目を選んで、 それらからなる (なるべくシーケンスと同じ型の) シーケンスを返す。 たとえば、いくつかの素数を計算するには、

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

"map(関数, シーケンス)" は、 シーケンスの各項目について 関数(項目) を呼び出し、 その戻り値からなるリストを返す。 たとえば、いくつかの3乗数を計算するには、

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

2個以上のシーケンスを渡してもよい。関数はシーケンスと同じ個数の引数をとる必要がある。 各シーケンスからの対応する項目 (あるシーケンスがほかよりも短いときは、 項目のかわりに None) を引数として関数を呼び出す。 関数のかわりに None を渡すと、引数をそのまま返す関数に置き換えられる。

これら二つの特別な場合を組み合わせると、 "map(None, list1, list2)" は リストのペアを、ペアのリストにする手軽な方法であることが分かる。 たとえば、

>>> seq = range(8)
>>> def square(x): return x*x
...
>>> map(None, seq, map(square, seq))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]

"reduce(関数, シーケンス)" は、 2引数の関数を、まずシーケンスの最初の2項目について呼び出し、 それからその結果とシーケンスの次の項目について呼び出し、等々として構成された 単一の値を返す。 たとえば 1 から 10 までの数の総和を計算するには、

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

シーケンスに項目が1個だけなら、その値が返される。 シーケンスが空なら、例外が発生する。

第3引数を渡して開始値を指定する事ができる。 この場合、シーケンスが空ならば開始値が返され、そうでなければ、 関数を、まず開始値とシーケンスの先頭項目に適用し、 それからその結果と次の項目に適用し、等々となる。たとえば、

>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
... 
>>> sum(range(1, 11))
55
>>> sum([])
0

この例の様に sum() の定義をしないように。数の合計は共通に必 要なので、内蔵の関数 sum(sequence) が提供され、上記の例と 同様の動作をする。 New in version 2.3.

5.1.4 リストの内包表記

リストの内包表記 (list comprehension) は、 map()filter()lambda の使用に 頼らずにリストを造る簡潔な方法を用意している。 結果として得られるリスト定義は、 それらの構文要素を使って組み立てたリストよりも、しばしば明快になる傾向がある。 リストの内包表記の内容は、1個の式の後に1個の for 節が続き、 そしてその後にゼロ個以上の for 節または if 節が続いている ものだ。 結果は、その式を後に続く for節と if 節の文脈で 評価して得られる値のリストになる。 タプルへと評価される式を書きたければ、丸かっこで囲まなければならない。

>>> 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]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec]  # エラー - タプルには丸かっこが必要
  File "<stdin>", line 1, in ?
    [x, x**2 for x in vec]
               ^
SyntaxError: invalid syntax
>>> [(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]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

リストの内包表記を for ループの動作に一致させるために、ルー プ変数への割当ては内包表記の外部に可視のまま残る。

>>> x = 100                     # これが上書きされる
>>> [x**3 for x in range(5)]
[0, 1, 8, 27, 64]
>>> x                           # range(5)の最後の値
4

 
5.2 del

リストから項目を、値ではなく添字で指定して削除する方法がある。 それが del 文だ。 この文はリストからのスライスの削除にも使える (これは 以前はスライスへの空リストの代入でおこなわれていた)。 たとえば、

>>> a = [-1, 1, 66.6, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]

del は変数そのものの削除にも使える。

>>> del a

名前 a を参照することは、 これ以降 (少なくともほかの値をそれに代入するまでは) エラーになる。 del のほかの使用方法については、また後で説明する事にする。

 
5.3 タプルとシーケンス

リストと文字列には添字付けやスライス演算などの多くの共通の性質 があることを見てきた。 これらはシーケンス (sequence) データ型の二つの例だ。 Python は発展途上の言語なので、 ほかのシーケンスデータ型が追加されることもあるかもしれない。 標準的なシーケンスデータ型はもう一つある。 それがタプル (tuple) だ。

タプルはコンマで区切られたいくつかの値からなる。たとえば、

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

上記のように、入れ子のタプルを正しく解釈できるようにするため、 出力時にはタプルはいつも丸かっこで囲まれる。 入力時には丸かっこで囲んでも、囲まなくても良いが、 (もしもタプルがより大きな式の一部なら) どのみち 丸かっこが必要になる場合がしばしばだ。

タプルには、例えば (x, y) 座標対や、データベースからの従業員レコードな どの多くの用途がある。 タプルは、文字列と同じく、変化不可能 (immutable) だ。 つまり、タプルの個々の項目へ代入することはできない (ただし、 スライスと連結を使って同様の結果を得る事ができる)。 リストなどの、変化可能 (mutable) なオブジェクトを含んだタプルを造ることも できる。

0 個または 1 個の項目からなるタプルの構築は特殊な問題になるが、 これを解決するため、構文に特別な小細工がある。 空タプルは、空の丸かっこのペアで構築される。 1項目のタプルは、1個の値の後にコンマを続けることで 構築できる (単一の値を丸かっこで囲むことでは出来ない)。 美しくはないが、効果的だ。 たとえば、

>>> empty = ()
>>> singleton = 'hello',    # <-- 末尾のコンマに注目
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

t = 12345, 54321, 'hello!'タプルパッキング (tuple packing) の例となる。 ここでは値 1234554321'hello!' が 一つのタプルにパックされる。 逆の演算も可能だ。

>>> x, y, z = t

これは、シーケンスアンパッキング (sequence unpacking) と呼ばれている。 シーケンスアンパッキングするには、左辺の変数並びの要素数が、 シーケンスの長さと同じであることが必要だ。 多重代入が実はタプルパッキングとシーケンスアンパッキングの 組み合わせにすぎないことに注意しよう!

ここにはわずかな非対称性がある。 すなわち、複数個の値のパッキングはいつもタプルを造るが、 アンパッキングはどんなシーケンスにも働く。

 
5.4 辞書

Python に組み込まれているもう一つの便利なデータ型が 辞書 (dictionary) だ。 辞書は、ほかの言語で は ``連想記憶 (associative memory)'' とか ``連想配列 (associative array)'' と して見ることがある。 ある範囲の数によって添字付けられるシーケンスとちがい、 辞書はキー (key) によって添字付けられる。 キーはどんな変化不可能型 (immutable type) でもよい。 文字列と数はいつでもキーになり得る。 文字列か数かタプルだけからなるタプルなら、それもキーとして使う事ができる。 しかし、もしもタプルがなんであれ変化可能 (mutable) なオブジェクトを 直接または間接に含んでいるなら、それをキーとして使うことはできない。 リストは、スライス代入や添字付け代入は もちろん append()extend() のメソッドを使って、 その場で改変 (modify in place) できるから、キーとしては使えない。

辞書とは キー: 値 のペアからなる順序付けられていない集合で、 各キーは (一つの辞書の中で) 一意的であることが要求されている、 と考えるのが最も良い。 波かっこのペア {} は空の辞書を造る。 コンマで区切った キー:値 のペアの並びを波かっこの中に置くと、 初期値として キー:値 のペアがその辞書に加わる。 これは出力時に辞書が書かれる方法でもある。

辞書についての主な演算は、なんらかのキーとともに値を格納することと、 キーを与えてその値を取り出すことだ。 キー:値 のペアを del で削除することもできる。 もしも既に使用中であるキーを使って格納すると、 そのキーに結合していた古い値は忘れ去られる。 存在しないキーを使って値を取り出すとエラーが発生する。

辞書オブジェクトの keys() メソッドは、その辞書で使われている すべてのキーを順不同に並べたリストを返す (もしソートされたリストが欲しければ、 キーのリストに sort() を適用すればよい)。 ある単一のキーが辞書にあるかどうか調べるには、 その辞書の has_key() メソッドを使う。

以下は辞書を用いた小さな例だ。

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
True

dict() コンストラクタはタプルとして格納されたキーと値のペア のリストから直接辞書を構築する。 このコンストラクタで辞書を作成する場合、リスト内包表現を利用すると簡潔 にキーと値のリストを指定することができる。

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>>> dict([(x, x**2) for x in vec])     # リスト内包表現を利用
{2: 4, 4: 16, 6: 36}

 
5.5 ループのテクニック

辞書によってループする場合、キーおよび対応する値は items() メ ソッドを利用して同時に取り出すことができる。

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print k, v
...
gallahad the pure
robin the brave

enumerate() 関数を使用してシーケンスをループさせると、添字 と添字に対応する値を同時に取りだす事ができる。

 
>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print i, v
...
0 tic
1 tac
2 toe

2つ以上の以上シーケンスを同時にループにするために、その要素を zip() 関数でペアにすることができる。

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print 'What is your %s?  It is %s.' % (q, a)
... 
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

 
5.6 もっと条件について

前述の while 文や if 文で使われる条件 (condition) を、 比較 (comparison) 以外の演算子で構成することもできる。

比較演算子 innot in は、 値がシーケンスに出現するか (出現しないか) どうかを調べる。 演算子 isis not は、二つのオブジェクトが本当に同じ オブジェクトかどうか比べるが、 このことはリストのような変化可能オブジェクトにとってだけ重要だ。 すべての比較演算子は同じ優先順位で、 そしてそれはすべての数値演算子の順位よりも低い。

比較は連鎖 (chain) することができる。 たとえば a < b == c は、ab より小さく、 かつ bc に等しいかどうかをテストする。

複数の比較を論理演算子 andor で組み合わせてもよいし、 比較の (またはなんであれ論理式の) 結果を not で否定してもよい。 これらはすべて、比較演算子よりもさらに低い優先順位だ。 その中では not の優先順位が最高で、or が最低となる。 したがって A and not B or C(A and (not B)) or C と 等価だ。 もちろん、丸かっこを使えば、望みの組み合わせを表現できる。

論理演算子 andor はいわゆる短絡 (short-circuit) 演算子だ。 つまり、引数が左から右へ評価され、結果が決定したらすぐに評価が止まる。 たとえば、もしも AC が真だが B が偽なら、 A and B and C は式 C を評価しない。 一般に、論理値としてではなく一般の値として使われるときは、短絡演算子の 戻り値は、最後に評価された引数となる。

比較やその他の論理式の結果を変数に代入することもできる。たとえば、

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Python では、C とちがい、代入が式の内部に出現できないことに注意するように。 C プログラマはこのことで不平を言うかもしれないが、 これは C プログラムの中で遭遇するありふれた種類の問題、 すなわち、式の中で == のつもりで = とタイプしてしまうこと を回避する。

 
5.7 シーケンスおよびその他の型の比較

シーケンスオブジェクトは、同じシーケンス型の他のオブジェクトと比較してよい。 比較には辞書式 (lexicographical) 順序が用いられる。 つまり、まず最初の項目どうしが比較され、 そしてもしそれらが異なっていればそれで比較結果が決まる。 もしそれらが等しければ、その次の項目どうしが比較される。 以下、これがシーケンスが尽きるまで繰り返される。 もしも比較される項目どうし自身が同じ型のシーケンスならば、 辞書式比較が再帰的に行われる。 もし二つのシーケンスの項目がすべて等しければ、二つのシーケンスは等しいと見なされる。 もし一方のシーケンスが他方のシーケンスの先頭部分列ならば、短い(少い)シーケンスの方が 小さいと見なされる。 文字列についての辞書式順序は、個々の文字について ASCII 順序を用いる。 下記は同じ型のシーケンスどうしの比較の例だ。

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

異なった型のオブジェクトの比較が有効であることに注意するように。 その結果は決定性をもつが恣意的だ。 つまり、型はその名前によって順序付けられる。 たとえば、リスト (list) はつねに文字列 (string) よりも小さく、 文字列はつねにタプル (tuple) よりも小さい。 混合数値型はその数値にしたがって比較される。したがって たとえば 0 は 0.0 は等しい5.1



... は等しい5.1
異なった型のオブジェクトを比較する規則に頼るべきではない。 それらは言語の将来のバージョンでは変更されるかもしれない。
See About this document... for information on suggesting changes.