やだやだやだ作りたい作りたい作りたい～～～～～！
この記事の目的
競技プログラミングでは、問題を解くうえで便利なデータ構造というものがいくつかあります（セグメント木、UnionFind、優先度付きキューなどなど……名前だけは聞いたことのある方もいるのではないでしょうか）。これらのデータ構造は、ライブラリとして作成しておくと、使いたいときにさっと取り出してパッと使えるので非常に便利です。
このライブラリ、Python では class を用いて作成することが多いのですが、class には機能が多く、イチから学ぶのは結構大変です。そのくせ、「競プロのライブラリを作る」という場面ではほとんど使わない機能も多いです。（継承、ゲッター/セッター、...）
そこで本記事では、class で競プロライブラリを作成するのに最低限必要な要素のみに絞って紹介したいと思います。
さらに細かい仕様や機能については書籍1や公式ドキュメントをご覧ください。
classって何？
皆さんが普段から使っている数値、文字列、リスト、……これらはオブジェクトと呼ばれるものです。オブジェクトには、整数を表す int 、文字列を表す string など、たくさんの型があります。これらはtype()関数によって調べることができます。
>>> a = 7
>>> b = "onigiri"
>>> c = {2, 4, 6}
>>> type(a)
<class 'int'>
>>> type(c)
<class 'set'>
各オブジェクトはそれぞれデータ（属性）を持っています。例えば、上の変数 $a$ は整数 $7$ を属性に持つ int オブジェクト、$c$ は「それぞれ整数 $2, 4, 6$ を持つ3つの int オブジェクト」を属性に持つ set オブジェクトです。
また、オブジェクトにはその型ごとに固有の機能（メソッド）があります。例えばlist型なら
| メソッド名 | 機能 |
|---|---|
list.append(x) |
末尾にオブジェクト $x$ を追加 |
list.pop() |
末尾のオブジェクトを取り出す |
list.sort() |
配列をソートする |
list.count(x) |
配列中の $x$ の個数を数える |
といった具合です。
class は、独自の属性・メソッドを持つ新たな型を定義するためのキーワードです。これを用いれば、「複数の頂点と辺を属性に持つグラフのオブジェクト」や、「名前、年齢、住所、……を属性に持つヒトのオブジェクト」など、もともと Python に存在しないオブジェクトを自由に作ることができます。
累積和を管理するクラス
本記事では、二つの list オブジェクトとその長さ（ int オブジェクト）を属性に持つ型を作りたいと思います。
属性を定義しよう！
型の定義は、class （型の名前）から始めます。
とりあえず名前はRuisekiとして、まずは属性、つまりそのオブジェクトがどういうデータを持つのかを定義しましょう。
class Ruiseki:
def __init__(self, l):
self.lis = l
self.N = len(l)
self.rui = [0]*(self.N + 1)
突然いろいろなものが出てきましたが、詳しくは後から説明するので、今はここに書かれた3つのself.～に注目してください。
これらが属性です。属性は__init__()の中で定義します。各属性は、self.（属性の名前）という変数を用いて表します。
まず、lisという名前の属性を定義します。ここでは、__init__()の引数lが、self.lisとしてそのままあてがわれています。これは、後にオブジェクトを作成する際に引数として渡すもの（今回は配列を想定しています）がそのオブジェクトの属性の一つとなることを表しています。
「オブジェクト作成時に引数を渡す」という操作に馴染みがなくても、競技プログラミングに触れたことがあれば誰でも一度はやったことがあるでしょう。
>>> x = int(input()) # intオブジェクト作成時に、引数として標準入力された文字列を渡している
>>>
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l) # Ruisekiオブジェクト作成時に引数として配列を渡すと
>>> a.lis # オブジェクトの属性lisに登録されている
[3, 1, 4, 1, 5]
個別のオブジェクトの属性には（オブジェクトを表す変数）.（属性の名前）でアクセスすることができます。
同時に定義されていた属性Nは渡された配列lの長さ（整数）を持ち、ruiは長さself.N + 1の配列を持っています。
>>> a.N
5
>>> a.rui
[0, 0, 0, 0, 0, 0]
ここで、
あれ？
__init__()の引数はselfとlの二つあったのに、オブジェクトを作るときはlしか渡さなくていいの？
と思った人は鋭いです。これは後ほど説明します。
メソッドを定義しよう！
さて、属性が設定できましたが、このままではただリスト二つと整数を一つ持っているだけのただの箱です。次はこの箱に新しい機能、メソッドを追加していきましょう。今回欲しい機能としては
- 累積和を取る
- 元の配列の $i$ 番目の要素を知る
- $i$ 番目の要素までの累積和を知る
- 累積和が初めて $x$ 以上になるインデックス $i$ を知る
あたりでしょうか。順に実装していきましょう。
まずは累積和を取るメソッドbuild()を作ります。これがないと始まりません。累積和を計算する上で必要な情報はすべて属性として持っているので、特に引数を取る必要はありません。
def build(self):
for i in range(self.N):
self.rui[i+1] = self.rui[i] + self.lis[i]
ここでは単純に、長さself.Nの配列self.lisの累積和を順に配列self.ruiに格納していく、という気持ちで大丈夫です。変数の名前が見慣れないだけで、普段と変わりません。
n = 5
f = [3, 1, 4, 1, 5]
g = [0]*(n+1)
for i in range(n):
g[i+1] = g[i] + f[i]
では、このメソッドbuild()を実行したらどうなるでしょうか。
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.rui # build前は初期状態のまま
[0, 0, 0, 0, 0, 0]
>>> a.build()
>>> a.rui
[0, 3, 4, 8, 9, 14]
見事累積和が計算できました！最初に定義した属性ruiに累積和が格納されています。
では次に、元の配列の $i$ 番目の要素を返すメソッドaccess()を作りましょう。引数として $i$ を取ります。
def access(self, i):
return self.lis[i]
元の配列は属性lisとして持っているので、self.lis[i]を返すだけです。簡単ですね。
本来は $i$ がself.N以上だった場合に例外を投げる、などの処理を行った方がよいのですが、どうせ配列self.lisにアクセスする際に Python が勝手に例外を投げてくれるので今回はよしとします。
>>> a.access(0)
3
>>> a.access(10)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\home\python\ruiseki.py", line 12, in access
return self.lis[i]
IndexError: list index out of range
同様に、$i$ 番目まで（ $i$ 番目は含む、つまり閉区間）の累積和を返すメソッドcumulate()は、
def cumulate(self, i):
return self.rui[i+1]
と書けますね。インデックスが $1$ ずれることに注意してください。
で、結局selfってなんなのさ
さて、そろそろずっと存在していた謎の引数selfについて説明します。わかりやすさを優先するため厳密には異なると思います。ご了承ください。
あるオブジェクトがメソッドを呼び出すとき、内部的にそのメソッドを呼び出したオブジェクト自身が引数として渡されます。そして、そのオブジェクトはほかの引数を押しのけて第一引数として渡されます。
これらの処理はあくまで内部的に行われるので、呼び出す際に明示的に引数として与えることはしません。ただし、メソッド側では、オブジェクト自身が引数として与えられることを考慮して記述する必要があります。これがselfの正体です。
つまり、access()を例にとると、
「
access()を呼び出したオブジェクトをselfとして、そのselfの持つ属性lisの $i$ 番目を返す」
という処理を行っている、ということです。オブジェクトの属性には（オブジェクトを表す変数）.（属性の名前）でアクセスすることができるので、self.lis[i]を返せばよいわけです。
a.access(3)
↓
access()メソッドを呼び出したのはオブジェクトa
↓
オブジェクトaの属性lis(=a.lis=[3, 1, 4, 1, 5])の $3$ 番目
↓
$1$
実は、以下のコードでも完全に同じように動きます。
def access(hoge, i):
return hoge.lis[i]
この場合、このメソッドの中では第一引数として渡されるオブジェクトの名前をhogeとして扱っています。何の問題もありません。2
ただし、ほとんどの場合において慣例的にselfという名前が使われており、他人がコードを見た際に混乱が生じやすい、などの理由により、第一引数の変数名としてはselfを用いることが極めて強く推奨されています。無意味な逆張りはしないようにしましょう。
まだ説明してないことがあるだろ
ここまでに書いたコードを振り返ると、最初に属性を定義した際の形式とメソッドを定義した形式がとても似ていることが分かります。実のところ、属性を定義する際に用いた__init__()はメソッドの一種であり、特殊メソッドと呼ばれるものの一つです。
特に__init__()は、
「オブジェクト作成時に、オブジェクトを初期化するために自動的に呼ばれるメソッド」です。
この内部で属性を定義しておくことで、オブジェクト作成と同時にオブジェクトに属性が与えられるため、とても便利、というわけです。
実際、__init__()を丸ごと削除してしまってもオブジェクトは作成できるものの、
>>> a = Ruiseki()
>>> a.lis
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'Ruiseki' object has no attribute 'lis'
このように、「属性lisなんてないよ」と怒られてしまいます。
__init__() の活用
ところで、上で書いたコードで、cumulate()を呼ぶ前に必ずbuild()を呼ばなくてはならないことに気付いたでしょうか。
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.cumulate(3)
0
>>> a.build()
>>> a.cumulate(3)
9
build()を呼ぶ前はruiの中身は全部0なので、見当違いな答えを返してしまいます。もしコンテストでうっかりbuild()を忘れて提出しようものなら、WAまっしぐらです。
そこで、__init__()の中身を次のように変更してみましょう。
def __init__(self, l):
self.lis = l
self.N = len(l)
self.rui = [0]*(self.N + 1)
self.build()
こうすると、オブジェクトを作成すると同時に、初期化の一環としてbuild()が呼ばれます。こうすれば、わざわざ自分でbuild()しなくてもよくなります。
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.cumulate(3)
9
あるいは、build()メソッドを削除して、__init__()を次のように書き換えても構いません。
def __init__(self, l):
self.lis = l
self.N = len(l)
self.rui = [0]*(self.N + 1)
for i in range(self.N):
self.rui[i+1] = self.rui[i] + self.lis[i]
build()で行っていた処理を丸々__init__()の中に移しました。最初に一度だけ行う処理であれば、このように__init__()をうまく使うことでより楽にオブジェクトを扱うことができます。
では最後に、まだ実装していなかった、累積和が初めて $x$ 以上になるインデックス $i$ を返すメソッドlower_bound()を作りましょう。$O(N)$での線形探索もいいですが、私は賢いので$O(\log N)$の二分探索をすることにします。
def lower_bound(self, x):
lo, hi = 0, self.N
while hi - lo > 1:
mid = (lo + hi) // 2
if self.rui[mid] < x:
lo = mid
else:
hi = mid
return hi - 1
インデックスのずれを考慮し、$-1$ してから出力しています。
これで無事累積和をもつ新しいクラスの完成です！おめでとうございます。
コード全体を見る
class Ruiseki:
def __init__(self, l):
self.lis = l
self.N = len(l)
self.rui = [0]*(self.N + 1)
self.build()
def build(self):
for i in range(self.N):
self.rui[i+1] = self.rui[i] + self.lis[i]
def access(self, i):
return self.lis[i]
def cumulate(self, i):
return self.rui[i+1]
def lower_bound(self, x):
lo, hi = 0, self.N
while hi - lo > 1:
mid = (lo + hi) // 2
if self.rui[mid] < x:
lo = mid
else:
hi = mid
return hi - 1
>>> l = [3, 1, 4, 1, 5]
>>> a = Ruiseki(l)
>>> a.access(2)
4
>>> a.cumulate(4)
14
>>> a.lower_bound(7)
2
作れたはいいけど、何がうれしいの？
別にわざわざ慣れない class を使わなくても、
n = 5
f = [3, 1, 4, 1, 5]
g = [0]*(n + 1)
for i in range(n):
g[i+1] = g[i] + f[i]
をコピペすれば十分じゃん、と思う方もいるかもしれません。
確かに、 class を使わず main 関数内でいくつかの変数と関数を定義するだけで済む場合もあります。しかし、例えば累積和を取りたい配列が100個あったらどうでしょう？
n1 = 5
f1 = [3, 1, 4, 1, 5]
g1 = [0]*(n1+1)
for i in range(n1):
g1[i+1] = g1[i] + f1[i]
n2 = 6
f2 = [9, 2, 6, 5, 3, 5]
腱鞘炎になる前にやめておきましょう。
このように、同一の操作を行いたい対象が多数存在する場合、class を用いたライブラリは本領を発揮します。
この前のコンテストでセグ木26本生やした時結構気持ちよかったんだけど、冷静に考えてセグ木を26本生やすことに快楽を覚えてるのヤバイな
— 煎茶 (@sentya7) March 4, 2020
その他、一度 class を定義してしまえば、ブラックボックスのようにその中身を気にせずメソッドを使えるため、コードがすっきりする、という利点があります。競プロなど、超短時間でデバッグを行う場合、確認すべき箇所が少なくて済むのは大きなメリットです。
ただ、先ほど挙げたような「累積和を取りたい配列が100個ある」場合は、二次元配列とfor文で簡単に実現することができます。何でもかんでも class 化すればいいってわけではないことは頭に入れておきましょう。
終わりに
幸い競プロ（特に AtCoder）で Python を使う人は割と多く、先人たちがさまざまなライブラリを class 化して公開してくれています。ありがたく使わせてもらいましょう。
ただ、その内部でどういった挙動をしているか把握していると、データ構造の応用やデバッグの際に大きく有利となります。理解を深めるためにも、コードを読み込む、あるいは一度自分で書いてみることをオススメします。また、この記事がその一助となれば幸いです。
君もPythonで変態データ構造を作ろう！