Сравнить два списка, чтобы увидеть, если один поворот другой


Пройдя через список общий вопрос интервью был следующий. Любые предложения о производительности и улучшения? Что может быть лучше реализации этого? Также поправьте меня, если я ошибаюсь, это будет \$О(П)\$ сложность?

'''
Problem statement: Given 2 integer arrays, determine if the 2nd array is a     rotated version of the 1st array. 
Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3} 

@author: Anonymous3.1415
'''

#@cmp_arr, is the array being compared to see if it is a rotation
def is_rotated(int_arr, cmp_arr):

    #lengths of arrays are the same and not equal to zero?
    if len(int_arr) != len(cmp_arr) or len(int_arr) == 0:
        return False

    #does array contain same numbers?
    if not set(int_arr) <= set(cmp_arr) and not set(int_arr) >= set(cmp_arr):
        return False

    #Find start of first list in the second
    index = 0
    while int_arr[0] != cmp_arr[index]:
        index += 1

    #split list at index point, compare the lists
    cmp_arr = cmp_arr[index:] + cmp_arr[:index]
    index = 0
    for x in int_arr:
        if x != cmp_arr[index]:
            return False
        index += 1

    return True

int_arr = [1,2,3,4,6,4,7]
cmp_arr = [6,4,7,1,2,3,4]
print(is_rotated(int_arr, cmp_arr))


Комментарии
2 ответа

Именования

Ваш 2 массивы используются таким же образом, это немного странно иметь 2 разных названия для них. Может int_arr1 и int_arr2 лучше бы имена. Также тот факт, что они содержат целые числа могут быть несущественны для именования: arr1 и arr2 будет делать трюк (или lst1 и lst2 поскольку соответствующий питона примитивная структура данных list).

Проблема с проверьте длины, равная 0

Проверка одинаковой длины, как в начале функции-приятный штрих.

Однако or len(lst1) == 0 состояние мне неловко. Он только делает другой, когда первая часть проверки была ложной и вторая часть Верна, который означает: len(lst1) == len(lst2) == 0 что на самом деле означает: lst1 == lst2 == [].

Я ожидал, что пустой массив, чтобы быть вращением пустой массив. Альтернативой может быть документ функции точны, что только нетривиальные повороты считаются (чего не происходит на данный момент). Легко исправить это возможно, чтобы удалить этот тест или возвращать true в этом случае (или whenver lst1 == lst2).

Комментарии

Комментирование кода-это хорошо, но при добавлении очевидные замечания никому не поможет. Существует тонкая грань между слишком много комментариев и мало комментариев.

Я бы избавиться от #lengths of arrays are the same and not equal to zero? например.

С другой стороны, #@cmp_arr, is the array being compared to see if it is a rotation может быть как-то. Это должно быть перемещена в строкой документации функции. Кроме того, Python имеет строкой документации конвенции называют Пеп 257. Вы могли бы написать:

def is_rotated(lst1, lst2):
"""Test whether list lst1 is a rotation of list lst2."""

Же значение, вычисленное в несколько раз

Вы рассчитываете set(lst1) несколько раз что не так эффективно, как это может быть (что печально для чего-то предназначены для оптимизации).

#does array contain same numbers?
s1 = set(lst1)
s2 = set(lst2)
if not s1 <= s2 and not s1 >= s2:
return False

Оптимизация не работает

Я думаю, дело в оптимизации будет обнаружить таких ситуациях, как:

lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
print(is_rotated(lst1, lst2))

lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
print(is_rotated(lst1, lst2))

К сожалению, это не обнаружено.

Я думаю, вместо not s1 <= s2 and not s1 >= s2ты имел в виду: not s1 <= s2 or not s1 >= s2 что эквивалентно not (s1 <= s2 and s1 >= s2) что эквивалентно более прямолинеен: s1 != s2.

В любом случае, как отметил Оскар Смит, эта оптимизация может и не стоит делать.

Повторное использование существующих функций

Ищу индекса может быть сделано с уже существующей функции: index = lst2.index(lst1[0]).

Петли, как родной

Свой последний круг не очень подходящие для Python. Большую часть времени в Python, вы можете избежать возни с индексами. Я сильно рекомендую Нэд Батчелдер говорить: "петля как родной".

В вашем случае, мы можем улучшить ваш код в несколько шагов. (Некоторые из этих шагов довольно искусственное в вашем случае, но я использую их, чтобы показать вам различные функции в вашем инструментов Python).

Введение enumerate чтобы избавиться от код для отслеживания index:

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for i, x in enumerate(lst1):
if x != rot2[i]:
return False
return True

Используя zip чтобы избежать доступа rot2 по индексу:

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for x1, x2 in zip(lst1, rot2):
if x1 != x2:
return False
return True

Используя all чтобы сделать вещи более лаконичными:

return all(x1 == x2 for x1, x2 in zip(lst1, rot2))

Последнее откровение: все это не требуется:

return lst1 == rot2

На данный момент код выглядит так:

def is_rotated(lst1, lst2):
"""Test whether list lst1 is a rotation of list lst2."""
if len(lst1) != len(lst2):
return False

if lst1 == lst2:
return True

if set(lst1) != set(lst2):
return False

index = lst2.index(lst1[0])

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
return lst1 == rot2

Сломанной код

Как отметил Оскар Смит, ваш код не работает.

Для такого рода задач программирования, это очень легко писать тесты, чтобы помочь вам обнаружить проблемы. Они могут быть написаны до, во время и после написания кода. Вы могли бы использовать правильную систему тестирования или просто утверждения, как:

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)

5
ответ дан 9 февраля 2018 в 06:02 Источник Поделиться

Хотя это O(n)Это не так быстро, как хотелось бы.

Первый чек-это хорошо, потому что это O(1)и будет хит для случайных списков изрядное количество. Однако у второго нет. найти уникальные элементы, вы в конечном итоге делает экран, который стоит в промежуток времени сравнимый с решения актуальной проблемы.

Следующий кусок кода действительно сломан, так как он только находит первое совпадение, а не все возможные совпадения. В самом деле, когда вы исправить эту ошибку, код будет O(n^2) в худшем случае (если [0]*1000+[1,0] а другой [0]*1000+[0,1])

4
ответ дан 9 февраля 2018 в 05:02 Источник Поделиться