Python3 データ構造

この章では、これまでに学んだ知識を踏まえて、Pythonのデータ構造を紹介します。

メソッド	説明
list.append(x)	リストの末尾に要素を1つ追加します。a[len(a):] = [x] と同じです。
list.extend(L)	指定したリストのすべての要素を追加してリストを拡張します。a[len(a):] = L と同じです。
list.insert(i, x)	指定した位置に要素を挿入します。最初の引数は、挿入する位置の直前にある要素のインデックスです。例えば、a.insert(0, x) はリスト全体の先頭に挿入し、a.insert(len(a), x) は a.append(x) と同じです。
list.remove(x)	リスト内の値が x である最初の要素を削除します。そのような要素がない場合はエラーが発生します。
list.pop([i])	リストの指定された位置から要素を削除し、その要素を返します。インデックスを指定しない場合、a.pop() は最後の要素を返します。要素はその後リストから削除されます。（メソッド内で i を囲む角かっこは、この引数が省略可能であることを示しており、実際に角かっこを入力する必要はありません。Pythonライブラリリファレンスではこのような表記をよく見かけます。）
list.clear()	リストのすべての項目を削除します。del a[:] と同じです。
list.index(x)	リスト内で値が x である最初の要素のインデックスを返します。一致する要素がない場合はエラーが発生します。
list.count(x)	リスト内で x が出現する回数を返します。
list.sort()	リストの要素をソートします。
list.reverse()	リストの要素を逆順にします。
list.copy()	リストの浅いコピーを返します。a[:] と同じです。

次の例では、リストのメソッドの大部分を示しています：

例

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

注意：insert、remove、sort など、リストを変更するメソッドは戻り値を返しません。

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

Pythonでは、リスト（list）を使ってスタックの機能を実装できます。スタックは後入れ先出し（LIFO, Last-In-First-Out）のデータ構造であり、最後に追加された要素が最初に削除されることを意味します。リストには、スタック操作に非常に適したいくつかのメソッドが用意されています。特にappend()とpop()メソッド。

append() メソッドを使うと要素をスタックの先頭に追加でき、インデックスを指定しない pop() メソッドを使うとスタックの先頭から要素を取り出すことができます。

スタック操作

プッシュ（Push）: 要素をスタックの先頭に追加します。
ポップ（Pop）: スタックの先頭要素を削除して返します。
スタックの先頭要素を参照する（Peek/Top）: スタックの先頭要素を削除せずに返します。
空かどうかをチェックする（IsEmpty）: スタックが空かどうかをチェックします。
スタックのサイズを取得する（Size）: スタック内の要素の数を取得します。

以下に、Pythonでリストを使ってこれらの操作を実装する方法の詳細を示します：

1、空のスタックを作成する

例

stack = []

2、プッシュ（Push）操作

append() メソッドを使って要素をスタックの先頭に追加します：

例

stack.append(1)
stack.append(2)
stack.append(3)
print(stack) # 出力: [1, 2, 3]

3、ポップ（Pop）操作

pop() メソッドを使ってスタックの先頭要素を削除して返します：

例

top_element = stack.pop()
print(top_element) # 出力: 3
print(stack) # 出力: [1, 2]

4、スタックの先頭要素を参照する（Peek/Top）

リストの最後の要素に直接アクセスします（削除しない）：

例

top_element = stack[-1]
print(top_element) # 出力: 2

5、空かどうかをチェックする（IsEmpty）

リストが空かどうかをチェックします：

例

is_empty = len(stack) == 0
print(is_empty) # 出力: False

6、スタックのサイズを取得する（Size）

len() 関数を使ってスタック内の要素の数を取得します：

例

size = len(stack)
print(size) # 出力: 2

例

以下は、上記の操作を使って簡単なスタックを実装する方法を示す完全な例です：

例

class Stack:
def __init__(self):
self.stack = []

def push(self, item):
self.stack.append(item)

def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
raise IndexError("pop from empty stack")

def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
raise IndexError("peek from empty stack")

def is_empty(self):
return len(self.stack) == 0

def size(self):
return len(self.stack)

