如何在 Python 中实现动态序列（例如 "geometric range"）？

Question

A Python range 是一个有趣的对象，因为它在内存方面表现得像一个生成器，但在其他方面表现得像一个序列，而且它还具有 O(1) 时间复杂度对于 in 操作，.index() 和 .count().

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

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

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

为了具体起见，让我们考虑 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

因为这样，虽然内存效率高，但不会表现得像 Sequence，例如：

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

将是（喜欢）一个 Sequence 但内存效率不高：

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

如何在 Python 中实现动态序列（例如 "geometric range"）？

How to implement a dynamic sequence in Python (e.g. a "geometric range")?

python

range

sequence

编辑