【Python】rangeを再実装し、計算量について学ぶ
rangeは、Pythonにおいて、繰り返しを可能にする仕組みです。本記事では、このrangeを再実装し、計算量について学びます。
計算量とは
あるアルゴリズムを使った演算の性能を表す指標のことです。計算量は大きく二つに分けられます。
- 時間計算量（処理時間の計算量）
- 空間計算量（メモリ使用量の計算量）
素朴な実装
組み込み型のドキュメントには、以下の記載があります。
range オブジェクトは collections.abc.Sequence ABC を実装し、包含判定、要素インデックス検索、スライシングのような機能を提供し、負のインデックスをサポートします (シーケンス型 — list, tuple, range を参照):
抽象クラスを継承することで、いくつかの属性が自動的に定義されそうです。具体的には、ここの表に記載があるとおり、以下の抽象メソッドを実装すれば、mixinメソッドとして、__contains__、__iter__、__reversed__、index、countがタダでついてきます。
__getitem____len__
以下に、内部表現としてリストを用いる、素朴な実装を示します。
import collections
class Range(collections.abc.Sequence):
def __init__(self, start, stop, step):
self._l = []
i = start
while i < stop:
self._l.append(i)
i += step
def __getitem__(self, i):
return self._l[i]
def __len__(self):
return len(self._l)
for i in Range(0, 100, 3):
print(i, end=' ')
0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99
for文で利用できていることから、最低限の機能は提供できていることがわかります。
空間計算量
しかし、このような素朴な実装は、空間計算量の点で問題があります。tracemallocのドキュメントを参考に、メモリ使用量を調べた結果が以下です。
y = Range(0, 1000, 1)
Top 10 lines
#1: <ipython-input-1-710c4331c126>:9: 20.3 KiB
i += step
#2: <ipython-input-1-710c4331c126>:8: 8.8 KiB
self._l.append(i)
#3: <ipython-input-1-710c4331c126>:48: 0.5 KiB
y = Range(0, 1000, 1)
Total allocated size: 30.9 KiB
y = Range(0, 10000, 1)
Top 10 lines
#1: <ipython-input-1-d724d7549469>:9: 266.4 KiB
i += step
#2: <ipython-input-1-d724d7549469>:8: 85.5 KiB
self._l.append(i)
#3: <ipython-input-1-d724d7549469>:48: 0.5 KiB
y = Range(0, 10000, 1)
Total allocated size: 353.7 KiB
y = Range(0, 10000, 1)
Top 10 lines
#1: <ipython-input-1-e1c2fdd7f6ec>:9: 2727.3 KiB
i += step
#2: <ipython-input-1-e1c2fdd7f6ec>:8: 805.1 KiB
self._l.append(i)
#5: <ipython-input-1-e1c2fdd7f6ec>:48: 0.5 KiB
y = Range(0, 100000, 1)
Total allocated size: 3536.3 KiB
Rangeの長さの分だけ、メモリ使用量が線形に増えていることがわかります。しかし、『Pythonチュートリアル 第3版』p.25に記載があるように、本家rangeはこのような性質を見せません。（注：Python3の話。）
range()関数が返すオブジェクトはさまざまな意味でリストのように振舞うが、実はlistではない。反復を掛けることで望みのシーケンスのアイテムを連続的に返すオブジェクトであり、本当にはリストを作らず、それにより空間を節約する。
ならば、Rangeも、内部表現としてリストを用いずに、実装してみることにしましょう。
Range（仮）
あれこれ考えつつ、実装していきました。以下を参考にしています。
- rangeのドキュメント
- collections.abc.Sequenceのドキュメント
- EQUALLY-SPACED NUMBERS (LINSPACE) (PYTHON RECIPE)
- Djexus氏による実装
- dcrosta氏による実装
- 本家rangeの実装
import collections
import numbers
class Range(collections.abc.Sequence):
def __init__(self, *args):
if len(args) == 0:
raise TypeError('Range expected 1 arguments, got 0')
elif len(args) > 3:
raise TypeError('Range expected at most 3 arguments,'
f' got {len(args)}')
else:
cargs = ()
for arg in args:
if isinstance(arg, numbers.Integral):
cargs += (arg,)
elif hasattr(arg, '__index__'):
cargs += (arg.__index__(),)
else:
raise TypeError(f"'{type(arg).__name__}' object "
"cannot be interpreted as an integer")
if len(cargs) == 1:
self.start, self.stop, self.step = 0, cargs[0], 1
elif len(cargs) == 2:
self.start, self.stop, self.step = cargs[0], cargs[1], 1
else:
self.start, self.stop, self.step = cargs
if self.step == 0:
raise ValueError('Range() arg 3 must not be zero')
self._len = max(0,
((self.stop - self.start) // self.step)
+ bool((self.stop - self.start) % self.step))
def __len__(self):
return self._len
def __getitem__(self, i):
if isinstance(i, slice):
result = Range(*(i.indices(self._len)))
elif isinstance(i, numbers.Integral):
if not (-self._len <= i < self._len):
raise IndexError('Range object index out of range')
else:
if i < 0:
i += self._len
result = self.start + self.step * i
else:
raise TypeError('Range indices must be integers or slices, '
f'not {type(i).__name__}')
return result
def __bool__(self):
return bool(self._len)
def __repr__(self):
if self.step == 1:
result = f'Range({self.start}, {self.stop})'
else:
result = f'Range({self.start}, {self.stop}, {self.step})'
return result
def __eq__(self, other):
if not isinstance(other, Range):
return False
return (self.start, self.stop, self.step) == (other.start, other.stop, other.step)
def __ne__(self, other):
return not self == other
def __hash__(self):
return hash((type(self), self.start, self.stop, self.step))
完全コピーを目指すため、実装が長くなっていますが、ポイントは、内部表現としてリストを用いずとも、__len__と__getitem__を実装できている、という点です。
内部表現としてリストを用いていないので、空間計算量の弱点はなくなっています。
y = Range(0, 1000, 1)
Top 10 lines
#1: <ipython-input-1-06cb9d8f21e6>:104: 0.5 KiB
y = Range(0, 1000, 1)
Total allocated size: 2.7 KiB
y = Range(0, 10000, 1)
Top 10 lines
#1: <ipython-input-1-251c447f8869>:104: 0.5 KiB
y = Range(0, 10000, 1)
Total allocated size: 2.7 KiB
y = Range(0, 100000, 1)
Top 10 lines
#1: <ipython-input-1-f98ef2fc9091>:104: 0.5 KiB
y = Range(0, 100000, 1)
Total allocated size: 2.7 KiB
時間計算量
それでは、時間計算量についてはどうでしょうか。最後尾の要素のインデクスを取得する場合の計算量（最悪計算量）を、本家rangeと比較してみましょう。
import range_proto as rp
num = 100000
x1 = range(num)
x2 = rp.Range(num)
print('比較：インデクス取得')
%timeit x1.index(num - 1)
%timeit x2.index(num - 1)
比較：インデクス取得
242 ns ± 2.12 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
149 ms ± 494 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
62万倍ほど遅いことがわかります。これについては、コレクションの抽象基底クラスのドキュメントに記載のとおり、index()等のmixinメソッドが、__getitem__()メソッドを繰り返し呼び出すことが原因です。その結果、__getitem__()が定数時間で実装されていても、mixinメソッドは、線形時間で動いてしまうのです。タダほど高いものはないとは、まさにこのことでしょうか。
以下に、__getitem__()の呼び出し回数をカウントする、簡単な例を示します。
import collections
class Range(collections.abc.Sequence):
def __init__(self, *args):
self.start, self.stop, self.step = args
self._len = max(0,
((self.stop - self.start) // self.step)
+ bool((self.stop - self.start) % self.step))
self.counter = 0
def __len__(self):
return self._len
def __getitem__(self, i):
self.counter += 1
result = self.start + self.step * i
return result
x = Range(0, 100000, 1)
print(x.counter)
x.index(100000 - 1)
print(x.counter)
0
100000
先頭から末尾まで走査している様が目に浮かびます。これでは性能も出ません。
Range
以上の弱点を克服するには、タダでついてきたmixinメソッドを、実装してやります。
def __iter__(self):
i = self.start
while (self.step > 0 and i < self.stop) or (self.step < 0 and i > self.stop):
yield i
i += self.step
def __reversed__(self):
stop = self.start - self.step
i = stop + self._len * self.step
step = -self.step
while (step > 0 and i < stop) or (step < 0 and i > stop):
yield i
i += step
def __contains__(self, n):
if self.step > 0:
inRange = self.start <= n < self.stop
elif self.step < 0:
inRange = self.start >= n > self.stop
hasSameMod = n % self.step == self.start % self.step
return inRange and hasSameMod
def count(self, n):
return int(self.__contains__(n))
def index(self, n):
if self.__contains__(n):
result = (n - self.start) // self.step
else:
raise ValueError(f'{n} is not in range')
return result
『Hello. 何？ …最初からそういえばいいのよ。それと敬語変だから。日本人としてそれじゃぁ恥ずかしいわよ？あと、電話レンジが（仮）っていうのもいい加減…』
ということで、Rangeの仮を外しましょう。一応、unittestもOKでしたので。Range本体とテストケースのソースはこちらです。
性能測定
以下を比較します。本家に勝てるとは思っていませんが、比較のためにお出まし願いましょう。
- 本家range
- 内部表現にリストを用いる実装（※）
- Range（仮）
- Range
※「素朴な実装」に対し、unittest（test_large_nums以外）をパスする程度に実装を加えたもの。mixinメソッドは未実装。
import range_list as rl
import range_proto as rp
import range as r
num = 100000
x1 = range(num)
x2 = rl.Range(num)
x3 = rp.Range(num)
x4 = r.Range(num)
print('比較1：イテレーション')
%timeit for _ in x1: pass
%timeit for _ in x2: pass
%timeit for _ in x3: pass
%timeit for _ in x4: pass
print('------')
print('比較2：リバース＋イテレーション')
%timeit for _ in reversed(x1): pass
%timeit for _ in reversed(x2): pass
%timeit for _ in reversed(x3): pass
%timeit for _ in reversed(x4): pass
print('------')
print('比較3：含むか')
%timeit (num - 1) in x1
%timeit (num - 1) in x2
%timeit (num - 1) in x3
%timeit (num - 1) in x4
print('------')
print('比較4：カウント')
%timeit x1.count(num - 1)
%timeit x2.count(num - 1)
%timeit x3.count(num - 1)
%timeit x4.count(num - 1)
print('------')
print('比較5：インデクス取得')
%timeit x1.index(num - 1)
%timeit x2.index(num - 1)
%timeit x3.index(num - 1)
%timeit x4.index(num - 1)
比較1：イテレーション
2.25 ms ± 59.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
122 ms ± 1.13 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
150 ms ± 1.48 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
22.1 ms ± 214 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
------
比較2：リバース＋イテレーション
2.06 ms ± 23.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
118 ms ± 455 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
146 ms ± 322 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
13.6 ms ± 48.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------
比較3：含むか
147 ns ± 0.278 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
126 ms ± 4.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
152 ms ± 587 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
565 ns ± 4.28 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
------
比較4：カウント
194 ns ± 0.587 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
125 ms ± 480 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
152 ms ± 427 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
792 ns ± 4.14 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
------
比較5：インデクス取得
239 ns ± 2.08 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
121 ms ± 359 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
148 ms ± 303 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
834 ns ± 1.62 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
ナノ（n）の1,000倍がマイクロ（μ）、マイクロの1,000倍がミリ（m）です。こうして見ると、やはり本家には勝てませんが、mixinメソッドを実装した効果はあったようです。
なお、比較2でイテレーションまでしているのは、リバースだけだと、ジェネレータのたぐいを返すだけで、性能の違いが見えなかったためです。
まとめ
実装（アルゴリズム）次第で計算量が大きく変わることを、改めて確認できました。よく、時間と空間のトレードオフと言いますが、rangeは言うなれば「等差リスト」であり、リストよりも狭い（リストに含まれる）概念です。よって、空間と時間の、両方の計算量を減らすことができたのだと思います。
そして、やってみて思ったのですが、いい勉強になりました。この課題には、いろんな要素が含まれるので。
- 基本処理（順次進行、条件分岐、繰り返し）
- オブジェクト指向
- イテレータ、ジェネレータ
- スライシング
- 計算量とアルゴリズム
- メモリ使用量、処理時間の計測方法
- 可変長引数、パッキング／アンパッキング
- CPython
- unittest
- 大きい数の取り扱い
- 例外処理
もし、あなたがPythonのOJT担当なら、課題の1ページに加えるとよいかもしれません。