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

Question

我通常使用的基本方法是使用list.index(元素(和reversed_list.index。什么是最好的方法(只需很少的时间(？

Answer 1

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

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

查找dicts的构造需要线性时间，但查找本身是恒定的。对list.index()的reas调用需要线性时间，并且重复这样做是二次的(给定查找次数取决于列表的大小(。

你也可以在一次迭代中构建一个单一的结构：

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 2

嗯，需要有人来查找元素，而在一个大列表中，这可能需要时间！如果没有更多的信息或代码示例，将很难帮助您，但通常情况下，最好的答案是使用另一种数据结构-例如，如果您可以将元素保存在字典中，而不是以键为元素、值为索引数组的列表中，您会快得多。

Answer 3

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

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 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列表似乎并不是最好的数据结构。

正如其他人所建议的那样，你可以建立一个dict:

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]