Собственные последовательности в Python: от теории к практике

Расширенные примеры реализации последовательностей

Последовательность с поддержкой срезов и отрицательных индексов

В следующем примере класс SequenceWithSlice обрабатывает объект slice в методе __getitem__ и корректно работает с отрицательными индексами.

class SequenceWithSlice:
    def __init__(self, items):
        self._items = list(items)

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

    def __getitem__(self, index):
        if isinstance(index, slice):
            # обрабатываем срез
            start, stop, step = index.indices(len(self._items))
            return [self._items[i] for i in range(start, stop, step)]
        elif isinstance(index, int):
            # поддерживаем отрицательные индексы
            if index < 0:
                index += len(self._items)
            if index < 0 or index >= len(self._items):
                raise IndexError('list index out of range')
            return self._items[index]
        else:
            raise TypeError('indices must be integers or slices')

seq = SequenceWithSlice([10, 20, 30, 40, 50])
print(seq[1:4])        # срез
print(seq[-1])         # последний элемент
print(seq[::2])        # каждый второй

[20, 30, 40]
50
[10, 30, 50]

Ленивая последовательность с кэшированием

Реализация последовательности, которая генерирует элементы по требованию (например, из итератора) и кэширует уже полученные значения. Это полезно для дорогостоящих вычислений или бесконечных последовательностей.

class LazySequence:
    def __init__(self, iterable):
        self._iter = iter(iterable)
        self._cache = []

    def __len__(self):
        # подгружаем все оставшиеся элементы для корректной длины
        try:
            while True:
                self._cache.append(next(self._iter))
        except StopIteration:
            pass
        return len(self._cache)

    def __getitem__(self, index):
        if isinstance(index, slice):
            # для среза сначала подгружаем нужные элементы
            start, stop, step = index.indices(10**9)  # условно большой лимит
            while len(self._cache) <= max(start, stop):
                try:
                    self._cache.append(next(self._iter))
                except StopIteration:
                    break
            return [self._cache[i] for i in range(start, stop, step) if i < len(self._cache)]
        if isinstance(index, int):
            if index < 0:
                # для отрицательных индексов загружаем все
                self.__len__()
                return self._cache[index]
            while len(self._cache) <= index:
                try:
                    self._cache.append(next(self._iter))
                except StopIteration:
                    raise IndexError('list index out of range')
            return self._cache[index]
        raise TypeError

def generate():
    for i in range(10):
        yield i

lazy = LazySequence(generate())
print(lazy[2])      # 2, загрузились элементы до индекса 2
print(lazy[5])      # 5, загрузились ещё
print(lazy[0])      # 0, уже в кэше
print(lazy[1:4])    # [1, 2, 3]

2
5
0
[1, 2, 3]

Последовательность на основе односвязного списка

Реализация неизменяемой последовательности, где данные хранятся в узлах односвязного списка. Метод __getitem__ проходит по цепочке до нужного индекса.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class LinkedListSeq:
    def __init__(self, head=None):
        self._head = head
        self._length = 0
        # подсчет длины при инициализации
        cur = head
        while cur:
            self._length += 1
            cur = cur.next

    def __len__(self):
        return self._length

    def __getitem__(self, index):
        if index < 0:
            index += self._length
        if index < 0 or index >= self._length:
            raise IndexError('list index out of range')
        cur = self._head
        for _ in range(index):
            cur = cur.next
        return cur.value

# создание списка: 10 -> 20 -> 30
tail = Node(30)
middle = Node(20, tail)
head = Node(10, middle)
lst = LinkedListSeq(head)
print(len(lst))   # 3
print(lst[1])     # 20
for val in lst:
    print(val, end=' ')

3
20
10 20 30