In Python, determinare in modo efficiente se due liste sono spostate le copie l'una dell'altra

Question

Qual è il modo più efficiente (nel tempo) di verificare se due elenchi relativamente brevi (circa 3-8 elementi) sono copiati l'uno dell'altro? E se sì, determinare e restituire l'offset?

Ecco il codice di esempio e l'uscita mi piacerebbe:

>>> def is_shifted_copy(list_one, list_two): 
>>>  # TODO 
>>> 
>>> is_shifted_copy([1, 2, 3], [1, 2, 3]) 
0 
>>> is_shifted_copy([1, 2, 3], [3, 1, 2]) 
1 
>>> is_shifted_copy([1, 2, 3], [2, 3, 1]) 
2 
>>> is_shifted_copy([1, 2, 3], [3, 2, 1]) 
None 
>>> is_shifted_copy([1, 2, 3], [1]) 
None 
>>> is_shifted_copy([1, 1, 2], [2, 1, 1]) 
1 

liste possono avere voci duplicate. Se più di un offset è valido, restituire qualsiasi offset.

Answer 1

Cercando due copie del primo elenco ci permette di evitare di eseguire un eccessivo concatenazione:

def is_shifted_copy(l1, l2): 
    l1l1 = l1 * 2 
    n = len(l1) 
    return next((i for i in range(n) if l1l1[i:i + n] == l2), None) 

Answer 2

ecco una semplice versione iteratore che fa il lavoro in iterazioni 2n (n essendo la lunghezza della lista)

import itertools 

def is_shifted_copy(list1, list2): 

    if len(list1) != len(list2): 
     return False 

    iterator = iter(list2) 

    for i, item in enumerate(itertools.chain(list1, list1)): 
     try: 
      if item == iterator.next(): 
       continue 
      else: 
       iterator = iter(list2) 
     except StopIteration: 
      return i - len(list2) 

    else: 
     return False 


print is_shifted_copy([1, 2, 3], [1, 2, 3]) #0 
print is_shifted_copy([1, 2, 3], [3, 1, 2]) #2 
print is_shifted_copy([1, 2, 3], [3, 2, 1]) #False 
print is_shifted_copy([1, 2, 3], [2, 3, 1]) #1 
print is_shifted_copy([1, 1, 2], [2, 1, 1]) #2 
print is_shifted_copy([1, 2, 3], [1]) #False 
print is_shifted_copy([1, 2, 1], [2, 1, 1]) #1 
print is_shifted_copy([1, 1, 1], [1, 1, 1]) #0 

e dalla vostra specifica,

non dovrebbe is_shifted_copy([1, 1, 2], [2, 1, 1]) ritorno 2?

Answer 3

Ecco una soluzione basata su indici e affettare:

>>> def is_shifted_copy(l1, l2): 
    try: 
     return [l1[-i:] + l1[:-i] for i in range(len(l1))].index(l2) 
    except ValueError: 
     return None 

Il risultato è come previsto:

>>> is_shifted_copy([1, 2, 3], [1, 2, 3]) 
0 
>>> is_shifted_copy([1, 2, 3], [3, 1, 2]) 
1 
>>> is_shifted_copy([1, 2, 3], [2, 3, 1]) 
2 
>>> is_shifted_copy([1, 2, 3], [2, 1, 3]) 
None 

Answer 4

Qui di seguito è una versione modificata della soluzione di NPE, che verifica la presenza di tutte le posizioni possibili partita . Si confronta favorevolmente alle soluzioni iteratore di thkang (e di ecatmur) intelligenti:

import itertools as IT 

def is_shifted_copy_thkang(list1, list2): 
    N = len(list1) 
    if N != len(list2): 
     return None 
    elif N == 0: 
     return 0 
    next_item = iter(list2).next 
    for i, item in enumerate(IT.chain(list1, list1)): 
     try: 
      if item == next_item(): 
       continue 
      else: 
       next_item = iter(list2).next 
     except StopIteration: 
      return -i % N 
    else: 
     return None 

def is_shifted_copy_NPE(list1, list2): 
    N = len(list1) 
    if N != len(list2): 
     return None 
    elif N == 0: 
     return 0 

    pos = -1 
    first = list1[0] 
    while pos < N: 
     try: 
      pos = list2.index(first, pos+1) 
     except ValueError: 
      break 
     if (list2 + list2)[pos:pos+N] == list1: 
      return pos 
    return None 

def is_shifted_copy_ecatmur(l1, l2): 
    l1l1 = l1 * 2 
    n = len(l1) 
    return next((-i % n for i in range(n) if l1l1[i:i + n] == l2), None) 


tests = [ 
    # ([], [], 0),  
    ([1, 2, 3], [1, 2, 3], 0), 
    ([1, 2, 3], [3, 1, 2], 1), 
    ([1, 2, 3], [2, 3, 1], 2), 
    ([1, 2, 3], [3, 2, 1], None), 
    ([1, 2, 3], [1], None), 
    ([1, 1, 2], [2, 1, 1], 1), 
    ([1,2,3,1,3,2], [1,3,2,1,2,3], 3) 
    ] 

for list1, list2, answer in tests: 
    print(list1, list2, answer) 
    assert is_shifted_copy_thkang(list1, list2) == answer 
    assert is_shifted_copy_NPE(list1, list2) == answer  
    assert is_shifted_copy_ecatmur(list1, list2) == answer   

---

In [378]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2]) 
100000 loops, best of 3: 3.5 us per loop 

In [377]: %timeit is_shifted_copy_ecatmur([1, 2, 3], [3, 1, 2]) 
100000 loops, best of 3: 2.37 us per loop 

In [379]: %timeit is_shifted_copy_NPE([1, 2, 3], [3, 1, 2]) 
1000000 loops, best of 3: 1.13 us per loop 

---

Nota: ho cambiato il valore di ritorno in is_shifted_copy_thkang e is_shifted_copy_ecatmur in modo che tutte e tre le versioni sarebbero superare i test in il post originale.

Ho confrontato le funzioni con e senza la modifica e ho rilevato che non influisce in modo significativo sulle prestazioni delle funzioni.

Ad esempio, con return i:

In [384]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2]) 
100000 loops, best of 3: 3.38 us per loop 

Con return -i % N:

In [378]: %timeit is_shifted_copy_thkang([1, 2, 3], [3, 1, 2]) 
100000 loops, best of 3: 3.5 us per loop