Python：有序嵌套列表的交集

Question

我想找到嵌套列表之间的交集，同时保持顺序。

taxa = [['E_pyrifoliae_Ep1_96', 'Bacteria', 'Proteobacteria', 'Gammaproteobacteria', 'Enterobacteriales', 'Enterobacteriaceae', 'Erwinia'],
 ['E_amylovora_CFBP1430', 'Bacteria', 'Proteobacteria', 'Gammaproteobacteria', 'Enterobacteriales', 'Enterobacteriaceae', 'Erwinia'], 
 ['E_amylovora_ATCC49946', 'Bacteria', 'Proteobacteria', 'Gammaproteobacteria', 'Enterobacteriales', 'Enterobacteriaceae', 'Erwinia']]

我需要找到交集，我的做法是：

set.intersection(*map(set, taxa))

或者

set(taxa[0]).intersection(*taxa)

但是原始的顺序没有保留。

set(['Erwinia', 'Gammaproteobacteria', 'Enterobacteriaceae', 'Enterobacteriales', 'Proteobacteria', 'Bacteria'])

基本上，我需要做的是找到嵌套列表（它们是分类学分类）之间的最后一个共同元素。因此，我不需要找到所有的交集，只需要找到最后一个或者当我可以调用最后一个条目时找到全部。

intersection_lst[-1]

在这个例子中，我希望输出结果为“Erwinia”。 谢谢你的帮助。

- Binnie

---

你正在使用哪个版本的Python？ - Dmitry B.

Answer 1

找到交集，然后重新排序。

intersection_set = set.intersection(*map(set, taxa))
intersection_lst = [t for t in taxa[0] if t in intersection_set]

或者，如果你非常喜欢使用一行代码：

sorted(set.intersection(*map(set, taxa)), key=lambda x: taxa[0].index(x))

- Steven Rumbalski

Answer 2

今天我遇到了类似的问题。在我的基准测试中，使用set.intersection是在CPython中实现这一目标最快的方法，使用我的数据集大约需要170微秒。

然而，在PyPy中，利用排序的手动编写的函数只需要大约80微秒，速度几乎是CPython的两倍！在CPython中，相同的函数需要大约6200微秒。

以下是该函数的代码，以备后用：

def intersect_ordered(a, b):
    matches = []
    ia, ib = 0, 0
    la, lb = len(a), len(b)
    while ia < la and ib < lb:
        va, vb = a[ia], b[ib]
        if va < vb:
            ia += 1
        elif vb < va:
            ib += 1
        else:
            matches.append(va)
            ia += 1
            ib += 1
    return matches

- Alec Thomas

Answer 3

你可以使用以下代码获得：

[t for t in taxa[0] if all(t in l for l in taxa)]
# ['Bacteria', 'Proteobacteria', 'Gammaproteobacteria', 'Enterobacteriales', 'Enterobacteriaceae', 'Erwinia']

如果列表很大，最好采用以下方式进行操作：

taxa_set = map(set, taxa)    
[t for t in taxa[0] if all(t in l for l in taxa_set)]

- David Robinson

Answer 4

from collections import OrderedDict
from itertools import chain

d=OrderedDict()
for elem in chain(*taxa):
    if elem in d:
        d[elem] += 1
    else:
        d[elem] = 1

intersection_lst = [ k for k,v in d.items() if v == len(taxa) ]

请注意，这仅在内部列表是唯一的情况下才有效。

以下是使用有序计数器的示例：

from collections import OrderedDict,Counter
from itertools import chain

class OrderedCounter(Counter,OrderedDict): pass

d = OrderedCounter(chain(*taxa))
intersection_lst = [ k for k,v in d.items() if v == len(taxa) ]

仅当每个子列表中的元素是唯一的时，才能正常工作

- mgilson

---

如果一个元素在内部列表中出现多次，这种方法将无法正常工作。 - David Robinson