W Pythonie, sprawnie określ, czy dwie listy są przesuniętymi kopiami siebie.

Question

Jaki jest najbardziej efektywny (na czas) sposób sprawdzenia, czy dwie względnie krótkie (około 3-8 elementów) listy są wzajemnie przesuniętymi kopiami? A jeśli tak, ustal i zwróć offset?

Oto przykładowy kod i wyjście Chciałbym:

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

Listy mogą mieć zduplikowane wpisy. Jeśli więcej niż jedno przesunięcie jest poprawne, zwróć wszelkie przesunięcie.

Answer 1

Searching dwie kopie pierwszej listy pozwala nam uniknąć wykonywania nadmiernej konkatenacji:

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

oto prosta wersja iterator, który wykonuje pracę w 2n iteracji (gdzie n oznacza długość listy)

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 

iz specyfikacji

nie powinien is_shifted_copy([1, 1, 2], [2, 1, 1]) powrót 2?

Answer 3

Oto rozwiązanie oparte na indeksach i krojenia:

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

Wynik jest zgodnie z oczekiwaniami:

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

Poniżej jest zmodyfikowaną wersją rozwiązania NPE, która sprawdza wszystkich możliwych pozycjach meczu . Porównuje ona pozytywnie na (i ecatmur'S) sprytnych rozwiązań iterator thkang za:

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 

---

Uwaga: Zmieniłem wartości zwracanej w is_shifted_copy_thkang i is_shifted_copy_ecatmur tak, że wszystkie trzy wersje by przejść testy w oryginalny post.

Przeprowadziłem analizę porównawczą funkcji zi bez zmiany i okazało się, że nie ma to znaczącego wpływu na działanie funkcji.

Na przykład, z 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 

Z 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