# 使用例
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("スタックの先頭要素:", stack.peek()) # 出力: スタックの先頭要素: 3
print("スタックサイズ:", stack.size()) # 出力: スタックサイズ: 3

print("ポップした要素:", stack.pop()) # 出力: ポップした要素: 3
print("スタックが空かどうか:", stack.is_empty()) # 出力: スタックが空かどうか: False
print("スタックサイズ:", stack.size()) # 出力: スタックサイズ: 2

上記のコードでは、Stack クラスを定義し、リストを基盤となるデータ構造としてカプセル化し、スタックの基本操作を実装しました。

出力結果は以下のとおりです：

栈顶元素: 3
栈大小: 3
弹出元素: 3
栈是否为空: False
栈大小: 2

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

Pythonでは、リスト（list）をキュー（queue）として使用できますが、リストの特性により、リストを直接使ってキューを実装するのは最適な選択ではありません。

キューは先入れ先出し（FIFO, First-In-First-Out）のデータ構造であり、最初に追加された要素が最初に削除されることを意味します。

リストを使用する場合、リストの先頭で要素の挿入や削除を頻繁に行うと、これらの操作の時間計算量が O(n) であるため、パフォーマンスに影響が出ます。この問題を解決するために、Python は collections.deque を提供しています。これは両端キューであり、両端で効率的に要素を追加・削除できます。

collections.deque を使ってキューを実装する

collections.deque は Python 標準ライブラリの一部であり、キューの実装に非常に適しています。

以下は deque を使ってキューを実装する例です：

例

from collections import deque

# 空のキューを作成する
queue = deque()

# キューの末尾に要素を追加する
queue.append('a')
queue.append('b')
queue.append('c')

print("キューの状態:", queue) # 出力: キューの状態: deque(['a', 'b', 'c'])

# キューの先頭から要素を削除する
first_element = queue.popleft()
print("削除した要素:", first_element) # 出力: 削除した要素: a
print("キューの状態:", queue) # 出力: キューの状態: deque(['b', 'c'])

# キューの先頭要素を参照する（削除しない）
front_element = queue[0]
print("キューの先頭要素:", front_element) # 出力: キューの先頭要素: b

# キューが空かどうかをチェックする
is_empty = len(queue) == 0
print("キューが空かどうか:", is_empty) # 出力: キューが空かどうか: False

# キューのサイズを取得する
size = len(queue)
print("キューのサイズ:", size) # 出力: キューのサイズ: 2

