Python中可索引字符串列表的数据结构

Question

我有一堆看起来像字符串的对象，但它们其实不是真正的字符串（可以想象成映射到内存的文件）。它们长得像这样：

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

我想要的是 x 能像一个大字符串那样直接被索引，也就是说：

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

（当然，我不想用 "".join(x) 这种方式把所有字符串合并起来，因为在我的情况下，读取字符串的开销太大了。记住，它们是映射到内存的文件。）

如果我遍历整个列表，这个操作很简单，但似乎是 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

那么你还想要能够访问第 n 个列表元素吗，比如找到 x.somemethod(2) == 'ij' 这个结果？

如果不想的话，那你的数据结构其实就是一个字符串，只是加了一些方法让它可以改变，并且可以从字符串列表中初始化。

如果你想要这样做，那你的数据结构依然是一个字符串，只不过多了那些额外的方法，还有一个元素用来跟踪它的元素来自哪里，比如 x.camefrom(1) == (3, 7)。

无论如何，看起来你想要存储和操作的都是一个字符串。

Answer 2

这可以作为一个开始：

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 3

你所描述的其实是一个叫做绳子数据结构的特殊情况。

不过，遗憾的是，我不知道有什么Python的实现。