RSSフィードを購読
Practical Python Design Patterns - The Iterator Pattern 編
Practical Python Design Patterns - Python で学ぶデザインパターン: The Iterator Pattern - Part. 1 「第13章: イテレータパターン」の巻 投稿一覧へ戻る
Published 2022年6月26日8:33 by mootaro23
SUPPORT UKRAINE
- Your indifference to the act of cruelty can thrive rogue nations like Russia -
Chapter 13: Iterator Pattern(第13章: イテレータパターン)
The wheels of bus go round and round, round and round, round and round
(バスの車輪はぐるぐる回る、ぐるぐる回る、まだまだ回る)
Overview
(概要)
データ構造とアルゴリズム (data structures and algorithms) はソフトウェアの設計と開発プロセスにおいて欠くことのできない存在です。データ構造それぞれには適した用途がありその時々の問題に対して適切なデータ構造を選択することで、作業量の大幅な削減、効率の大幅な向上が期待できます。的確なデータ構造を選択しそれにマッチするアルゴリズムを採用できれば問題解決のハードルはグンと下がります。
データ構造の実装はそれぞれ異なるため、それぞれに機能する特化したアルゴリズムを実装したい、という誘惑は常に付きまといます。例えば次のようなバイナリツリー (二分木、二進木) 構造を考えます:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __init__(self, data):
self.data = data
self.left = None
self.right = None
この構造内のすべての要素を「訪問 (参照)」するためのコードは次のようになるでしょう:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def tree_traverse(node):
if node.left is not None:
tree_traverse(node.left)
print(node.data)
if node.right is not None:
tree_traverse(node.right)
if __name__ == '__main__':
root = Node('親')
root.left = Node('親-左')
root.right = Node('親-右')
root.left.right = Node('親-左-右')
tree_traverse(root)
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def tree_traverse(node):
if node.left is not None:
tree_traverse(node.left)
print(node.data)
if node.right is not None:
tree_traverse(node.right)
if __name__ == '__main__':
root = Node('親')
root.left = Node('親-左')
root.right = Node('親-右')
root.left.right = Node('親-左-右')
tree_traverse(root)
単純なリストの要素を参照するコードと比較してください:
lst = [1, 2, 3, 4, 5]
for i in range(len(lst)):
print(lst[i])
for i in range(len(lst)):
print(lst[i])
for ループ内でインデックス番号を利用して各要素を参照するこの方法が pythonic ではないことは重々承知していますが、C/C++ や Jave をメインに利用されている方には馴染み深いコードであるはずです。ここで敢えてこの実装方法で記述したのは、ほぼほぼ同じ結果を得るためのコードであるにもかかわらず list の場合とバイナリツリーの場合の顕著な違いを改めて認識してほしかったからです。
ジェネリックプログラミング (generic programming) の提唱者であり C++ Standard Template Library の主要な設計者・実装者である Alexander Stepanov は多大な時間を費やして、定義時には決定していないデータ型 (型は実際の利用時に引数として与えられる) に対して機能するアルゴリズムを採用して記述するジェネリックプログラミングの手法を考案しました。彼は、純粋数学 (pure mathematics) 並びに代数学 (algebra) とコンピュータサイエンスを結び付け、ほとんどのアルゴリズムはコンテナ (containers) と呼ばれる代数的データ型 (algebraic data type) に関連して定義することが可能である、と結論付けました。
アルゴリズムをある特定の型やコンテナの実装から切り離すことで、それらのコンテナの実装の詳細に一切注意を払うことなくアルゴリズムを記述することが可能となります。この「分離」の結果、コードがよりジェネリックなものになると同時に再利用性が向上します。
前の例に戻れば、全ての要素を参照する (traverse: 横断する) 対象がリストなのか、バイナリツリーなのか、はたまたほかのコレクションなのかを気にすることなく操作を行いたいわけです。
そのためには、コレクションが継承するインターフェースを作成し、そのインターフェースによってコレクションの要素を参照する (traverse する) 操作を一般化 (共通化) します。この実装に必要となるコンポーネントは次の通りです。
最初に必要なのはインターフェースです。このインターフェースではコレクション内の次のアイテムを取得するためのメソッドを定義します。また、利用者に対してコレクション内にはもう参照すべき要素がないことを知らせるためのメソッドも必要です。
続いて、最初に定義したインターフェースを継承しコレクション内の要素を実際にトラバースするクラスが必要です。このクラスのオブジェクトが iterator (イテレーター) になります。
こうした従来のアプローチ方法で実装したものが次のコードになります:
classic_iter.py
import abc
class Iterator(metaclass=abc.ABCMeta):
@abc.abstractmethod
def has_next(self):
pass
@abc.abstractmethod
def next(self):
pass
class Container(metaclass=abc.ABCMeta):
@abc.abstractmethod
def getIterator(self):
pass
class MyListIterator(Iterator):
def __init__(self, my_list):
self.index = 0
self.list = my_list.list
def has_next(self):
return self.index < len(self.list)
def next(self):
self.index += 1
return self.list[self.index - 1]
class MyList(Container):
def __init__(self, *args):
self.list = list(args)
def getIterator(self):
return MyListIterator(self)
if __name__ == '__main__':
my_list = MyList(1, 2, 3, 4, 5, 6)
my_iterator = my_list.getIterator()
while my_iterator.has_next():
print(my_iterator.next())
class Iterator(metaclass=abc.ABCMeta):
@abc.abstractmethod
def has_next(self):
pass
@abc.abstractmethod
def next(self):
pass
class Container(metaclass=abc.ABCMeta):
@abc.abstractmethod
def getIterator(self):
pass
class MyListIterator(Iterator):
def __init__(self, my_list):
self.index = 0
self.list = my_list.list
def has_next(self):
return self.index < len(self.list)
def next(self):
self.index += 1
return self.list[self.index - 1]
class MyList(Container):
def __init__(self, *args):
self.list = list(args)
def getIterator(self):
return MyListIterator(self)
if __name__ == '__main__':
my_list = MyList(1, 2, 3, 4, 5, 6)
my_iterator = my_list.getIterator()
while my_iterator.has_next():
print(my_iterator.next())
実行結果は以下の通りです:
1
2
3
4
5
6
2
3
4
5
6
コレクションの要素をトラバースするためのこのアイデアがイテレータパターン (iterator pattern) と呼ばれているものです。
この記事に興味のある方は次の記事にも関心を持っているようです...
- People who read this article may also be interested in following articles ... -