Как реализовать динамическую последовательность в Python (например, «геометрический диапазон»)? - PullRequest
Новая
       37

Как реализовать динамическую последовательность в Python (например, «геометрический диапазон»)?

1 голос
/ 28 октября 2019

Python range - интересный объект, потому что он ведет себя как генератор, когда дело доходит до памяти, но в остальном он ведет себя как последовательность и дополнительно имеет O(1) временную сложность для операции in, .index() и.count().

Это пример динамической последовательности, то есть объекта Sequence, который не хранит свои элементы в памяти.

Как реализоватьдинамическая последовательность в Python?

Операция in, методы .index() и .count, реализованные за O(1) время, были бы, конечно, хорошим дополнением.

Для конкретности рассмотрим случай Геометрическая последовательность : 

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, но не будет эффективным использованием памятиent: 

import sys


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

EDIT

Это не дубликат Как реализовать минимальный класс, который ведет себя как последовательность в Python? как время /вопросы памяти здесь не обсуждаются.

1 Ответ

1 голос
/ 28 октября 2019

Упрощенная реализация геометрической последовательности со значениями, не сохраненными внутри, будет выглядеть следующим образом: 

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 неотрицательны int с.

Этот объект будет вести себя по существу как 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
...