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() はリストの 末尾の要素を削除して、返します。この場合も要素は削除されます。 (メソッドの用法 (signature) で i の両側にある角括弧は、 この引数がオプションであることを表しているだけなので、角括弧を 入力する必要はありません。この表記法は Python Library Reference の中で頻繁に見ることになるでしょう。)

index( x)
リスト中で、値 x を持つ最初の要素のインデクスを返します。 該当する項目がなければエラーとなります。

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

sort( )
リストの項目を、インプレース演算 (in place、元のデータを演算結果で 置き換えるやりかた) でソートします。

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]


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

リスト型のメソッドのおかげで、簡単にリストをスタックとして使えます。 スタックでは、最後に追加された要素が最初に取り出されます (``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() を使います。キューの先頭から項目を取り出すには インデクスに 0 を指定して pop() を使います。 例えば以下のようにします:

>>> 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(function, sequence)" は、 シーケンス sequence 中の要素 item から、 function(item) が真となるような要素からなる シーケンスを返します。 もし sequencestringtupleなら、 返り値も同じタイプになります。そうでなければ listになります。 例えば、いくつかの素数を計算するには以下のようにします:

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

"map(function, sequence)" は、 シーケンス sequence の各要素 item に対して function(item) を呼び出し、その戻り値からなる リストを返します。例えば、三乗された値の列を計算するには以下のように します:

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

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

"reduce(function, sequence)" は単一の値を返します。 この値は 2 つの引数をとる関数 function をシーケンス sequence の最初の 二つの要素を引数として呼び出し、次にその結果とシーケンスの次の要素を 引数にとり、以降これを繰り返すことで構成します。 例えば、 1 から 10 までの数の総和を計算するには以下のようにします:

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

シーケンス中にただ一つしか要素がなければ、その値自体が返されます; シーケンスが空なら、例外が送出されます。

3 つめの引数をわたして、初期値を指定することもできます。 この場合、空のシーケンスを渡すと初期値が返されます。それ以外の場合には、 まず初期値とシーケンス中の最初の要素に対して関数が適用され、次いでその結果 とシーケンスの次の要素に対して適用され、以降これが繰り返されます。例えば 以下のようになります:

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

(2.3 以降では) 実際には、上の例のように sum() を定義しないでください: 数値の合計は広く必要とされている操作なので、すでに組み込み関数 sum(sequence) が提供されており、上の例と全く同様に 動作します。 バージョン 2.3 で 新たに追加 された仕様です。

5.1.4 リストの内包表記

リストの内包表記 (list comprehension) は、リストの生成を map()filter()lambda の使用に 頼らずに行うための簡潔な方法を提供しています。 結果として得られるリストの定義は、しばしば上記の構文を使ってリストを 生成するよりも明快になります。各々のリストの内包表記は、 式、続いて for 節、そしてその後ろに続くゼロ個かそれ以上の 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]

リストの内包表記は map() よりもはるかに柔軟性があり、 複雑な式や入れ子になった関数でも利用できます:

