Python中两个列表的有序交集 [英] Ordered intersection of two lists in Python

问题描述

我知道在Python中，如果有的话:

I know that in Python, if I have:

list_1 = [1,2,3]
list_2 = [2,3,4]

我可以执行以下操作找到两者之间的交集:

I can do the following to find the intersection between the two:

list(set(list_1) & set(list_2))
# = [2,3]

但是这种方法存在一个问题:集不像列表那样保持顺序.所以，如果我真的有:

But there's one problem with that approach: sets don't maintain order the way that lists do. So if I actually have:

list_1 = [3,2,1]
list_2 = [2,3,4]

我得到:

list(set(list_1) & set(list_2))
# = [2,3]

即使我更希望从第一个列表中获得订单，即:

even though I'd prefer to have the order from the first list, ie.:

# = [3,2]

有没有一种替代的交集技术，可以使生成的交集"保持与第一个列表相同的顺序?

Is there an alternative intersection technique which keeps the resulting "intersection set" in the same order as the first list?

推荐答案

set_2 = frozenset(list_2)
intersection = [x for x in list_1 if x in set_2]

set而不是frozenset也可以工作，在我不打算对数据进行突变的情况下，我越来越习惯使用不可变的类.关键是要维护顺序，您需要按照要维护的顺序遍历列表，但是您不想拥有天真的方法n [x for x in list_1 if x in list_2].与列表中的成员资格的O(n)相比，检查set或类似的基于哈希的类型的成员资格大致为O(1).

set instead of frozenset works too, I'm just increasingly in the habit of using immutable classes in cases where I don't intend to mutate the data. The point is that to maintain order you need to traverse the list in the order you want to maintain, but you don't want to have the n*m complexity of the naive approach: [x for x in list_1 if x in list_2]. Checking for membership in a set or similar hash-based type is roughly O(1), compared to O(n) for membership in a list.

这篇关于Python中两个列表的有序交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！