5. データ構造

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

5.1. リスト型についてもう少し

The list data type has some more methods. Here are all of the methods of list objects:

list.append(value, /)

リストの末尾に要素を一つ追加します。a[len(a):] = [x] と同様です。

list.extend(iterable, /)

iterable のすべての要素をリストの末尾に追加します。 a[len(a):] = iterable と同様です。

list.insert(index, value, /)

指定した位置に要素を挿入します。第 1 引数は、リストのインデクスで、そのインデクスを持つ要素の直前に挿入が行われます。従って、 a.insert(0, x) はリストの先頭に挿入を行います。また a.insert(len(a), x) は a.append(x) と等価です。

list.remove(value, /)

Remove the first item from the list whose value is equal to value. It raises a ValueError if there is no such item.

list.pop(index=-1, /)

指定された位置の要素をリストから取り除き、それを返します。インデックスが指定されていない場合、 a.pop() はリスト末尾の要素を取り除いて返します。リストが空であるか、インデックスがリストの範囲外の場合は、IndexError を送出します。

list.clear()

リスト中の全ての要素を削除します。del a[:] と同様です。

list.index(value[, start[, stop]])

Return zero-based index of the first occurrence of value in the list. Raises a ValueError if there is no such item.

任意の引数である start と end はスライス記法として解釈され、リストの探索範囲を指定できます。返される添字は、start 引数からの相対位置ではなく、リスト全体の先頭からの位置になります。

list.count(value, /)

Return the number of times value appears in the list.

list.sort(*, key=None, reverse=False)

リストの項目を、インプレース演算 (in place、元のデータを演算結果で置き換えるやりかた) でソートします。引数はソート方法のカスタマイズに使えます。 sorted() の説明を参照してください。

list.reverse()

リストの要素を、インプレース演算で逆順にします。

list.copy()

リストの浅い (shallow) コピーを返します。a[:] と同様です。

以下にリストのメソッドをほぼ全て使った例を示します:

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # インデックス4から数えて次の banana の位置
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

insert、remove、sort など、リストの変更だけを行うメソッドの戻り値が表示されていないことに気が付いたかもしれません。 これらのメソッドはデフォルトの None を返しています。 [1] これは Python の変更可能なデータ構造全てについての設計上の原則となっています。

もうひとつ気付くとしたら、すべてのデータでソートや比較できるわけではないということです。 例えば、 [None, 'hello', 10] はソートされません。なぜなら整数は文字列と比べられませんし、 None は他の型と比べられないからです。 また、順序関係が定義されていない型もあります。 例えば、 3+4j < 5+7j は有効な比較ではありません。

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

The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved ("last-in, first-out"). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index. For example:

>>> 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）をリストの末尾に対して行うと速いのですが、挿入（insert）や取り出し（pop）をリストの先頭に対して行うと遅くなってしまいます（他の要素をひとつずつずらす必要があるからです）。

キューの実装には collections.deque を使います。このクラスは両端で要素を高速に追加・取り出しできるように設計されています。例えば次のように使います:

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry が到着
>>> queue.append("Graham")          # Graham が到着
>>> queue.popleft()                 # 最初に到着した人が去る
'Eric'
>>> queue.popleft()                 # 2番目に到着した人が去る
'John'
>>> queue                           # 残っている人を到着順に表示
deque(['Michael', 'Terry', 'Graham'])

5.1.3. リストの内包表記

リスト内包表記を使うとリストを簡潔に作れます。シーケンスやイテラブルの各要素に操作を適用した結果から新しいリストを作るときによく使います。また、特定の条件を満たす要素だけを取り出して部分シーケンスを作ることもできます。

例えば、次のような平方のリストを作りたいとします:

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

このコードは x という名前の変数を作るか、既存の変数を上書きします。この変数がループ終了後も残ることに注意してください。次のように書けば、副作用なしで平方のリストを計算できます:

squares = list(map(lambda x: x**2, range(10)))

もしくは、以下でも同じです:

squares = [x**2 for x in range(10)]

これはより簡潔で読みやすいです。

リスト内包表記は、式とそれに続く for 句、さらに0個以上の for 句または if 句を角括弧で囲んだものです。式に続く for 句と if 句に従って式を評価し、その結果を要素とする新しいリストを作ります。例えば次のリスト内包表記は、2つのリストから等しくない要素同士を組み合わせてペアを作ります:

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

これは次のコードと等価です:

>>> combs = []
>>> for x in [1,2,3]:
...     for y in [3,1,4]:
...         if x != y:
...             combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

どちらのコードでも for 文と if 文の順序が同じであることに注目してください。

式がタプルの場合は前の例の (x, y) のように丸括弧で囲む必要があります。

