Python：使用'is'而非'=='的最快list.index()操作（按引用）

Question

问题：

在Python中，list.index(a)会返回一个索引，这个索引满足a == list[index]这个条件。但我需要找到一个索引，使得a is list[index]为真，而且我希望这个过程尽可能快（速度很重要）。我该怎么做呢？

背景：

也许我在编程的方式上有些不对。为了说明，我需要解决上面提到的问题：

我有一些文本，需要能够非常快速地插入或删除字符。因此，我使用一个字符列表（大约一百万个字符），而不是字符串。

此外，在任何给定的插入或删除操作后，我必须快速知道在该索引之前有多少个换行符。我尝试过list[0:index].count(newline)，但速度太慢了。所以我在尝试用上面问题的解决方案来寻找第二种方法。

当然，也许在每次操作后再计算这个信息本身就太慢了。但我想不出有什么快速的方法来维护这些信息（为了查找，这样我就不必每次都计算），因为每次插入或删除字符时，索引和换行符的数量都可能会改变。

编辑：

这是我到目前为止的解决方案。使用cProfile，我发现它的速度大约是chars[0:index].count()的1/50，但仍然不够快：

#Initialized once, and then maintained after every change.
chars = [['\n'],['a'],['b'],['\n'],.... ]
newlines = [newline for newline in chars if newline == ['\n']]

#called every time I need the count of newlines preceding 'index'
def newlinecount(index):

    #find closest preceding newline
    previousNewlineIndex = index
    while not chars[previousNewlineIndex ] == ['\n']:
        previousNewlineIndex -= 1
    previousNewline = chars[previousNewlineIndex]

    #find position of 'previousNewline' in 'newlines', and thus newlinecount
    for count, newline in enumerate(newlines):
        if newline is previousNewline:
            return count + 1 #(add 1 because 'count' starts from 0)

谢谢！

Answer 1

我觉得，你可能需要维护两个不同的数据结构：

• char_list：就是字符的列表，所有的字符都在这里。
• index_list：另一个排序好的列表，里面存的是换行符的位置（索引）。

你在插入和删除字符的时候，会同时对这两个数据结构进行操作。当你插入或删除一个字符时，需要在index_list中相应的位置加一或减一。之后，index_list.index(new_char_index) 就可以告诉你在插入或删除的字符之前有多少个换行符。

Answer 2

我不太确定我理解得对不对，但你有没有想过把你的文本当作一系列行来处理呢？

如果你把1Mb的文本存储为一个字符串列表（每行一个字符串），那么在插入或替换时会非常快（因为字符串会很短），而且你可以用列表的索引来跟踪文本中某个点前后有多少个换行符。

这样做有没有帮助，还是我误解了你的意思？

Answer 3

在Python中，list.index(a)会返回一个索引，这个索引满足条件a == list[index]为真。但我需要找到一个索引，使得a is list[index]为真，并且希望这个过程尽可能快（速度很重要）。

即使list.index()是这样工作的，你也不会得到太多好处。因为Python没有字符类型，所以你应该把字符存储为整数，而不是一个字符的字符串。整数在比较时==和is的方式是一样的。

我有一些文本，需要能够非常快速地插入或删除字符。因此，我使用一个字符列表（大约一百万个字符），而不是字符串。

把字符存储在列表中并不是实现快速插入和删除的好方法。Python的列表是动态数组，而不是链表，所以添加或删除项目的时间复杂度是O(n)。举个例子，如果你想删除range(10)中的5，那么6到9的项目就需要向左移动一个位置。

而且，在任何给定的插入或删除操作后，我必须非常快速地知道在该索引之前有多少个换行符。

我建议你把换行符的索引保存在一个单独的数据结构中，并在每次添加或删除换行符时更新这个结构。否则，你总是需要扫描整个列表直到当前的位置。

由于Python是一种高级语言，我怀疑你能在纯Python中获得真正好的性能来解决你的问题。