>>> [str(round(355/113.0, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']


5.2 del

指定された値の要素をリストから削除する代わりに、インデクスで指定する 方法があります: それが del 文です。これはpop()メソッ ドとちがい、値を返しません。del文はリストから スライスを除去したり、リスト全体を削除することもできます (以前はスライスに空のリストを代入 して行っていました)。例えば以下のようにします:

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

del は変数全体の削除にも使えます:

>>> del a

この文の後で名前 a を参照すると、(別の値を a に 代入するまで) エラーになります。del の別の用途について はまた後で取り上げます。


5.3 タプルとシーケンス

リストや文字列には、インデクスやスライスを使った演算のように、 数多くの共通の性質があることを見てきました。これらは シーケンス (sequence) データ型 の二つの例です。Python はまだ 進歩の過程にある言語なので、他のシーケンスデータ型が追加されるかも しれません。標準のシーケンス型はもう一つあります: タプル (tuple) 型です。

タプルはコンマで区切られたいくつかの値からなります。例えば以下の ように書きます:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # タプルを入れ子にしてもよい
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

ご覧のように、タプルは常に丸括弧で囲われています。これは、入れ子に なったタプルが正しく解釈されるようにするためです; 入力の際には 丸括弧なしでもかまいませんが、結局 (タプルがより大きな式の 一部分の場合) たいてい必要となります。

タプルの用途はたくさんあります。例えば、(x, y) 座標対、データベースから 取り出した従業員レコードなどです。タプルは文字列と同じく、変更不能です: タプルの個々の要素に代入を行うことはできません (スライスと連結を使って 同じ効果を実現することはできますが)。リストのような変更可能な オブジェクトの入ったタプルを作成することもできます。

問題は 0 個または 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 には、集合 (set) を扱うためのデータ型もあります。集合 とは、重複する要素をもたない、順序づけられていない要素の集まりです。 Set オブジェクトは、結合 (union)、交差 (intersection)、差分 (difference)、 対象差 (symmetric difference) といった数学的な演算もサポートしています。

簡単なデモンストレーションを示します:

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> fruit = set(basket)               # 重複のない集合を作成
>>> fruit
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruit                 # 高速なメンバシップテスト
True
>>> 'crabgrass' in fruit
False

>>> # 二つの単語の文字を例にした集合間の演算
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # a 内の一意な文字
set(['a', 'r', 'b', 'c', 'd'])
>>> a - b                              # a にあって b にない文字
set(['r', 'd', 'b'])
>>> a | b                              # a か b にある文字
set(['a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'])
>>> a & b                              # a と b の双方にある文字
set(['a', 'c'])
>>> a ^ b                              # a または b の片方だけにある文字
set(['r', 'd', 'b', 'm', 'z', 'l'])


5.5 辞書

もう一つ、有用な型が Python に組み込まれています。それは 辞書 (dictionary) です。辞書は他の言語にも ``連想記憶 (associated memory)'' や ``連想配列 (associative array)'' として存在することがあります。 ある範囲の数でインデクス化されているシーケンスと異なり、辞書は キー (key) でインデクス化されています。このキーは何らかの変更不能な型になります; 文字列、数値、およびタプルは常にキーにすることができます; ただし、タプルに 何らかの変更可能なオブジェクトが含まれている場合にはキーに使うことは できません。リストをキーとして使うことはできません。これは、リストに スライスやインデクス指定の代入を行ったり、 append()extend()のようなメソッドを使うと、 インプレースで変更することができるためです。

辞書は順序付けのされていない キー(key): 値(value) のペアからなり、 キーが (辞書の中で) 一意でければならない、と考えると最もよいでしょう。 波括弧 (brace) のペア: {} は空の辞書を生成します。 カンマで区切られた key: value のペアを波括弧ペアの間に入れると、 辞書の初期値となる key: value が追加されます; この表現方法は 出力時に辞書が書き出されるのと同じ方法です。

辞書での主な操作は、ある値を何らかのキーを付けて記憶することと、 キーを指定して値を取り出すことです。 del で key: value のペアを 削除することもできます。 すでに使われているキーを使って値を記憶すると、以前そのキーに関連 づけられていた値は忘れ去られてしまいます。存在しないキーを使って 値を取り出そうとするとエラーになります。

辞書オブジェクトの keys() メソッドは、辞書で使われている 全てのキーからなるリストを適当な順番で返します (リストをソート したいなら、このキーのリストに sort() を使ってください)。 ある単一のキーが辞書にあるかどうか調べるには、辞書の has_key() メソッドか、inキーワード を使います。

以下に、辞書を使った小さな例を示します:

>>> 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')
1
>>> 'guido' in tel
True

dict() コンストラクタは、キーと値のペアをタプルにしたもの からなるリストを使って直接辞書を生成します。キーと値のペアが あるパターンをなしているなら、リストの内包表現を使えばキーと値の リストをコンパクトに指定できます。

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

チュートリアルの後部では、キー=値ペアをdict()コンストラクタ に渡すために適したジェネレータ式について学習します。

キーが単純な文字列の場合、キーワード引数を使って定義する方が単純な場合 もあります。

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}


5.6 ループのテクニック

辞書の内容にわたってループを行う際、iteritems() メソッドを使うと、 キーとそれに対応する値を同時に取り出せます。

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.iteritems():
...     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

二つまたはそれ以上のシーケンス型を同時にループするために、 関数 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.

シーケンスを逆方向に渡ってループするには、まずシーケンスの範囲を順方向に指定し、 次いで関数reversed() を呼び出します。

 
>>> for i in reversed(xrange(1,10,2)): 
...     print i 
... 
9 
7 
5 
3 
1

シーケンスを並び順にループするには、sorted() 関数を使います。 この関数は元の配列を変更せず、並べ変え済みの新たな配列を返します。

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print f
... 	
apple
banana
orange
pear


5.7 条件についてもう少し

whileif 文 で使った条件 (condiction) には、 値の比較だけでなく、他の演算子も使うことができます、

比較演算子 in および not in は、ある値があるシーケンス中に 存在するか (または存在しないか) どうかを調べます。演算子 is および is not は、二つのオブジェクトが実際に同じオブジェクト であるかどうかを調べます; この比較は、リストのような変更可能な オブジェクトにだけ意味があります。全ての比較演算子は同じ優先順位を 持っており、ともに数値演算子よりも低い優先順位となります。

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

比較演算はブール演算子 andor で組み合わせられます。また、 比較演算 (あるいは何らかのブール式) の結果の否 (negate) はnot で とれます。これらの演算子は全て、比較演算子よりも低い優先順位になっています。 A and not B or C(A and (not B)) or C が等価になるように、 ブール演算子の中で、not の優先順位が最も高く、or が最も 低くなっています。もちろん、丸括弧を使えば望みの組み合わせを表現できます。

ブール演算子 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.8 シーケンスとその他の型の比較

シーケンスオブジェクトは同じシーケンス型の他のオブジェクトと比較できます。 比較には 辞書的な (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) よりも小さい、といった 具合になります。5.1

型混合の数値の比較は、数値そのものに従って比較 されるので、例えば 0 は 0.0 と等しい、という結果になります。



... 具合になります。5.1
異なる型のオブジェクトを比較するための規則を今後にわたって当てに してはなりません; Python 言語の将来のバージョンでは変更されるかも しれません。
ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。