```

リストを使ってキューを実装する

deque の方が効率的ですが、それでもリストを使ってキューを実装したい場合は、そのようにすることもできます。以下は、リストを使ってキューを実装する方法の例です：

1. キューを作成する

例

queue = []

2. キューの末尾に要素を追加する

append() メソッドを使って要素をキューの末尾に追加します：

例

queue.append('a')
queue.append('b')
queue.append('c')
print("キューの状態:", queue) # 出力: キューの状態: ['a', 'b', 'c']

3. キューの先頭から要素を削除する

pop(0) メソッドを使ってキューの先頭から要素を削除します：

例

first_element = queue.pop(0)
print("削除された要素:", first_element) # 出力: 削除された要素: a
print("キューの状態:", queue) # 出力: キューの状態: ['b', 'c']

4. キューの先頭要素を確認する（削除しない）

リストの最初の要素に直接アクセスします：

例

front_element = queue[0]
print("キューの先頭要素:", front_element) # 出力: キューの先頭要素: b

5. キューが空かどうかを確認する

リストが空かどうかを確認します：

例

is_empty = len(queue) == 0
print("キューが空かどうか:", is_empty) # 出力: キューが空かどうか: False

6. キューのサイズを取得する

len() 関数を使ってキューのサイズを取得します：

例

size = len(queue)
print("キューのサイズ:", size) # 出力: キューのサイズ: 2

例（リストを使ってキューを実装）

例

class Queue:
def __init__(self):
self.queue = []

def enqueue(self, item):
self.queue.append(item)

def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
else:
raise IndexError("dequeue from empty queue")

def peek(self):
if not self.is_empty():
return self.queue[0]
else:
raise IndexError("peek from empty queue")

def is_empty(self):
return len(self.queue) == 0

def size(self):
return len(self.queue)

# 使用例
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')

print("キューの先頭要素:", queue.peek()) # 出力: キューの先頭要素: a
print("キューのサイズ:", queue.size()) # 出力: キューのサイズ: 3

print("削除された要素:", queue.dequeue()) # 出力: 削除された要素: a
print("キューが空かどうか:", queue.is_empty()) # 出力: キューが空かどうか: False
print("キューのサイズ:", queue.size()) # 出力: キューのサイズ: 2

リストを使ってキューを実装することもできますが、collections.deque を使う方が効率的で簡潔です。deque は O(1) の時間計算量で追加・削除ができるため、キューのようなデータ構造に非常に適しています。

リスト内包表記

リスト内包表記は、シーケンスからリストを作成する簡単な方法を提供します。通常、アプリケーションはシーケンスの各要素に何らかの操作を適用し、その結果を新しいリストの要素として使ったり、特定の判定条件に基づいて部分シーケンスを作成したりします。

各リスト内包表記は、for の後に式が続き、その後にゼロ個以上の for または if 句が続きます。返される結果は、式をその後の for や if のコンテキストに基づいて生成したリストです。式がタプルを導出するようにしたい場合は、括弧を使う必要があります。

ここではリスト内の各数値を3倍にして、新しいリストを取得します：

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

ここで少し遊んでみましょう：

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

ここではシーケンス内の各要素に対してメソッドを呼び出します：

例

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

if 句をフィルタとして使うことができます：

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

以下はループやその他のテクニックのデモです：

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

リスト内包表記では、複雑な式やネストした関数を使うことができます：

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

ネストしたリスト内包表記

Pythonのリストは入れ子にすることもできます。

次の例は3X4の行列リストを示しています：

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

次の例は3X4の行列リストを4X3のリストに変換します：

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

上記の例は次の方法でも実装できます：

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

もう1つの実装方法：

>>> transposed = []
>>> for i in range(4):
... # the following 3 lines implement the nested listcomp
... 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]]

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

タプルとシーケンス

タプルはカンマで区切られたいくつかの値から構成されます。例：

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

ご覧のように、タプルは出力時には常に括弧が付き、入れ子構造を正しく表現します。入力時には括弧があってもなくても構いませんが、通常は括弧が必要です（タプルがより大きな式の一部である場合）。

集合

集合（セット）は、順序付けられておらず重複しない要素の集まりです。基本的な機能には、関係テストと重複要素の排除があります。

波括弧（{}）を使って集合を作成できます。注意：空の集合を作成するには、{} ではなく set() を使う必要があります。{} は空の辞書を作成します。このデータ構造については次の節で説明します。

以下は簡単なデモです：

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket) # 重複を削除
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket # メンバーシップの確認
True
>>> 'crabgrass' in basket
False

>>> # 以下は2つの集合の操作のデモ
...
>>> 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 にあるが、a と b の両方にはない文字
{'r', 'd', 'b', 'm', 'z', 'l'}

集合も内包表記をサポートしています：

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

辞書

もう1つの非常に便利な Python 組み込みデータ型は辞書です。

シーケンスは連続した整数をインデックスとしますが、辞書はキーワードをインデックスとします。キーワードには任意のイミュータブル（不変）な型を使用でき、通常は文字列または数値です。

辞書を理解する最良の方法は、順序付けられていないキー=>値のペアの集合と見なすことです。同じ辞書内では、キーは互いに異なっている必要があります。

波括弧1組で空の辞書 {} が作成されます。

これは辞書を使った簡単な例です：

>>> 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}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

コンストラクタ dict() は、キーと値のペアのタプルのリストから直接辞書を構築します。固定のパターンがある場合は、リスト内包表記で特定のキーと値のペアを指定できます：

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

さらに、辞書内包表記を使うと、任意のキーと値の式から辞書を作成できます：

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

キーが単純な文字列である場合は、キーワード引数を使ってキーと値のペアを指定する方が便利なことがあります：

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

ループのテクニック

辞書をループするとき、キーとそれに対応する値は 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 {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 f in sorted(set(basket)):
... print(f)
...
apple
banana
orange
pear

Python3上級チュートリアル