Trong Python, xác định hiệu quả nếu hai danh sách được dịch chuyển các bản sao của nhau

Question

Cách hiệu quả nhất (theo thời gian) là kiểm tra xem hai danh sách tương đối ngắn (khoảng 3-8 phần tử) có được sao chép của nhau không? Và nếu có, xác định và trả lại khoản bù trừ?

Đây là đoạn mã ví dụ và đầu ra tôi muốn:

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

Chức năng có thể có mục trùng lặp. Nếu nhiều hơn một offset là hợp lệ, trả về bất kỳ offset nào.

Answer 1

Tìm kiếm hai bản sao của danh sách đầu tiên cho phép chúng tôi để tránh thực hiện nối quá mức:

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

đây là một phiên bản lặp đơn giản mà không được công việc trong lặp 2n (n là chiều dài của danh sách)

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 

và từ đặc điểm kỹ thuật của bạn,

không nên is_shifted_copy([1, 1, 2], [2, 1, 1]) trở 2?

Answer 3

Đây là một giải pháp dựa trên các chỉ mục và cắt:

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

Kết quả được như mong đợi:

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

Dưới đây là một phiên bản sửa đổi của giải pháp NPE, mà kiểm tra cho tất cả các vị trí phù hợp với khả năng . Nó so sánh thuận lợi để (và ecatmur của) các giải pháp iterator thông minh thkang của:

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 

---

Lưu ý: Tôi đã thay đổi giá trị trả về trong is_shifted_copy_thkang và is_shifted_copy_ecatmur để tất cả ba phiên bản sẽ vượt qua các bài kiểm tra trong bài đăng gốc.

Tôi đã đánh giá các hàm có và không có thay đổi và thấy nó không ảnh hưởng đáng kể đến hiệu suất của các hàm.

Ví dụ, với 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 

Với 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