Python: линейный __getitem__ для пары списков списков

Хотя ваша реализация хороша, я хотел бы поделиться своим собственным способом итерации с использованием chain.from_iterable. Потому что в основном мы цепляем элементы, будь то в начале или в конце.

Для одного списка:

Единственная часть, которая нуждается в объяснении, это map(reversed, reversed(self.instructions)). Нам нужно перевернуть не только весь список, но и отдельные подсписки.

from itertools import chain

class MyClass:
    def __init__(self):
        self.instructions = [
            [0, 1, 2],
            [3, 4, 5, 6],
            [7, 8],
        ]

    def __getitem__(self, ind):
        if ind >= 0:
            chunks = self.instructions
            range_parameter = ind + 1
        else:
            chunks = map(reversed, reversed(self.instructions))
            range_parameter = abs(ind)

        iterator = chain.from_iterable(chunks)

        try:
            for _ in range(range_parameter):
                n = next(iterator)
        except StopIteration:
            raise IndexError("index out of range")

        return n

x = MyClass()
print(x[5])
print(x[-5])

Для двух списков:

Поскольку вы сказали, что нам нужно колебаться, zip — правильный инструмент для этого. Когда ind положительный, все просто. Мы заархивируем их и используем chain.from_iterable два раза, потому что в противном случае это дает нам отдельные подсписки.

Если ind отрицательное, нам нужно два reversed() перед сжатием. Один для внешних списков и один для подсписков.

from itertools import chain

class MyClass:
    def __init__(self):
        self.instructions = [
            [0, 1, 2],
            [5, 6, 7, 8],
            [12, 13],
        ]

        self.annotations = [
            [3, 4],
            [9, 10, 11],
            [14, 15, 16],
        ]

    def __getitem__(self, ind):
        if ind >= 0:
            chunks = zip(self.instructions, self.annotations)
            range_parameter = ind + 1
        else:
            chunks = zip(
                map(reversed, reversed(self.annotations)),
                map(reversed, reversed(self.instructions)),
            )
            range_parameter = abs(ind)

        iterator = chain.from_iterable(chain.from_iterable(chunks))

        try:
            for _ in range(range_parameter):
                n = next(iterator)
        except StopIteration:
            raise IndexError("index out of range")

        return n

x = MyClass()
print(x[9])
print(x[-4])

Вот мой подход:

import itertools


class NewClass:
    def __init__(self):
        #
        self.instructions = []
        self.annotations = []

        # for demo purposes
        self.instructions.append([0, 1, 2])
        self.instructions.append([5, 6, 7, 8])
        self.instructions.append([12, 13])
        
        self.annotations.append([3, 4])
        self.annotations.append([9, 10, 11])
        self.annotations.append([14, 15, 16])
        
    def __iter__(self):
        zipped = itertools.zip_longest(self.instructions, self.annotations, fillvalue=[])
        for sub_lists in zipped:
            yield from itertools.chain.from_iterable(sub_lists)

    def __getitem__(self, key):
        flat = list(self)
        return flat[key]

Примечания

• Я создал метод __iter__, который позволяет вызывающему объекту перебирать объект следующим образом:

    x = NewClass()
    for e in x:
        print(e)
  

• __getitem__ построен на __iter__

• О данных zipped: концептуально вы можете рассматривать это как

    [
        [[0, 1, 2], [3, 4]],          # This is a sub_lists
        [[5, 6, 7, 8], [9, 10, 11]],  # a sub_lists
        ...
    ]
  

• Выражение itertools.chain.from_iterable(sub_lists) в основном сглаживает sub_lists от [[0, 1, 2], [3, 4]] до [0, 1, 2, 3, 4]

• Это решение работает для произвольного количества списков, а не только для 2.

Обновлять

Я исправил __getitem__ для обработки отрицательного индекса за счет производительности. Мне лень создавать более эффективное решение.

Если два объединенных списка имеют одинаковый размер, вы можете использовать что-то вроде этого:

div, mod = divmod(ind, 2)
if mod:
    return get_item(second_list, div)
else:
    return get_item(first_list, div)

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

import itertools
import bisect

class Index:
    def __init__(self,ll):
        self.ll = ll
        self.oo = list(itertools.accumulate(map(len,ll), initial=0))

    def __getitem__(self, i):
        if i < 0:
            i += self.oo[-1]
        j = bisect.bisect(self.oo,i)
        if not 0 < j <= len(self.ll):
            raise IndexError
        return self.ll[j-1][i-self.oo[j-1]]

    def __iter__(self):
        return itertools.chain.from_iterable(self.ll)

# Example:
i = Index(
  [[9,1,7],
   [3,0],
   [],
   [4,4,4,2]]
)
assert i[4]==0 and i[8]==2

j-1 потому, что начальный 0 приводит к тому, что i из 0 назначается точка вставки 1. Вы можете опустить ,initial=0 (и фактически последний элемент self.oo) за счет более сложного кода для края/ошибки случаи. __iter__ предоставляется, потому что он асимптотически быстрее, чем индексация с последовательными целыми числами, каждое из которых должно подвергаться бинарному поиску, даже если обычно будет найден один и тот же подсписок.

Очевидно, расширение этого для поддержки чередования двух списков (одинаковой длины) тривиально: суммируйте чередующиеся длины, а затем используйте divmod(j-1,2), чтобы получить индекс в списке и выбор между двумя списками (соответственно).

вот моя идея, для версии 2 списка

сначала мы определяем функцию для переключения между списками

from itertools import zip_longest

def alternate(*iterables: "list[list[Any]]") -> "Iterator[list[Any]]":
    for group in zip_longest(*iterables):
        for it in group:
            if it is not None:
                yield it
            

как это может чередоваться между любым количеством ваших списков

теперь для класса

class MyClass:
    def __init__(self):
        self.instructions = [
            [0, 1, 2],
            [5, 6, 7, 8],
            [12, 13],
        ]

        self.annotations = [
            [3, 4],
            [9, 10, 11],
            [14, 15, 16],
        ]
        
    def __len__(self):
        return sum(map(len,alternate(self.instructions, self.annotations)))
    
    def __getitem__(self, index:int ):
        size = len(self)
        if index >= 0:
            if index >= size:
                raise IndexError(index)
        else:
            new_index = size + index
            if 0 <= new_index < size:
                index = new_index
            else:
                raise IndexError(index)
        for item in alternate(self.instructions, self.annotations):
            n = len(item)
            if 0 <= index < n:
                return item[index]
            index -= n
        raise RuntimeError("this should not happens")

test = MyClass()
print(test[9])
print(test[-4])

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

После этого и с учетом того, что подсписок не имеет одинакового размера, тогда просто идет цикл для каждого из подсписков, и если индекс попадает в его диапазон, возвращаемый, который в противном случае вычитает размер этого подсписка и переходит к следующему .

и поскольку python такой крутой, вы получаете бесплатно, что ваш класс является итерируемым (просто имея и __getitem__, которые принимают межэлементные значения) и обратимым (также имея __len__)

>>> list(test)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> list(reversed(test))
[16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

в качестве альтернативы вы можете использовать n-й рецепт

from itertools import islice
   
def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)   

(или из more_itertools сторонней библиотеки)

а затем вместе с itertools.chain вы можете изменить последний цикл в getitem для return nth(chain.from_iterable(alternate(self.instructions, self.annotations)), index), учитывая, что мы уже проверяем, попадает ли индекс в диапазон