python - 如何在Python中实现动态序列(例如 "geometric range")？

Question

Python range 是一个有趣的对象，因为它在内存方面的行为类似于生成器，但在其他方面它的行为类似于序列，并且它还具有 O(1) in 操作、.index() 和 .count() 的时间复杂度。

这是动态序列的示例，即 Sequence不将其元素存储在内存中的对象。

如何在 Python 中实现动态序列？

in 操作、.index() 和 .count 方法在 O(1) 时间内实现，当然，这是一个很好的补充。

<小时/>

为了具体起见，让我们考虑 Geometric sequence 的情况:

s_k = a * r ** k

其中k是一个整数。

显然，不能简单地使用生成器(简化的)，例如:

def geom_seq(a, r, start, stop=None):
    if stop is None:
        start, stop = 0, start
    else:
        start, stop = start, stop
    item = a * r ** start
    for _ in range(start, stop):
        yield item
        item *= r

因为这虽然具有内存效率，但其行为不会像序列，例如:

a = geom_seq(1, 2, 8)

len(a)
# TypeError...

list(a)
# [1, 2, 4, 8, 16, 32, 64, 128]
list(a)  # generator is consumed...
# []

相反，类似:

a = tuple(geom_seq(1, 2, 8))

将是(类似)一个序列，但内存效率不高:

import sys


print(sys.getsizeof(geom_seq(1, 2, 1000)))
# 88
print(sys.getsizeof(tuple(geom_seq(1, 2, 1000))))
# 8048

<小时/>

编辑

这不是 How to implement a minimal class that behaves like a sequence in Python? 的重复项因为那里没有讨论时间/内存考虑因素。

Answer 1

几何序列的简化实现(其值未存储在内部)如下所示:

import collections.abc
import math


class GeomRange(collections.abc.Sequence):
    def __init__(self, a, r, start, stop=None):
        self.a = a
        self.r = r
        if stop is None:
            start, stop = 0, start
        self.k = range(start, stop, 1)

    def __getitem__(self, i):
        if isinstance(i, int):
            if i < 0:
                i += len(self)
            if i in self.k:
                return self.a * self.r ** (self.k.start + i)
            else:
                raise IndexError
        elif isinstance(i, slice):
            sliced = self.k[i]
            return type(self)(self.a, self.r, sliced.start, sliced.stop)

    def __len__(self):
        return len(self.k)

    def __contains__(self, item):
        r_k = item / self.a
        if r_k > 0:
            k = math.log2(r_k) / math.log2(self.r)
            if math.isclose(k % 1, 1.0):
                k = int(k)
        else:
            k = None
        return k in self.k

    def __iter__(self):
        item = self.a * self.r ** self.k.start
        for _ in self.k:
            yield item
            item *= self.r

    def __reversed__(self):
        item = self.a * self.r ** (self.k.stop - 1)
        for _ in reversed(self.k):
            yield item
            item //= self.r

    def index(self, item):
        r_k = item / self.a
        if r_k > 0:
            k = math.log2(r_k) / math.log2(self.r)
            if math.isclose(k % 1, 1.0):
                k = int(k)
        else:
            k = None
        return self.k.index(k)


    def count(self, item):
        if item in self:
            return 1
        else:
            raise ValueError

    def __str__(self):
        return f'Geom[{self.a}, {self.r}]-{self.k}'

    __repr__ = __str__

请注意，上述代码不一定能很好地处理所有极端情况。 例如，它假设 a 和 r 为非负 ints。

该对象的行为本质上类似于range()，但会产生几何级数:

a = GeomRange(1, 2, 8)
print(a)
# Geom[1, 2]-range(0, 8)
print(len(a))
# 8

print(list(a))
# [1, 2, 4, 8, 16, 32, 64, 128]
print(list(a))
# [1, 2, 4, 8, 16, 32, 64, 128]
print(list(reversed(a)))
# [128, 64, 32, 16, 8, 4, 2, 1]

print(a[2], a[-2])
# 4 64

print((a[:2]), (a[2:]))
# Geom[1, 2]-range(0, 2) Geom[1, 2]-range(2, 8)
print((a[:-2]), (a[-2:]))
# Geom[1, 2]-range(0, 6) Geom[1, 2]-range(6, 8)
print(list(a[:2]), list(a[2:]))
# [1, 2] [4, 8, 16, 32, 64, 128]
print(list(a[:-2]), list(a[-2:]))
# [1, 2, 4, 8, 16, 32] [64, 128]

print((a[:10]), (a[10:]))
# Geom[1, 2]-range(0, 8) Geom[1, 2]-range(8, 8)
print((a[:-10]), (a[-10:]))
# Geom[1, 2]-range(0, 0) Geom[1, 2]-range(0, 8)
print(list(a[:10]), list(a[10:]))
# [1, 2, 4, 8, 16, 32, 64, 128] []
print(list(a[:-10]), list(a[-10:]))
# [] [1, 2, 4, 8, 16, 32, 64, 128]

print(a.index(4))
# 2
print(a.count(8))
# 1

print(all((
    0 not in a,
    1 in a,
    128 in a,
    256 not in a,
    2 in a,
    3 not in a,
    1.99999999 not in a)))
# True

尽可能使用O(1)操作，例如:

%timeit 2 ** 100 in GeomRange(1, 2, 1000)
# 100000 loops, best of 3: 4.7 µs per loop
%timeit 2 ** 100 in GeomRange(1, 2, 1000000)
# 100000 loops, best of 3: 4.68 µs per loop

同时仍然具有内存效率，例如:

import sys


print(sys.getsizeof(GeomRange(1, 2, 1000)))
# 56
print(sys.getsizeof(tuple(GeomRange(1, 2, 1000))))
# 8048

<小时/>

迭代时，所有这些机制的速度代价是几个百分点，例如:

%timeit tuple(GeomRange(1, 2, 10000))
# 100 loops, best of 3: 3.47 ms per loop
%timeit tuple(geom_seq(1, 2, 10000))
# 100 loops, best of 3: 3.18 ms per loop