Структура данных Python для индексируемого списка строк

Question

Я получил список объектов, которые выглядят как строки, но не являются реальными строками (подумайте о файлах mmap).Например:

x = [ "abc", "defgh", "ij" ]

Я хочу, чтобы x был непосредственно индексируемым, как если бы это была большая строка, например:

(x[4] == "e") is True

(Конечно, я не хочуdo "" .join (x), который объединит все строки, потому что чтение строки слишком дорого в моем случае. Помните, что это файлы mmap.).

Это легко, если вы перебираете весь список, но, похоже, O (n).Поэтому я реализовал __getitem__ более эффективно, создав такой список:

x = [ (0, "abc"), (3, "defgh"), (8, "ij") ]

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

Я вижу, как реализовать __setitem__, но это кажется таким скучным, мне интересно, нет ли чего-то, что уже делает это.

Чтобы быть более точным, вот как должна соответствовать структура данных __setitem__:

>>> x = [ "abc", "defgh", "ij" ]
>>> x[2:10] = "12345678"
>>> x
[ "ab", "12345678", "j" ]

Я бы подумал о реализации такой структуры данных, имени или любой подсказке.

Answer 1

То, что вы описываете, является частным случаем структуры данных веревки .

К сожалению, я не знаю ни о каких реализациях Python.

Answer 2

Я не знаю ничего, что делает то, что вы хотите.

Однако, если вы реализовали __getitem__ эффективно, как вы говорите, то у вас уже есть код, который сопоставляет индекс с вашимкортеж, список строк.Поэтому кажется, что вы могли бы просто повторно использовать этот фрагмент кода - с небольшим рефакторингом - для реализации __setitem__, который нуждается в той же информации для выполнения своей функции.

Answer 3

Это может быть начало:

self._h = {0:"abc", 3:"defgh", 8:"ij"} #create _h and __len__ in __init__
self.__len__ = 10

def __getitem__(i):
    if i >= self.__len__:
        raise IndexError
    o=0
    while True:
        if i-o in self._h:
            return self._h[i-o][o]
        o+=1

улучшения содержат изменчивость.

Answer 4

Итак, вы все еще хотите иметь возможность обращаться к n-му элементу списка, например, найти это x.somemethod(2) == 'ij'?Если нет, то ваша структура данных - это просто строка с некоторыми методами, чтобы сделать ее изменчивой и инициализировать ее из списка строк.

Если вы хотите это сделать, то ваша структура данных все ещеstring с этими дополнительными методами, плюс еще один элемент для отслеживания диапазонов, из которых произошли его элементы, например x.camefrom(1) == (3, 7).

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

Answer 5

Вы воссоздали тип данных словаря.