Получение плоского представления вложенного списка

Вам нужно будет создать класс, содержащий ссылку на исходные списки.

Вам не нужны копии списков, вам просто нужна ссылка. Этот класс знает, как получить доступ и обновить значения в каждом из своих списков.

Вы можете получить доступ к любому элементу списка со сложностью поиска O(log n) (двоичный поиск) без использования дополнительной памяти для хранения плоского списка.

Выполнение

Импорт следующих типов:

from typing import Any, Callable, Iterable, List, Tuple, Union

Если вы хотите, чтобы представление прослушивало изменения в базовых списках, вам нужно будет создать ListWrapper, который может делегировать базовому списку и уведомлять представление об изменениях в списках.

Мы хотим быть уверены, что self._notify() вызывается при каждом изменении списка.

class ListWrapper:
    def __init__(self, lst: List[Any]):
        self._list: List[Any] = lst
        self.callbacks: List[Callable[[], None]] = []

    def __getitem__(self, index: int) -> Any:
        return self._list[index]

    def __setitem__(self, index: int, value: Any) -> None:
        self._list[index] = value
        self._notify()

    def __len__(self) -> int:
        return len(self._list)

    def append(self, item: Any) -> None:
        self._list.append(item)
        self._notify()

    def extend(self, iterable: Iterable[Any]) -> None:
        self._list.extend(iterable)
        self._notify()

    def insert(self, index: int, item: Any) -> None:
        self._list.insert(index, item)
        self._notify()

    def remove(self, item: Any) -> None:
        self._list.remove(item)
        self._notify()

    def pop(self, index: int = -1) -> Any:
        item = self._list.pop(index)
        self._notify()
        return item

    def clear(self) -> None:
        self._list.clear()
        self._notify()

    def _notify(self) -> None:
        for callback in self.callbacks:
            callback()

    def add_callback(self, callback: Callable[[], None]) -> None:
        self.callbacks.append(callback)

Вот класс, который обеспечивает «плоское представление» нескольких списков, где обновления исходных списков отражаются в плоском представлении.

class FlatView:
    def __init__(self, lists: List[ListWrapper]) -> None:
        self.lists = lists
        self.update_lengths()
        for lst in self.lists:
            lst.add_callback(self.update_lengths)

    def update_lengths(self) -> None:
        self.sub_lengths = self._compute_overall_length()

    def _compute_overall_length(self) -> List[int]:
        lengths = [0]
        for lst in self.lists:
            lengths.append(lengths[-1] + len(lst))
        return lengths

    def __getitem__(self, index: int) -> Any:
        if index < 0 or index >= len(self):
            raise IndexError("list index out of range")
        list_index = self._find_list_index(index)
        sublist_index = index - self.sub_lengths[list_index]
        return self.lists[list_index][sublist_index]

    def _find_list_index(self, index: int) -> int:
        # Binary search to find the list that contains the index
        low, high = 0, len(self.sub_lengths) - 1
        while low < high:
            mid = (low + high) // 2
            if self.sub_lengths[mid] <= index < self.sub_lengths[mid + 1]:
                return mid
            elif index < self.sub_lengths[mid]:
                high = mid
            else:
                low = mid + 1
        return low

    def __len__(self) -> int:
        return self.sub_lengths[-1]

    def __repr__(self) -> str:
        return repr([item for lst in self.lists for item in lst])

Применение

Следующая функция-обертка создает экземпляр FlatView для предоставленного списка списков.

Мы заключаем каждый список в ListWrapper, чтобы можно было присоединить функцию обратного вызова для обновления общей длины представления, используемой для доступа к данным.

def flat_view(lists: List[List[Any]]) -> Tuple[FlatView, List[ListWrapper]]:
    wrappers = [ListWrapper(lst) for lst in lists]
    return FlatView(wrappers), wrappers

Вот как вы бы это использовали. Обратите внимание, что нам нужно изменить оболочки представления, чтобы понять, как изменяются списки.

Например, b[0] = "x" не будет работать.

if __name__ == "__main__":
    a = ["a", "b", "c"]
    b = ["d", "e", "f"]
    view, [a_wrapper, b_wrapper] = flat_view([a, b])
    
    print(view)                # Output: ['a', 'b', 'c', 'd', 'e', 'f']
    
    b_wrapper[0] = "x"
    print(view)                # Output: ['a', 'b', 'c', 'x', 'e', 'f']
    
    print(view[3], len(view))  # Output: 'x' 6
    
    a_wrapper.append("y")
    print(view, len(view))     # Output: ['a', 'b', 'c', 'y', 'x', 'e', 'f'] 7

    print(a, len(a))           # Output: ['a', 'b', 'c', 'y'] 4
    print(b, len(b))           # Output: ['x', 'e', 'f'] 3

Вы можете написать генератор, который выравнивает содержащуюся в нем структуру. Это отразит все изменения в структуре и будет вести себя так, как вам нужно.

class FlatView:
    def __init__(self, sequence):
        self.sequence = sequence
    def __iter__(self):
        yield from FlatView.flatten(self.sequence)
    @staticmethod
    def flatten(item):
        for i in item:
            if hasattr(i, '__iter__') and not isinstance(i, str):
                yield from FlatView.flatten(i)
            else:
                yield i
    
a = ["a", "b", "c"]
b = ["d", "e", "f"]
c = [a,b]
view = FlatView(c)
print(list(view)) # ['a', 'b', 'c', 'd', 'e', 'f']
b[0] = "x"
print(list(view)) # ['a', 'b', 'c', 'x', 'e', 'f']
c.append(["g", "h", "i"])
print(list(view)) # ['a', 'b', 'c', 'x', 'e', 'f', 'g', 'h', 'i']
print(c)          # [['a', 'b', 'c'], ['x', 'e', 'f'], ['g', 'h', 'i']]

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

from collections.abc import Sequence

def generate_refs(nested, prefix):
    for i, value in enumerate(nested):
        idx = prefix + [i] 
        if isinstance(value, Sequence) and not isinstance(value, str):
            yield from generate_refs(value, idx)
        else:
            yield idx 

class FlatView:
    def __init__(self, nested):
        self._nested = nested

    def __getitem__(self, n): 
        if not isinstance(n, int):
            raise TypeError("integer indices only")
        if n < 0:
            raise IndexError("negative indices not supported")
        gen = generate_refs(self._nested, [])
        try:
            for _ in range(n+1):
                ref = next(gen)
        except StopIteration:
            raise IndexError("index out of range") from None
        # print(f"debug: position [{n}]: {ref}")
        value = self._nested
        for i in ref:
            value = value[i]
        return value

a = ["a", "b", "c"]
b = ["d", "e", "f"]
test = [a, [b, "g", "h"], "i"]

fw = FlatView(test)
print("nested:", test)
print("flattened:", list(fw))
print("item [5]:", fw[5])
a.extend(["c2", "c3"]) ; print("extended the list 'a'")
print("item [5]:", fw[5])

Выход:

nested: [['a', 'b', 'c'], [['d', 'e', 'f'], 'g', 'h'], 'i']
flattened: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
item [5]: f
extended the list 'a'
item [5]: d