Python: intersezione di elenchi annidati in cui l'ordine è importante

Question

Vorrei trovare l'intersezione tra gli elenchi annidati mantenendo l'ordine.

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']] 

Per trovare l'intersezione ho:

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

o

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

ma l'ordine originale non viene mantenuta.

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

In sostanza, quello che devo fare è trovare l'ultimo elemento comune tra le liste nidificate (sono classificazioni taxanomic). Quindi non ho bisogno di trovare tutti gli incroci, solo l'ultimo o tutti quando posso solo chiamare l'ultima voce.

intersection_lst[-1] 

In questo caso voglio che l'uscita sia "Erwinia".

Grazie per il vostro aiuto.

Answer 1

trovare l'intersezione, poi riproporre, ordine.

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

Oppure, se siete eccessivamente affezionato a one-liner:

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

Answer 2

È possibile ottenere questo con:

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

Se le liste sono di grandi dimensioni, sarebbe più efficace per farlo:

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

Answer 3

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) ] 

Si noti che questo funziona solo se le liste interne sono unici

Ed ecco un esempio utilizzando un contatore ordinata:

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) ] 

ancora funziona solo se gli elementi sono unici in ogni sottoelenco

Answer 4

Ho avuto un problema simile oggi. Nei miei benchmark, l'utilizzo di set.intersection era il modo più veloce per ottenere questo risultato in CPython, prendendo circa 170us con il mio set di dati.

In PyPy tuttavia, una funzione arrotolata a mano che sfruttava l'ordine richiedeva solo ~ 80us, quasi il doppio della velocità di CPython! La stessa funzione in CPython ha ~ 6200us.

qui è che la funzione per i posteri:

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