Pythonのrange関数の再実装と計算量について

Pythonのrange関数は、繰り返しを可能にする重要な仕組みです。この記事では、range関数の再実装とその計算量について詳しく見ていきましょう。

range関数の再実装

まず、range関数の素朴な実装を見てみましょう。この実装では、内部表現としてリストを使用しています。

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

しかし、この実装は空間計算量の観点から問題があります。Rangeの長さの分だけ、メモリ使用量が線形に増えてしまいます。これは、range関数の本来の性質を満たしていません。

range関数の改良

次に、内部表現としてリストを使用せずにrange関数を再実装してみましょう。

import collections
import numbers

class Range(collections.abc.Sequence):
    def __init__(self, *args):
        # 省略
        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):
        # 省略
        result = self.start + self.step * i
        return result

この実装では、Rangeの長さに関わらず、メモリ使用量が一定に保たれます。これにより、range関数の本来の性質が満たされています。

以上、Pythonのrange関数の再実装とその計算量について見てきました。この知識を活かして、Pythonの理解を深めていきましょう。.