如何在列表中找到首先出现在另一个给定列表中的元素的索引? [英] How to find the index of the element in a list that first appears in another given list?
问题描述
a = [3, 4, 2, 1, 7, 6, 5]
b = [4, 6]
答案应该是1.因为在a中,4在列表b中首先出现,并且它的索引是1。
The answer should be 1. Because in a, 4 appears first in list b, and it's index is 1.
问题是python中有没有快速代码来实现这个目标?
The question is that is there any fast code in python to achieve this?
PS:实际上a是随机排列而b是子集a,但它表示为一个列表。
PS: Actually a is a random permutation and b is a subset of a, but it's represented as a list.
推荐答案
如果 b
是被视为子集(顺序无关紧要,所有值都出现在 a
中),然后使用 min()
带 map()
:
If b
is to be seen as a subset (order doesn't matter, all values are present in a
), then use min()
with a map()
:
min(map(a.index, b))
这将返回最低的索引。这是一个O(NK)解决方案(其中N是 a
的长度,K是 b
的K),但是所有循环都在C代码中执行。
This returns the lowest index. This is a O(NK) solution (where N is the length of a
, K that of b
), but all looping is executed in C code.
另一种选择是将 a
转换为集合并使用 next()
循环超过 enumerate()
:
Another option is to convert a
to a set and use next()
on a loop over enumerate()
:
bset = set(b)
next(i for i, v in enumerate(a) if v in bset)
这是一个O(N)解决方案,但具有更高的常量成本(要执行的Python字节码)。它在很大程度上取决于 a
和 b
的大小,哪一个会更快。
This is a O(N) solution, but has higher constant cost (Python bytecode to execute). It heavily depends on the sizes of a
and b
which one is going to be faster.
对于问题中的小输入示例, min(map(...))
wins:
For the small input example in the question, min(map(...))
wins:
In [86]: a = [3, 4, 2, 1, 7, 6, 5]
...: b = [4, 6]
...:
In [87]: %timeit min(map(a.index, b))
...:
608 ns ± 64.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [88]: bset = set(b)
...:
In [89]: %timeit next(i for i, v in enumerate(a) if v in bset)
...:
717 ns ± 30.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
这篇关于如何在列表中找到首先出现在另一个给定列表中的元素的索引?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!