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

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
4                               # range(5)の最後の値
>>

 
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!')
>>> # タプルを入れ子にしてもよい
... 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')
1

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

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.