>>> vec = [-4, -2, 0, 2, 4]
>>> # 値を2倍にした新しいリストを作る
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # リストから負の数を除く
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # すべての要素に関数を適用する
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # 各要素のメソッドを呼び出す
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # (number, square) のような2要素のタプルのリストを作る
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # タプルを丸括弧で囲まないとエラーになる
>>> [x, x**2 for x in range(6)]
  File "<stdin>", line 1
    [x, x**2 for x in range(6)]
     ^^^^^^^
SyntaxError: did you forget parentheses around the comprehension target?
>>> # 2つの 'for' を持つリスト内包表記でリストをフラットにする
>>> vec = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in vec for num in elem]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

リスト内包表記では複雑な式や入れ子になった関数呼び出しも使えます:

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

5.1.4. ネストしたリストの内包表記

リスト内包表記中の最初の式は任意の式なので、そこに他のリスト内包表記を書くこともできます。

長さ 4 のリスト 3 つからなるリストで実装した、次の 3x4 の行列について考えます。

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

次のリスト内包表記は、matrix の行と列を入れ替えます:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

前の節で見たように、内側のリスト内包表記は、続く for のコンテキストの中で評価されます。そのため、この例は次のコードと等価です:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

これをもう一度変換すると、次のコードと等価になります:

>>> transposed = []
>>> for i in range(4):
...     # 以下の3行はネストされたリスト内包表記と同じ実装
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

実際のコードでは、複雑な制御フローの文よりも組み込み関数を優先すべきです。 この用途には zip() 関数が適しています。

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

この行にあるアスタリスクの詳細については 引数リストのアンパック を参照してください。

5.2. del 文

There is a way to remove an item from a list given its index instead of its value: the del statement. This differs from the pop() method which returns a value. The del statement can also be used to remove slices from a list or clear the entire list (which we did earlier by assignment of an empty list to the slice). For example:

>>> 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) データ型 (Sequence Types --- list, tuple, range を参照) の二つの例です。 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))
>>> # タプルは不変(イミュータブル):
>>> t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # しかし、可変(ミュータブル)オブジェクトを含むことができる:
>>> v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

ご覧のとおり、タプルの表示には常に丸括弧がついていて、タプルのネストが正しく解釈されるようになっています。 タプルを書くときは必ずしも丸括弧で囲まなくてもいいですが、(タプルが大きな式の一部だった場合は) 丸括弧が必要な場合もあります。 タプルの各要素に代入することはできません。 しかし、タプルにリストのような変更可能なオブジェクトを含めることはできます。

タプルはリストと似て見えますが、使う場面や目的は異なることが多いです。 タプルは 不変 で、通常は異なる型の要素が並びます。 要素には、アンパック (この節の後半で説明します) やインデックスを使ってアクセスします (namedtuples では属性でもアクセスできます)。 リストは 可変 で、要素は通常同じ型であり、リストを反復処理してアクセスします。

問題は 0 個または 1 個の項目からなるタプルの構築です。これらの操作を行うため、構文には特別な細工がされています。空のタプルは空の丸括弧ペアで構築できます。一つの要素を持つタプルは、値の後ろにコンマを続ける (単一の値を丸括弧で囲むだけでは不十分です) ことで構築できます。美しくはないけれども、効果的です。例えば以下のようにします:

>>> empty = ()
>>> singleton = 'hello',    # <-- 末尾にカンマがあることに注意
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

文 t = 12345, 54321, 'hello!' は タプルのパック (tuple packing) の例です。値 12345, 54321, 'hello!' が一つのタプルにパックされます。逆の演算も可能です:

>>> x, y, z = t

この操作は、シーケンスのアンパック (sequence unpacking) とでも呼ぶべきもので、右辺には全てのシーケンス型を使うことができます。シーケンスのアンパックでは、等号の左辺に列挙されている変数が、右辺のシーケンスの長さと同じ数だけあることが要求されます。複数同時の代入が実はタプルのパックとシーケンスのアンパックを組み合わせたものに過ぎないことに注意してください。

5.4. 集合型

Python also includes a data type for sets. A set is an unordered collection with no duplicate elements. Basic uses include membership testing and eliminating duplicate entries. Set objects also support mathematical operations like union, intersection, difference, and symmetric difference.

中括弧、または set() 関数は set を生成するために使用することができます。注: 空集合を作成するためには set() を使用しなければなりません ({} ではなく)。後者は空の辞書を作成します。辞書は次のセクションで議論するデータ構造です。

Because sets are unordered, iterating over them or printing them can produce the elements in a different order than you expect.

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

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # 重複が削除されていることを確認
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # 高速なメンバー判定
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
>>>
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # aのユニークな文字
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # aにあってbにない文字
{'r', 'd', 'b'}
>>> a | b                              # aまたはbまたは両方に存在する文字
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # aとbの両方に存在する文字
{'a', 'c'}
>>> a ^ b                              # aまたはbにあるが、両方にはない文字
{'r', 'd', 'b', 'm', 'z', 'l'}

