Ottenere tutte le chiavi in ​​un dict che si sovrappongono ad altri tasti nella stessa dict

Question

Ho una lista di comprensione che assomiglia a questo:

cart = [ ((p,pp),(q,qq)) for ((p,pp),(q,qq))\ 
     in itertools.product(C.items(), repeat=2)\ 
     if p[1:] == q[:-1] ] 

C è un dict con le chiavi che sono tuple di interi arbitrari. Tutte le tuple hanno la stessa lunghezza. Il caso peggiore è che tutte le combinazioni dovrebbero essere incluse nella nuova lista. Questo può accadere abbastanza frequentemente.

Per fare un esempio, ho un dizionario come questo:

C = { (0,1):'b', 
     (2,0):'c', 
     (0,0):'d' } 

E voglio che il risultato sia:

cart = [ (((2, 0), 'c'), ((0, 1), 'b')) 
     (((2, 0), 'c'), ((0, 0), 'd')) 
     (((0, 0), 'd'), ((0, 1), 'b')) 
     (((0, 0), 'd'), ((0, 0), 'd')) ] 

Così, si sovrappongono mi riferisco, per esempio, che le tuple (1,2,3,4) e (2,3,4,5) hanno la sezione di sovrapposizione (2,3,4). Le sezioni sovrapposte devono essere sui "bordi" delle tuple. Voglio solo sovrapposizioni che abbiano una lunghezza inferiore alla lunghezza della tupla. Pertanto, (1,2,3,4) non si sovrappone a (3,4,5,6). Si noti inoltre che quando si rimuove il primo o l'ultimo elemento di una tupla potremmo finire con tuple non distinte, che devono essere confrontate con tutti gli altri elementi. Questo ultimo punto non è stato enfatizzato nel mio primo esempio.

La parte migliore del tempo di esecuzione dei miei codici viene utilizzata per comprendere questo elenco. Ho sempre bisogno di tutti gli elementi di cart quindi non sembra esserci alcuna accelerazione quando si utilizza un generatore.

La mia domanda è: c'è un modo più veloce per farlo?

un pensiero che avevo era che avrei potuto cercare di creare due nuovi dizionari come questo:

aa = defaultdict(list) 
bb = defaultdict(list) 
[aa[p[1:]].append(p) for p in C.keys()] 
[bb[p[:-1]].append(p) for p in C.keys()] 

E in qualche modo unire tutte le combinazioni di elementi della lista in aa[i] con l'elenco in bb[i] per tutti i, ma Nemmeno io riesco a comprendere questa idea.

Aggiornamento

Sia la soluzione aggiunto da tobias_k e shx2 hanno meglio la complessità del mio codice originale (per quanto posso dire). Il mio codice è O (n^2) mentre le altre due soluzioni sono O (n). Per la mia dimensione e composizione del problema, tuttavia, tutte e tre le soluzioni sembrano funzionare più o meno nello stesso tempo. Suppongo che questo abbia a che fare con una combinazione di sovraccarico associato alle chiamate di funzione, nonché la natura dei dati con cui lavoro. In particolare il numero di tasti diversi, così come la composizione effettiva dei tasti, sembra avere un grande impatto. Quest'ultimo lo so perché il codice funziona molto più lentamente per chiavi completamente casuali. Ho accettato la risposta di Tobias_k perché il suo codice è il più facile da seguire. Tuttavia, sarei ancora molto lieto di ricevere altri suggerimenti su come eseguire questa attività.

Answer 1

Si era effettivamente sulla strada giusta, usando i dizionari per memorizzare tutti i prefissi ai tasti. Tuttavia, tieni presente che (per quanto comprendo la domanda) due chiavi possono anche sovrapporsi se la sovrapposizione è inferiore alen-1, ad es. anche le chiavi (1,2,3,4) e (3,4,5,6) si sovrappongono. Quindi dobbiamo creare una mappa che tenga tutti i prefissi. (Se mi sbaglio, basta rilasciare i due anelli interni for.Una volta che abbiamo questa mappa, possiamo scorrere tutte le chiavi una seconda volta e controllare se per ognuno dei loro suffissi ci sono chiavi corrispondenti nella mappa prefixes. (Aggiornamento: Dal tasti possono sovrapporsi WRT più di un prefisso/suffisso, abbiamo memorizzare le coppie che si sovrappongono in un set.)

def get_overlap(keys): 
    # create map: prefix -> set(keys with that prefix) 
    prefixes = defaultdict(set) 
    for key in keys: 
     for prefix in [key[:i] for i in range(len(key))]: 
      prefixes[prefix].add(key) 
    # get keys with matching prefixes for all suffixes 
    overlap = set() 
    for key in keys: 
     for suffix in [key[i:] for i in range(len(key))]: 
      overlap.update([(key, other) for other in prefixes[suffix] 
                 if other != key]) 
    return overlap 

(Si noti che, per semplicità, mi interessa solo le chiavi nel dizionario , non i valori. Estendere questo per restituire i valori, anche, o facendo questo come un passo post-elaborazione, dovrebbe essere banale.)

tempo totale di funzionamento dovrebbe essere solo 2*n*k, n essendo il numero di tasti e k la lunghezza i tasti. La complessità dello spazio (la dimensione della mappa prefixes) deve essere compresa tra n*k e n^2*k, se ci sono molte chiavi con gli stessi prefissi.

Nota: La risposta sopra è per il caso più generale che la regione di sovrapposizione può avere qualsiasi lunghezza. Per il caso più semplice che si considera solo si sovrappone una più corta della tupla originale, il seguente dovrebbe essere sufficiente e dato i risultati descritti nei tuoi esempi:

def get_overlap_simple(keys): 
    prefixes = defaultdict(list) 
    for key in keys: 
     prefixes[key[:-1]].append(key) 
    return [(key, other) for key in keys for other in prefixes[key[1:]]] 

Answer 2

La tua idea di pre-elaborazione dei dati in un dict è stata buona. Qui va:

from itertools import groupby 
C = { (0,1): 'b', (2,0): 'c', (0,0): 'd' } 

def my_groupby(seq, key): 
    """ 
    >>> group_by(range(10), lambda x: 'mod=%d' % (x % 3)) 
    {'mod=2': [2, 5, 8], 'mod=0': [0, 3, 6, 9], 'mod=1': [1, 4, 7]} 
    """ 
    groups = dict() 
    for x in seq: 
     y = key(x) 
     groups.setdefault(y, []).append(x) 
    return groups 

def get_overlapping_items(C): 
    prefixes = my_groupby(C.iteritems(), key = lambda (k,v): k[:-1]) 
    for k1, v1 in C.iteritems(): 
     prefix = k1[1:] 
     for k2, v2 in prefixes.get(prefix, []): 
      yield (k1, v1), (k2, v2) 

for x in get_overlapping_items(C): 
    print x  

(((2, 0), 'c'), ((0, 1), 'b')) 
(((2, 0), 'c'), ((0, 0), 'd')) 
(((0, 0), 'd'), ((0, 1), 'b')) 
(((0, 0), 'd'), ((0, 0), 'd')) 

E, a proposito, invece di:

itertools.product(*[C.items()]*2) 

fare:

itertools.product(C.items(), repeat=2)