以下は、すべての可能な一致位置をチェックするNPEのソリューションの修正バージョンです。これは、thkang(およびecatmur)の巧妙なイテレータソリューションと比べて遜色ありません。
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
注:の戻り値を変更して、is_shifted_copy_thkang
3is_shifted_copy_ecatmur
つのバージョンすべてが元の投稿のテストに合格するようにしました。
変更がある場合とない場合の関数のベンチマークを行ったところ、関数のパフォーマンスに大きな影響はないことがわかりました。
たとえば、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
と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