前回は正規表現を中心に文字列処理とジェネレータについて説明しました。今回は Python のオブジェクト指向機能について説明します。
プログラミングに興味のある方ならば、オブジェクト指向という言葉は聞いたことがあると思います。よく使われているオブジェクト指向言語にＣ++や Java があります。Ｃ++はオブジェクト指向プログラミングができるようにＣ言語を拡張したものですが、度重なる機能追加により複雑な言語仕様になってしまいました。このため、初心者がオブジェクト指向を学ぶには適していないと言われています。
その点、Python や Java はオブジェクト指向言語として設計されているため、すっきりとした言語仕様になっています。Python はわかりやすくて使いやすいプログラミング言語ですが、これはオブジェクト指向機能にもあてはまるのです。まずは最初に、一般的なオブジェクト指向について簡単に説明します。
プログラムを作る場合、全体を小さな処理に分割して、ひとつひとつの処理を作成し、それらを組み合わせて全体のプログラムを完成させます。このとき、基本的な部品となるのが関数です。つまり、処理を関数単位で分割して、それらを組み合わせてプログラムを作るわけです。もともと関数の役割は、入力されたデータを処理してその結果を返すことです。つまり、関数は機能を表しているのです。このため、全体を小さな処理に分割するにしても、機能単位で行われることが普通です。
オブジェクト指向プログラミングでは、関数ではなく「オブジェクト (object)」を部品として扱います。たとえば、えんぴつを考えてみましょう。えんぴつには、色、長さ、固さ、などいろいろな性質があります。そして、えんぴつを使って文字を書いたり、絵を描いたりすることができます。プログラムでは、このような性質をデータで表し、機能を関数で表すことになります。そしてオブジェクトとは、このデータと関数を結び付けたものなのです。
いままでのプログラミング言語では、データと関数を別々に定義するため、それをひとつのオブジェクトとして表すことができません。えんぴつで文字を書くにも、えんぴつの種類をチェックして文字を書くようにプログラムしなければいけません。ところが、オブジェクトはデータと関数を結び付けたものなので、自分がなにをしたらよいかわかっています。えんぴつオブジェクトに文字を書けと命じれば、それが赤えんぴつのオブジェクトであれば文字は赤に、黒えんぴつのオブジェクトであれば黒い文字になるのです。
このように、オブジェクトはデータと関数をひとつにまとめたものです。従来のプログラミングが全体を機能単位で分割するのに対し、オブジェクト指向プログラミングでは全体をオブジェクト単位に分割して、それを組み合わせることでプログラムを作成します。
ところで、データと関数を結び付けることは、従来のプログラミング言語でも可能です。オブジェクト指向はプログラミングの考え方のひとつであり、Ｃ++のようなオブジェクト指向言語を使わなくても、たとえばＣ言語でもその考え方にしたがってプログラムを作れば、オブジェクト指向プログラミングになります。
実際、オブジェクト指向には様々な考え方があり、いろいろなオブジェクト指向言語が存在します。ですが、データと関数をひとつにまとめたものをオブジェクトとして扱うという基本的な考え方は、オブジェクト指向言語の元祖と言われる Smalltalk でも、Ｃ++, Java, Python でも同じです。
次は、一般的なオブジェクト指向機能について簡単に説明します。
「クラス (class)」はオブジェクトの振る舞いを定義したものです。ここでデータを格納するための変数や、それを操作する関数が定義されます。この変数をメンバ変数とかインスタンス変数といい、関数を「メソッド (method)」といいます。メソッドはあとで説明します。
クラスはオブジェクトの設計図にあたるもので、オブジェクトの「雛形」と呼ぶこともあります。クラスはオブジェクトの振る舞いを定義するだけで、アクセスできる実体はなにも生み出していない、ということに注意してください。
このクラスから実体として作り出されるのが「インスタンス (instance)」です。このインスタンスを「オブジェクト」と考えてください。インスタンスを生成する方法は、当然ですがプログラミング言語によって違います。たとえば Ｃ++や Java は new を使います。図 1 を見てください。
┌─ class Foo ─┐ ┌─ instance ─┐
│ │ │ │
│ 設計図 │─ インスタンスの生成 →│ 実体 │
│ │ │ │
└────────┘ └───────┘
│
│
│ ┌─ instance ─┐
│ │ │
└───── インスタンスの生成 →│ 実体 │
│ │
└───────┘
図 1 : クラスとインスタンスの関係
クラスはオブジェクトの定義を表すものですから、Foo というクラスはひとつしかありません。これに対し、インスタンスはクラスから生み出されるオブジェクトです。たとえば、クラス Foo に new を適用することで、いくつでもインスタンスを生み出すことができるのです。クラスは設計図であり、それに従って作られるオブジェクトがインスタンスと考えるとわかりやすいでしょう。
メソッドはオブジェクトと結びついた関数です。オブジェクト指向プログラミングでは、ほかの関数から直接オブジェクトを操作することはせず、メソッドを呼び出すことで行います。メソッドは、クラスが異なっていれば同じ名前のメソッドを定義することができます。たとえば、クラス Foo1 にメソッド bar() が定義されていても、クラス Foo2 に同名のメソッド bar() を定義することができます。
そして、ここからが重要なのですが、あるオブジェクトに対してメソッド bar() を呼び出した場合、それが Foo1 から作られたオブジェクトであれば、Foo1 で定義された bar() が実行され、Foo2 から作られたオブジェクトであれば、Foo2 で定義された bar() が実行されるのです。
このように、オブジェクトが属するクラスによって、実行されるメソッドが異なるのです。この機能を「ポリモーフィズム(polymorphism)」と呼びます。これにより、オブジェクトは自分が行うべき適切な処理を実行できるわけです。
クラス、インスタンス、メソッドの関係は図 2 のようになります。
┌─ class Foo1 ─┐ ┌─ instance ─┐
│ │ │ │
│ 設計図 │─── 生成 ───→│ 実体 │
│ │ │ │
│ │ └───────┘
│┌─ method ─┐│ ↑
││ ││ │
││ bar()←─┼┼─── アクセス ─────┘
││ ││
│└──────┘│
└────────┘
図 2 : クラス、インスタンス、メソッドの関係
クラスという設計図が中心にあり、そこからインスタンスが生み出され、メソッドを使ってインスタンスを操作する、という関係になります。
さて、一般的な話はここまでにして、Python のオブジェクト指向機能に目を向けてみましょう。Python は class 文でクラスを定義します。class 文の構文を図 3 に示します。
class class_name(super_class, ...):
.....
図 3 : class 文の構文
class の次にクラス名を指定し、その次のカッコで他のクラスを指定すると、そのクラスの機能を引き継ぐことができます。この機能を「継承」といいます。継承は次回で詳しく説明します。カッコを省略すると継承は行われません。そのあとにコロン ( : ) を付けて、インデントでクラス定義の範囲を表します。
一番簡単なクラス定義を示しましょう。リスト 1 を見てください。
リスト 1 : クラス定義
class Foo:
pass
一般に、クラス名は英大文字から始めることが多いので、名前は Foo としました。pass は何もしないことを表す Python の文です。Python はインデントでブロックの範囲を表すので、このように pass が必要になる場合があります。Foo はクラス名しかありませんが、これでも立派なクラスなのです。次の例を見てください。
>>> class Foo: ... pass ... >>> a = Foo() >>> a <__main__.Foo object at 0x7fd850d7dd00>
Python はクラスを関数と同じ形式で呼び出すと、そのクラスのインスタンスを生成して返します。Foo() を呼び出すとき引数を指定することができます。これはあとで説明します。
Python のインスタンス変数は、他のオブジェクト指向言語のそれとはちょっと変わっています。Python には class 文でインスタンス変数を定義する特別な構文はありません。関数のローカル変数と同様に、インスタンス変数への代入が行われると、Python はその変数をインスタンス内に生成します。
インスタンス変数のアクセスは、モジュールの場合と同様にインスタンスの後ろにドットを付けて、その後ろにアクセスする名前を指定します。次の例を見てください。
>>> a = Foo() >>> a.x Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'Foo' object has no attribute 'x' >>> a.x = 10 >>> a.x 10
クラス Foo のインスタンスを生成して変数 a にセットします。a.x と入力すると、インスタンス変数 x にアクセスしますが、インスタンス内に x は存在しないのでエラーになります。a.x = 10 と代入操作を行うと、インスタンス変数 x を生成して、そこに値 10 を代入します。したがって、次に a.x を入力すると、その値 10 を表示します。
このように、Python のインスタンス変数は、代入操作が行われるときに生成されます。これは他のオブジェクト指向言語と異なる Python の特徴です。そして、もう一つ重要なことがあります。Python のインスタンス変数は、どこからでもアクセスすることができるのです。Ｃ++や Java のように、private や protected でアクセスを制限することはできません。Python のインスタンス変数はすべて public なのです。
アクセス制限がないからといって、Python のオブジェクト指向機能が役に立たないわけではありません。Python のほかにも、たとえば CLOS (Common Lisp Object system) のように、インスタンス変数のアクセス制限がないオブジェクト指向言語があります。インスタンス変数のアクセスはメソッドを介して行うなど、お行儀のよいプログラムを作るように注意すれば大丈夫です。
メソッドは関数と同じく def 文で定義します。Python の場合、class 文の中で定義された関数がメソッドになります。メソッドの第 1 引数にはインスタンスが渡されます。Python では、この引数名を self と記述する習慣があります。
簡単な例として、点を表すクラスを作ってみましょう。名前は Point にしました。x 座標をインスタンス変数 x に、y 座標を変数 y に格納します。リスト 2 を見てください。
リスト 2 : Point クラス
import math
class Point:
def __init__(self, x1, y1):
self.x = x1
self.y = y1
# 2 点間の距離を求める
def distance(p1, p2):
dx = p1.x - p2.x
dy = p1.y - p2.y
return math.sqrt(dx * dx + dy * dy)
Python の場合、'__' で始まり '__' で終わる名前のメソッドには特別な機能が割り当てられています。これを「特殊メソッド」といいます。__init__() はインスタンスを生成するときに自動的に呼び出される特殊メソッドです。
Python では、__init__() で必要なインスタンス変数を初期化します。self には Point のインスタンスが渡されます。この段階では、インスタンス変数はまだ設定されていません。ここで、self.x と self.y に代入操作を行うと、インスタンス変数 x と y が生成されて値がセットされます。なお、__init__() は return で値を返すとエラーになります。ご注意ください。
それでは、実際に試してみましょう。
>>> a = Point(0, 0) >>> a.x 0 >>> a.y 0
__init__() の第 1 引数にはインスタンスが渡されるので、Point(0, 0) の最初の実引数 0 が __init__() の仮引数 x に、2 番目の実引数 0 が仮引数 y に渡されます。そして、インスタンス変数 x, y が引数の値に初期化されます。
メソッド distance() は Point クラスのインスタンスを 2 つ受け取り、その距離を計算します。Python の場合、メソッドの第 1 引数には self と書く習慣がありますが、distance() は 2 点の距離を求めるメソッドなので、このプログラムでは引数名を p1 と p2 にしました。sqrt() は平方根を求める関数で、モジュール math に定義されています。
メソッド distance() は、次のように呼び出すことができます。
>>> a = Point(0, 0) >>> b = Point(10, 10) >>> a.distance(b) 14.142135623730951
メソッドのアクセスはインスタンス変数と同じ形式で、メソッド名の後ろにカッコを付けて呼び出します。最初に Python は a が属するクラスを調べます。a には Point クラスのインスタンスが格納されているので、Python は Point クラスに定義されているメソッドを調べ、該当するメソッド distance() を呼び出すのです。これは、次のような関数形式の呼び出しと同じです。
>>> Point.distance(a, b) 14.142135623730951
このように、クラス名を明示してメソッドを呼び出すこともできます。ここで、インスタンスを使ったメソッドの呼び出しは、クラス名を明示する通常の関数呼び出しと違い、インスタンスによって適切なメソッドが選択されることに注意してください。たとえば、3 次元の座標を表す Point3D クラスを考えてみましょう。リスト 3 を見てください。
リスト 3 : Point3D クラス
class Point3D:
def __init__(self, x1, y1, z1):
self.x = x1
self.y = y1
self.z = z1
# 2 点間の距離を求める
def distance(p1, p2):
dx = p1.x - p2.x
dy = p1.y - p2.y
dz = p1.z - p2.z
return math.sqrt(dx * dx + dy * dy + dz * dz)
クラス Point3D は Point を 3 次元に拡張しただけです。Point でも Point3D でも距離を計算するメソッド distance() が定義されていることに注目してください。それでは、メソッド distance() を呼び出してみましょう。
>>> a = Point(0, 0) >>> b = Point(10, 10) >>> c = Point3D(0, 0, 0) >>> d = Point3D(10, 10, 10) >>> a.distance(b) 14.142135623730951 >>> c.distance(d) 17.320508075688775
このように、ドットの左側のインスタンスによって適切なメソッドが呼び出され、ポリモーフィズムが働いていることがわかります。もしも、ポリモーフィズムを利用せずにプログラムすると、distance() の中でインスタンスの種類をチェックしなければいけません。インスタンスの種別を調べるには関数 isinstance() を使います。
isinstance(object, class_name)
instance() は引数 object が class_name のインスタンスであれば真を返し、そうでなければ偽を返します。isinstance() を使って distance() を書き換えると、リスト 4 のようになります。
リスト 4 : ポリモーフィズムを使わない distance()
def distance(p1, p2):
if isinstance(p1, Point):
dx = p1.x - p2.x
dy = p1.y - p2.y
return math.sqrt(dx * dx + dy * dy)
elif isinstance(p1, Point3D):
dx = p1.x - p2.x
dy = p1.y - p2.y
dz = p1.z - p2.z
return math.sqrt(dx * dx + dy * dy + dz * dz)
else:
raise NotImplementedError
distance() は 2 つのデータを扱うだけなので、プログラムはそれほど複雑にはなりません。しかし、たくさんのデータを扱うようになると、それだけプログラムは複雑になります。とくに新しいデータを追加する場合、プログラムの内部でデータの種別をチェックしている箇所をすべて調べて、そこに新しい処理を追加しなければいけません。プログラムの規模が大きくなると、修正箇所を調べるだけでも大変です。
ところが、ポリモーフィズムを使ってプログラムを作ると、新しいデータを追加するにしても、そのデータを表すクラスとメソッドを定義するだけでいいのです。あとは Python がインスタンスに合わせて適切なメソッドを呼び出してくれます。オブジェクト指向では、オブジェクトをひとつの部品として扱います。新しい部品を追加するにしても、今までの部品を修正せずにそのまま使えた方が便利です。ポリモーフィズムはオブジェクト指向に必須の機能なのです。
インスタンス変数は個々のインスタンス (オブジェクト) に格納される変数です。その値はインスタンスによって変わります。クラスで共通の変数や定数を使いたい場合は、class 文の中で変数を定義します。これを「クラス変数」といいます。簡単な例を示しましょう。
>>> class Foo: ... z = 1 ... >>> Foo.z 1 >>> a = Foo() >>> b = Foo() >>> a.z 1 >>> b.z 1 >>> Foo.z = 10 >>> a.z 10 >>> b.z 10
変数 z はクラス Foo の中で定義しているのでクラス変数になります。クラス変数は「クラス名 + ドット ( . ) + 変数名」でアクセスすることができます。Foo.z は 1 と表示されます。
クラス変数はインスタンスからでもアクセスすることができます。インスタンスを生成して変数 a, b にセットします。a.z と b.z とすると、クラス変数 z にアクセスします。クラス変数 z の値を 10 に更新すると、a.z と b.z の値も 10 になります。
ただし、インスタンス変数に z があると、クラス変数を隠してしまいます。次の例を見てください。
>>> a.z = 100 >>> a.z 100 >>> Foo.z 10 >>> b.z 10
インスタンスで変数の代入が行われると、それはインスタンス変数として扱われます。a.z = 100 はインスタンス a に変数 z がないので、インスタンス変数 z を生成して 100 をセットします。これ以降、a.z はインスタンス変数 z をアクセスすることになります。
メソッドは個々のインスタンスを操作する関数です。一般に、ユーザが定義するメソッドは引数のインスタンスを操作対象とし、クラスの動作にかかわることはありません。インスタンスを操作するメソッドを「インスタンスメソッド」といいます。これに対し、クラスの動作にかかわるメソッドを考えることができます。これを「クラスメソッド」をといいます。
たとえば、クラス Foo のクラス変数 z を操作するクラスメソッド get_z(), set_z() を考えてみましょう。Python のメソッドは呼び出すのにインスタンスが必要になります。クラス名を明示して呼び出す場合でも、第 1 引数にインスタンスを渡さないといけません。インスタンスが不要な場合、これでは面倒です。
また、クラス変数にアクセスするためにはクラスが必要になります。クラスメソッドを呼び出すとき、たとえば Foo.get_z(), Foo.set_z(1) とすると、メソッドの第 1 引数にクラスが渡されると便利です。Python の場合、デコレータ @classmethod を使ってクラスメソッドを実現します。次の例を見てください。
>>> class Foo: ... z = 1 ... @classmethod ... def get_z(cls): return cls.z ... @classmethod ... def set_z(cls, x): cls.z = x ... >>> Foo.get_z() 1 >>> Foo.set_z(10) >>> Foo.get_z() 10 >>> a = Foo() >>> a.get_z() 10
メソッド get_z(), set_z() の前に @classmethod を書くだけです。これで引数 cls にドットの左側のクラスが渡されます。また、Python はクラスメソッドのほかに「スタティックメソッド」を定義することができます。説明は割愛しますので、詳細は Python のマニュアルをお読みください。
Python では、インスタンス変数やクラス変数、メソッドのことを「属性 (attribute)」といいます。属性は名前で管理されていて、同じ名前のインスタンス変数とメソッドを同時に使うことはできません。インスタンス変数の方が優先されるため、メソッドを呼び出すことができなくなります。インスタンス変数はクラス変数やメソッドよりも優先されることに注意してください。
(1)変数
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(None)
└─┘ └─┴─┘ └─┴─┘ └─┴─┘
(2)ヘッダセル
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(None)
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 5 : 連結リスト
それでは簡単な例題として、連結リスト (linked list) というデータ構造を作ってみましょう。Python のリストは 1 次元配列のことですが、連結リストはデータを一方向につなげたデータ構造です。リストを操作するプログラミング言語では Lisp が有名ですが、Lisp で扱うリストが連結リストです。図 5 に連結リストの構造を示します。
連結リストはセル (cell) というデータを繋げて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図 5 でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへの参照を格納します。リストの終わりを示すため、最後のセルの右側には特別な値（たとえば None）を格納します。そして、図 5 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 5 (2) のようにヘッダセルを用意する方法もあります。
連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかります。これが連結リストの短所です。
それではプログラムを作りましょう。連結リストを表すクラス LinkedList とセルを表すクラス Cell を定義します。リスト 6 を見てください。
リスト 6 : 連結リストの定義
# 連結リストクラス
class LinkedList:
# セル
class Cell:
def __init__(self, data, link = None):
self.data = data
self.link = link
# 連結リストの初期化
def __init__(self, *args):
self.top = LinkedList.Cell(None) # ヘッダセル
for x in reversed(args):
self.insert(0, x)
・・・メソッドの定義・・・
セルは連結リストを構成する部品で、他のクラスから利用されることはありません。そこで、クラス Cell はクラス LinkedList の中で定義することにします。このように、クラス定義は入れ子にすることができます。
なお、入れ子にしたクラスは LinkedList.Cell のようにドット ( . ) を使って参照することができます。厳密な意味で Cell を隠蔽することはできませんが、プログラムを書くときに余分な手間がかかるので、連結リストを実装する場合はこれで十分だと思います。
Cell のインスタンス変数 data にデータを格納し、link に次のセルへの参照を格納します。Python の場合、インスタンスは参照渡しされるので、渡されたセルをそのまま link にセットするだけです。なお、Cell のインスタンス変数 data と link は直接アクセスすることにします。アクセスメソッドを用意する方法もありますが、Cell は LinkedList の中でしか使用しないので、直接アクセスしても問題はないでしょう。
次に、セルを使って連結リストクラス LinkedList を作成します。LinkedList はセルを保持するインスタンス変数 top を用意します。メソッド __init__() で、top にヘッダセルをセットします。ヘッダセルの data はダミーで、このプログラムでは None をセットします。
__init__() は可変個の引数を受け取るようにすると便利です。関数 reversed() で配列 args の後ろから要素 x を取り出し、メソッド insert() で連結リストの先頭に x を追加していきます。これで、連結リストには args と同じ順番で要素を並べることができます。
あとは、連結リストを操作するメソッドを定義します。連結リストを操作する基本的なメソッドを表 1 に示します。
| メソッド | 機能 |
|---|---|
| ls.at(n) | n 番目の要素を求める |
| ls.insert(n, x) | n 番目の位置にデータ x を挿入する |
| ls.delete(n) | n 番目の要素を削除する |
| ls.isEmpty() | 連結リストが空の場合は真を返す |
ls は LinkedList のインスタンスを表します。要素の位置はリストと同様に 0 から数えることにします。位置 n がリストの要素数（長さ）よりも多い場合、at(), insert(), delete() は None を返すことにします。isEmpty() は連結リストが空の場合は True を返し、データがあれば False を返します。
最初に、作業用のメソッドとして n 番目のセルを求める処理を作ります。メソッド名は _nth() としました。リスト 7 を見てください。
リスト 7 : n 番目のセルを求める
def _nth(self, n):
i = -1
cp = self.top
while cp is not None:
if i == n: return cp
i += 1
cp = cp.link
return None
最初に、ヘッダセル top を cp にセットします。ヘッダセルから数えるので、変数 i は -1 に初期化します。次に、while ループでセルをたどり、i が n と等しくなったとき、そのセルを return で返します。
セルのたどり方は実に簡単です。図 6 を見てください。
cp1 cp2 cp3
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│10│・┼→│20│・┼→│30│・┼→
└─┴─┘ └─┴─┘ └─┴─┘
↑ ↑
(1) (2)
(1) cp = cp.link => cp2
(2) cp = cp.link => cp3
図 6 : セルのたどり方
セル cp1 の link にはセル cp2 への参照が格納されています。変数 cp が cp1 の場合、cp = cp.link とすれば、cp の値はセル cp2 になります (図 6 (1))。さらに cp = cp.link とすれば、cp の値は cp3 になります (図 6 (2))。
_nth() の場合、while ループでセルをたどっていきますが、途中でセルがなくなった場合、cp の値は None になるので while ループを終了して None を返すことになります。
それでは、n 番目の要素を求めるメソッド at() から作りましょう。リスト 8 を見てください。
リスト 8 : n 番目の要素を求める
def at(self, n):
cp = self._nth(n)
if cp is not None: return cp.data
return None
メソッド _nth() を呼び出して n 番目のセルを求めます。cp が None でなければ、格納されているデータ cp.data を返します。cp が None の場合は None を返します。
次は、データの挿入を行うメソッド insert() を作りましょう。データの挿入はセルの link を書き換えることで実現できます。図 7 を見てください。セル (1) とセル (2) の間に、セル (3) を挿入します。
top (1) (2)
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ┼──→│10│・┼─ X ─→│20│・┼→│30│／│
└─┘ └─┴┼┘ └─┴─┘ └─┴─┘
│ (3) ↑
│ ┌─┬─┐│
└→│40│・┼┘
└─┴─┘
セル(1)とセル(2)の間にセル(3)を挿入する場合
図 7 : データの挿入
セル (1) の後ろにセル (3) を挿入する場合、セル (1) の link にはセル (2) への参照がセットされているので、この値をセル (3) の link にセットします。これで、セル (3) とセル (2) がリンクされます。次に、セル (1) の link にセル (3) への参照をセットします。これで、セル (1) とセル (2) の間に、セル (3) を挿入することができます。
プログラムをリスト 9 に示します。
リスト 9 : データの挿入
def insert(self, n, x):
cp = self._nth(n - 1)
if cp is not None:
cp.link = LinkedList.Cell(x, cp.link)
return x
return None
連結リストにデータを挿入する場合、挿入する位置のひとつ手前のセルが必要になります。_nth() で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろに data を挿入します。n が 0 の場合、_nth() はヘッダセルを返すので、リストの先頭にデータが挿入されることになります。
LinkedList.Cell(x, cp.link) で x を格納する新しいセルを生成します。第 2 引数に cp.link を指定することで、新しいセルの後ろに、cp の次のセルを接続することができます。そして、cp.link の値を新しいセルに書き換えます。これで cp の後ろに新しいセルを挿入することができます。最後に挿入した x を返します。
次は、データを削除するメソッド delete_at() を作りましょう。
(1) (2) (3)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│10│・┼×→│20│・┼→│30│・┼→
└─┴┼┘ └─┴─┘ └─┴─┘
│ ↑
└─────────┘
図 8 : データの削除:セル(2) を削除する場合
データを削除する場合も、セルを付け替えるだけで済ますことができます。図 8 を見てください。セル (1) の後ろにあるセル (2) を削除する場合、セル (1) の link をセル (3) への参照に書き換えればいいのです。セル (3) はセル (2) の link から求めることができます。つまり、セル (1) を保持する変数を cp とすると、セル (3) は cp.link.link で求めることができるのです。
プログラムをリスト 10 に示します。
リスト 10 : データの削除
def delete(self, n):
cp = self._nth(n - 1)
if cp is not None and cp.link is not None:
data = cp.link.data
cp.link = cp.link.link
return data
return None
データを削除する場合も、削除する位置のひとつ手前のセルが必要になります。_nth() で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろのセルを削除します。
次に、削除するセルがあるか cp.link の値をチェックします。値が None でなければ、そのセルを削除します。まず、削除するセルに格納されているデータを data に取り出します。それから cp.link の値を cp.link.link に書き換えます。最後に data を返します。
ところで、連結リストからはずされたセルやデータは、変数 top からアクセスすることができなくなります。Python の場合、どの変数からも参照されなくなったオブジェクトはゴミになり、「ゴミ集め (GC)」[*1] によって回収して再利用されます。
GC がないプログラミング言語では、不要になったオブジェクトは自動的に回収されません。それを行うようにプログラムする必要があるのです。Python のように GC があるプログラミング言語では、ゴミになったオブジェクトは自動的に回収されるので、プログラマの負担はそれだけ少なくなります。
それでは実行してみましょう。
>>> a = LinkedList() >>> for x in range(5): ... print(a.insert(0, x)) ... 0 1 2 3 4 >>> for x in range(5): ... print(a.at(x)) ... 4 3 2 1 0 >>> while not a.isEmpty(): ... print(a.delete(0)) ... 4 3 2 1 0
正常に動作していますね。
前回説明したように、Python にはイテレータという機能があります。イテレータはクラスで特殊メソッド __iter__() と __next__() を定義することで実現できます。関数 iter() はメソッド __iter__() を、next() は __next__() を呼び出します。さっそく、連結リストにもイテレータを実装してみましょう。リスト 11 を見てください。
リスト 11 : イテレータの実装
def __iter__(self):
self.index = self.top.link
return self
def __next__(self):
if self.index is None:
raise StopIteration
data = self.index.data
self.index = self.index.link
return data
メソッド __iter__() はメソッド __next()__ で使用するインスタンス変数 index を先頭のセル top.link の値で初期化します。これで連結リストのインスタンス self にセルを参照する変数が作成されます。__iter__() は引数 self をそのまま返します。
メソッド __next__() は要素 index.data を求めてから、インスタンス変数 index の値を次のセル index.link に更新します。これで next() が呼び出されるたびに連結リストの要素を順番に取り出すことができます。index が None ならば連結リストは空になったので、raise で例外 StopIteration を送出します。これはイテレータを使うときの規則です。
それでは実行例を示しましょう。
>>> a = LinkedList(*range(5)) >>> for x in a: ... print(x) ... 0 1 2 3 4 >>> list(a) [0, 1, 2, 3, 4] >>> tuple(a) (0, 1, 2, 3, 4)
イテレータを用意すると、for 文やイテレータを引数に受け取る関数に連結リストを渡すことができます。list() に渡すと連結リストをリストに、tuple() に渡すとタプルに変換することができます。
イテレータはインスタンス変数を使いましたが、ジェネレータ (generator) を使うともっと簡単に実現できます。リスト 12 を見てください。
リスト 12 : ジェネレータ
def each(self):
cp = self.top.link
while cp is not None:
yield cp.data
cp = cp.link
メソッド名は each としました。each() は yield 文でセルの要素 cp.data を順番に返していくだけです。実行例を示しましょう。
>>> a = LinkedList(*range(5)) >>> for x in a.each(): ... print(x) ... 0 1 2 3 4 >>> list(a.each()) [0, 1, 2, 3, 4] >>> tuple(a.each()) (0, 1, 2, 3, 4)
引数にイテレータを受け取る関数では、ジェネレータを渡しても動作します。list() に a.each() を渡せば、連結リストをリストに変換することができます。同様に、tuple() に渡せばタプルに変換することができます。
リストやタプルのように、連結リストでも要素のアクセスに角カッコ [ ] を使うことができると便利です。これは、クラスに特殊メソッドを定義することで実現できます。
Python には演算子や特定の機能に対応する特殊メソッドが用意されていて、クラスで独自の処理を行わせることができます。これを「演算子のオーバーロード」といいます。Python は演算子のオーバーロードを積極的に使っています。Python の特殊メソッドは多数あるので、説明は割愛いたします。詳細は Python のマニュアルをお読みください。
クラス LinkedList では表 2 に示す特殊メソッドを定義してみましょう。
| 特殊メソッド名 | 操作 | 機能 |
|---|---|---|
| __len__(self) | len(L) | 連結リストの長さを求める |
| __str__(self) | print() | 連結リストの表示 |
| __getitem__(self, n) | L[n] | n 番目の要素を求める |
| __setitem__(self, n, x) | L[n] = x | n 番目の要素を x に更新 |
| __delitem__(self, n) | del L[n] | n 番目の要素を削除 |
| __add__(x , y) | x + y | x と y を連結する |
メソッド__len__() と __str__() は簡単です。リスト 13 を見てください。
リスト 13 : __len__() と __str__()
def __len__(self):
n = 0
for _ in self.each(): n += 1
return n
def __str__(self):
if self.top.link is None: return 'LList()'
s = 'LList('
for x in self.each(): s += '{}, '.format(x)
return s[:-2] + ')'
メソッド __len__() は each() を呼び出して要素の個数を数えるだけです。__str__() は連結リストを文字列に変換して返します。文字列は変数 s に格納します。連結リストが空の場合は 'LList()' を返します。そうでなければ、each() を呼び出して要素を順番に取り出し、format で文字列に変換して変数 s に連結します。最後に、余分な ', ' を削除して ')' を付け加えます。
それでは実行例を示しましょう。
>>> a = LinkedList() >>> len(a) 0 >>> print(a) LList() >>> b = LinkedList(*range(10)) >>> print(b) LList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) >>> len(b) 10
LinkedList() で連結リストのインスタンスを生成して変数 a にセットします。a は空リストなので、len(a) は 0 になります。print(a) で表示すると LList() になります。次に、0 から 9 までの整数値を格納した連結リストを生成して変数 b にセットします。len(b) は格納したデータの個数 10 になり、print(b) で連結リストのデータを表示することができます。
角カッコで要素をアクセスする場合も簡単です。リスト 14 を見てください。
リスト 14 : 角カッコ [] でのアクセス
def __getitem__(self, n):
cp = self._nth(n)
if cp is not None: return cp.data
raise IndexError
def __setitem__(self, n, x):
cp = self._nth(n)
if cp is not None:
cp.data = x
return None
raise IndexError
def __delitem__(self, n):
if self.delete(n) is None: raise IndexError
メソッド __getitem__() は n 番目の要素を返します。_nth で n 番目のセルを求めて cp にセットします。cp が None でなければ cp.data を返します。cp が None の場合は n 番目のセルがないので、例外 IndexError を raise で送出します。
例外はエラーのことで、IndexError はエラーを表すクラスです。IndexError は添字が範囲外の場合に発生するエラーです。例外は次回で詳しく説明します。
メソッド __setitem__() も同様に _nth() で n 番目のセル cp を求め、cp.data を引数 x の値に書き換えます。メソッド __delitem__() は連結リストの delete() を呼び出すだけです。削除できなかった場合は IndexError を送出します。
実行例を示します。
>>> print(b) LList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) >>> for x in range(10): ... print(b[x]) ... 0 1 2 3 4 5 6 7 8 9 >>> b[5] = 100 >>> print(a) LList(0, 1, 2, 3, 4, 100, 6, 7, 8, 9) >>> del b[5] >>> print(b) LList(0, 1, 2, 3, 4, 6, 7, 8, 9)
b[x] で連結リストの要素を取り出し、b[5] = 100 で要素を書き換えることができます。そして、del b[5] で 5 番目の要素を削除することができます。
次は演算子 + を実装します。リスト 15 を見てください。
リスト 15 : 連結リストの連結
def __add__(x, y):
# リストのコピー
def copy(a):
if not a: return None
return LinkedList.Cell(a.data, copy(a.link))
# リストの連結
def append(a, b):
if a is None: return copy(b)
return LinkedList.Cell(a.data, append(a.link, b))
if not isinstance(y, LinkedList):
raise NotImplementedError
z = LinkedList()
z.top.link = append(x.top.link, y.top.link)
return z
メソッド __add__() は内部関数 append() で引数 a と b を連結します。__add__() の引数 x は LinkedList のインスタンスですが、引数 y のデータ型はわかりません。このため、isinstance() を使って LinkedList のインスタンスであることを確認しています。
append() は再帰定義でプログラムしていて、引数 a をコピーしてその後ろに b を連結します。append() の動作を図 9 に示します。
┌────────────────────────────┐
│append( (1, 2), (3, 4) ) │
├────────────────────────────┤
│ ( 1, 2 ) │
│ ┬ ──rest()─┐ │
│ first() ↓ │
│ │ ┌──────────────────────┐│
│ │ │append( (2), (3, 4) ) ││
│ │ ├──────────────────────┤│
│ │ │ ( 2 ) ││
│ │ │ ┬ ─rest()─┐ ││
│ │ │ first() ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │append( None, (3, 4) ) => (3 4) │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ Cell() ←┘ ││
│ │ │ (2, 3, 4) ││
│ │ └─────┼────────────────┘│
│ └──→ Cell() ←┘ │
└──────┼─────────────────────┘
↓
(1, 2, 3, 4)
図 9 : append の動作
引数 a が None であればセル b をそのまま返します。そうでなければ、a.link を append() に渡して再帰呼び出しします。そして、その結果と a.data を Cell() で接続すればいいのです。
ただし、第 2 引数のリストをそのまま返すと、その部分は 2 つのリストで共有されることになります。この場合、メソッド del などで共有部分を破壊的に修正すると、他の連結リストの値も変化することになります。そこで、今回は append() で第 2 引数の連結リストをコピーすることにします。引数 a が None の場合、引数 b をそのまま返すのではなく、内部関数 copy() で b をコピーしたリストを返します。
それでは実行例を示します。
>>> a = LinkedList(*range(5)) >>> print(a) LList(0, 1, 2, 3, 4) >>> b = LinkedList(*range(5, 10)) >>> print(b) LList(5, 6, 7, 8, 9) >>> c = a + b >>> print(c) LList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
LinkedList() で連結リストを生成して変数 a, b にセットします。そして、c = a + b とすると、c には a と b をつないだ連結リストがセットされます。
最後に、関数呼び出しをエミュレートする特殊メソッドを紹介しましょう。クラスにメソッド __call__() を定義すると、インスタンスを関数のように呼び出すことができます。簡単な例を示しましょう。
>>> class Foo: ... def __init__(self, n): ... self.x = n ... def __call__(self, n): ... return self.x * n ... >>> foo10 = Foo(10) >>> foo10(5) 50 >>> foo10(10) 100 >>> foo100 = Foo(100) >>> foo100(5) 500
この機能を使うと、関数のクロージャと同じような働きをさせることができます。Foo(10) のインスタンスを変数 foo10 にセットします。そして、foo10(5) と呼び出すと、メソッド __call__() が呼び出され、引数 5 を 10 倍した 50 を返します。同様に、foo10(10) は 100 を返します。Foo(100) で生成されたインスタンスは、引数を 100 倍する関数として使うことができます。
また、ジェネレータのように、値をひとつずつ生成していくことも簡単にできます。簡単な例として、フィボナッチ数列 ( 0, 1, 1, 2, 3, 5, 8, ..... ) を発生する関数を作ってみます。フィボナッチ数列を求める関数の定義を図 10 に示します。
フィボナッチ関数はこのまま再帰定義でプログラムすると、再帰呼び出しを 2 回行う「二重再帰」になるため時間がかかります。このため、二重再帰を末尾再帰に変換するか、繰り返しでプログラムを作るのが普通です。
ジェネレータのように値をひとつずつ発生させる場合、ひとつ前の値 a1 とふたつ前の値 a2 を保存しておけば、次の値を a1 + a2 で求めることができます。そして、a1 と a2 の値を更新すればいいわけです。プログラムをリスト 16 に示します。
リスト 16 : フィボナッチ数列
class MakeFibo:
def __init__(self):
self.a1 = 0
self.a2 = 1
def __call__(self):
n = self.a1
self.a1, self.a2 = self.a2, self.a1 + self.a2
return n
クラス MakeFibo はフィボナッチ数列を発生させるインスタンスを生成します。メソッド __init__() でインスタンス変数 a1 を 0 に、a2 を 1 に初期化します。メソッド__call__() では、変数 n に a1 の値を保存してから、a1 と a2 の値を更新します。最後に return で n を返します。
それでは、実際に実行してみましょう。
>>> a = MakeFibo() >>> for x in range(10): ... print(a()) ... 0 1 1 2 3 5 8 13 21 34
このように、MakeFibo() でインスタンスを生成すれば、フィボナッチ数列を生成する関数として使うことができます。
オブジェクト指向の基本的な考え方と、Python のクラス、インスタンス、メソッドについて説明しました。それから、連結リストを例題にして、演算子のオーバーロード、イテレータ、ジェネレータについて説明しました。次回は継承と例外処理について説明します。
#
# linkedlist.py : 連結リスト
#
# Copyright (C) 2006-2022 Makoto Hiroi
#
# 連結リストクラス
class LinkedList:
# セル
class Cell:
def __init__(self, data, link = None):
self.data = data
self.link = link
# 連結リストの初期化
def __init__(self, *args):
self.top = LinkedList.Cell(None) # ヘッダセル
for x in reversed(args):
self.insert(0, x)
# n 番目のセルを求める
def _nth(self, n):
i = -1
cp = self.top
while cp is not None:
if i == n: return cp
i += 1
cp = cp.link
return None
# 挿入
def insert(self, n, x):
cp = self._nth(n - 1)
if cp is not None:
cp.link = LinkedList.Cell(x, cp.link)
return x
return None
# 参照
def at(self, n):
cp = self._nth(n)
if cp is not None: return cp.data
return None
# 削除
def delete(self, n):
cp = self._nth(n - 1)
if cp is not None and cp.link is not None:
data = cp.link.data
cp.link = cp.link.link
return data
return None
# リストは空か
def isEmpty(self): return self.top.link is None
# イテレータ
def __iter__(self):
self.index = self.top.link
return self
def __next__(self):
if self.index is None:
raise StopIteration
data = self.index.data
self.index = self.index.link
return data
# ジェネレータ
def each(self):
cp = self.top.link
while cp is not None:
yield cp.data
cp = cp.link
# リストの長さ
def __len__(self):
n = 0
for _ in self.each(): n += 1
return n
# [] による参照
def __getitem__(self, n):
cp = self._nth(n)
if cp is not None: return cp.data
raise IndexError
# [] による更新
def __setitem__(self, n, x):
cp = self._nth(n)
if cp is not None:
cp.data = x
return None
raise IndexError
# del []
def __delitem__(self, n):
if self.delete(n) is None: raise IndexError
# +
def __add__(x, y):
# リストのコピー
def copy(a):
if not a: return None
return LinkedList.Cell(a.data, copy(a.link))
# リストの連結
def append(a, b):
if a is None: return copy(b)
return LinkedList.Cell(a.data, append(a.link, b))
if not isinstance(y, LinkedList):
raise NotImplementedError
z = LinkedList()
z.top.link = append(x.top.link, y.top.link)
return z
# 表示
def __str__(self):
if self.top.link is None: return 'LList()'
s = 'LList('
for x in self.each(): s += '{}, '.format(x)
return s[:-2] + ')'
# 簡単なテスト
if __name__ == '__main__':
a = LinkedList()
print(a)
print(len(a))
print(a.isEmpty())
for x in range(5): a.insert(x, x)
print(a)
print(len(a))
print(a.isEmpty())
for x in range(5):
print(a.at(x), a[x])
for x in range(5):
a[x] = a[x] * 10
for x in a:
print(x)
for x in a.each():
print(x)
while not a.isEmpty():
# a.delete(0)
del a[0]
print(a)
a = LinkedList(1,2,3,4,5)
b = LinkedList(6,7,8,9,10)
c = a + b
print(a)
print(b)
print(c)
c[0] = 10
c[5] = 60
print(a)
print(b)
print(c)