在 Python 的列表中查找元素第一次出现和最后一次出现的最佳方法是什么？

Question

我通常使用的基本方法是使用list.index(element)和reversed_list.index(element)，但是当我需要搜索很多元素和长度时，这会失败列表太大，比如 10^5 或 10^6 甚至更大。最好的方法是什么（使用很少的时间）？

Answer 1

好吧，需要有人来完成查找元素的工作，而在大型列表中，这可能需要时间！如果没有更多信息或代码示例，将很难为您提供帮助，但通常首选的答案是使用另一种数据结构——例如，如果您可以将元素保存在字典中而不是包含键的列表中作为元素和值作为索引数组，你会更快。

Answer 2

您只需记住列表中每个元素的第一个和最后一个索引即可：

In [9]: l = [random.randint(1, 10) for _ in range(100)]

In [10]: first_index = {}

In [11]: last_index = {}

In [12]: for idx, x in enumerate(l):
    ...:     if x not in first_index:
    ...:         first_index[x] = idx
    ...:     last_index[x] = idx
    ...:


In [13]: [(x, first_index.get(x), last_index.get(x)) for x in range(1, 11)]
Out[13]:
[(1, 3, 88),
 (2, 23, 90),
 (3, 10, 91),
 (4, 13, 98),
 (5, 11, 57),
 (6, 4, 99),
 (7, 9, 92),
 (8, 19, 95),
 (9, 0, 77),
 (10, 2, 87)]

In [14]: l[0]
Out[14]: 9

Answer 3

您可以构建辅助查找结构：

lst = [1,2,3,1,2,3] # super long list

last = {n: i for i, n in enumerate(lst)}
first = {n: i for i, n in reversed(list(enumerate(lst)))}
last[3]
# 5
first[3]
# 2

查找字典的构造需要线性时间，但查找本身是恒定的。 Whreas 调用 list.index() 需要线性时间，然后重复这样做是二次的（假设您进行的查找次数取决于列表的大小）。

您也可以在一次迭代中构建一个结构：

from collections import defaultdict

lookup = defaultdict(lambda: [None, None])

for i, n in enumerate(lst):
    lookup[n][1] = i
    if lookup[n][0] is None:
        lookup[n][0] = i
    

lookup[3]
# [2, 5]
lookup[2]
# [1, 4]

Answer 4

你的方法听起来不错，我做了一些测试并且：

import numpy as np

long_list = list(np.random.randint(0, 100_000, 100_000_000))

# This takes 10ms in my machine
long_list.index(999)

# This takes 1,100ms in my machine
long_list[::-1].index(999)

# This takes 1,300ms in my machine
list(reversed(long_list)).index(999)

# This takes 200ms in my machine
long_list.reverse()
long_list.index(999)
long_list.reverse()

但归根结底，Python 列表似乎并不是最好的数据结构。

正如其他人所建议的，您可以构建一个字典：

indexes = {}
for i, val in enumerate(long_list):
    if val in indexes.keys():
        indexes[val].append(i)
    else:
        indexes[val] = [i]

这会占用大量内存，但可以解决您的问题（取决于您修改原始列表的频率）。

然后你可以这样做：

# This takes 0.02ms in my machine
ix = indexes.get(999)
ix[0], ix[-1]

在 Python 的列表中查找元素第一次出现和最后一次出现的最佳方法是什么？

What is the best possible way to find the first AND the last occurrences of an element in a list in Python?

python-3.x

list

find-occurrences