リスト内包 と同様に、 set 内包もサポートされています:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

5.5. 辞書型 (dictionary)

Another useful data type built into Python is the dictionary (see Mapping Types --- dict). Dictionaries are sometimes found in other languages as "associative memories" or "associative arrays". Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. Tuples can be used as keys if they contain only strings, numbers, or tuples; if a tuple contains any mutable object either directly or indirectly, it cannot be used as a key. You can't use lists as keys, since lists can be modified in place using index assignments, slice assignments, or methods like append() and extend().

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

The main operations on a dictionary are storing a value with some key and extracting the value given the key. It is also possible to delete a key:value pair with del. If you store using a key that is already in use, the old value associated with that key is forgotten.

Extracting a value for a non-existent key by subscripting (d[key]) raises a KeyError. To avoid getting this error when trying to access a possibly non-existent key, use the get() method instead, which returns None (or a specified default value) if the key is not in the dictionary.

辞書オブジェクトに対し list(d) を実行すると、辞書で使われている全てのキーからなるリストをキーが挿入された順番で返します (ソートされたリストが欲しい場合は、代わりに sorted(d) を使ってください)。ある単一のキーが辞書にあるかどうか調べるには、 in キーワードを使います。

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

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> tel['irv']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'irv'
>>> print(tel.get('irv'))
None
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

dict() コンストラクタは、キーと値のペアからなるシーケンスから直接辞書を生成します。

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

さらに、辞書内包表記ではキーと値に任意の式を使って辞書を作れます。

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

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

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

5.6. ループのテクニック

辞書に対してループを行う際、 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

二つまたはそれ以上のシーケンス型を同時にループするために、関数 zip() を使って各要素をひと組みにすることができます。

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(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(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

シーケンスをソートされた順序でループするには、 sorted() 関数を使います。 この関数は元のシーケンスを変更せず、ソート済みの新たなリストを返します。

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

シーケンスに set() を使うと、重複する要素を取り除けます。 sorted() と set() を組み合わせると、シーケンスの要素から重複を除き、 ソート順にループできます。 これはよく使われる書き方です。

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

リストを反復処理しながらそのリストを変更したくなることもありますが、代わりに新しいリストを作る方が簡単で安全なことがよくあります。

>>> import math
>>> raw_data = [56.2, float('NaN'), 51.7, 55.3, 52.5, float('NaN'), 47.8]
>>> filtered_data = []
>>> for value in raw_data:
...     if not math.isnan(value):
...         filtered_data.append(value)
...
>>> filtered_data
[56.2, 51.7, 55.3, 52.5, 47.8]

5.7. 条件についてもう少し

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

比較演算子 in および not in は、ある値があるコンテナーの中に存在するか (または存在しないか) どうかを確認するメンバーシップテストです。演算子 is および is not は、二つのオブジェクトが実際に同じオブジェクトであるかどうかを調べます。全ての比較演算子は同じ優先順位を持っており、ともに数値演算子よりも低い優先順位となります。

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

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

ブール演算子 and と or は、いわゆる 短絡 (short-circuit) 演算子です。これらの演算子の引数は左から右へと順に評価され、結果が確定した時点で評価を止めます。例えば、 A と C は真で 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プログラムで発生する一般的なクラスの問題を回避できます。

5.8. シーケンスとその他の型の比較

概して、シーケンスオブジェクトは、同じシーケンス型の他のオブジェクトと比較できます。 比較には 辞書的な (lexicographical) 順序が用いられます。 まず、二つのシーケンスの先頭要素同士を比較し、その値が等しくなければその時点で比較結果が決まります。 等しければ次の二つの要素を比較し、以降シーケンスの要素が尽きるまで続けます。 比較しようとする二つの要素がいずれも同じシーケンス型であれば、そのシーケンス間での辞書比較を再帰的に行います。 二つのシーケンスの全ての要素の比較結果が等しくなれば、シーケンスは等しいとみなされます。 片方のシーケンスがもう一方の先頭部分にあたる部分シーケンスならば、短い方のシーケンスが小さいシーケンスとみなされます。 文字列に対する辞書的な順序づけには、個々の文字ごとに Unicode コードポイントの数値による順序を用います。 以下に、同じ型のシーケンス間での比較を行った例を示します。

(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)

異なる型のオブジェクト同士も、適切な比較メソッドがあれば < や > で比較できます。 例えば、異なる数値型は数値としての値に従って比較されるので、0 と 0.0 は等しいとみなされます。 適切な比較メソッドがない場合、インタープリタは恣意的な順序を付ける代わりに TypeError 例外を送出します。

脚注