Эффективный способ сдвинуть список в Python

Question

Какой самый эффективный способ сдвинуть список в python? Прямо сейчас у меня есть что-то вроде этого:

>>> def shift(l, n):
...     return l[n:] + l[:n]
... 
>>> l = [1,2,3,4]
>>> shift(l,1)
[2, 3, 4, 1]
>>> shift(l,2)
[3, 4, 1, 2]
>>> shift(l,0)
[1, 2, 3, 4]
>>> shift(l,-1)
[4, 1, 2, 3]

Есть ли лучший способ?

Answer 1

Джон Бентли из Programming Pearls (столбец 2) описывает элегантный и эффективный алгоритм поворота n -элемента-элемента x, оставленного на i позициях:

Давайте рассмотрим проблему как преобразование массива ab в массив ba, но давайте также предположим, что у нас есть функция, которая обращает элементы в указанной части массива. Начиная с ab, мы обратный a чтобы получить a<sup>r</sup>b, обратный b чтобы получить a<sup>r</sup>b<sup>r</sup>, а затем полностью изменить вещь, чтобы получить (a<sup>r</sup>b<sup>r</sup>)<sup>r</sup>, что точно ba. Это приводит к следующему коду для вращение:

reverse(0, i-1)
reverse(i, n-1)
reverse(0, n-1)

Это можно перевести на Python следующим образом:

def rotate(x, i):
    i %= len(x)
    x[:i] = reversed(x[:i])
    x[i:] = reversed(x[i:])
    x[:] = reversed(x)
    return x

Демо-версия:

>>> def rotate(x, i):
...     i %= len(x)
...     x[:i] = reversed(x[:i])
...     x[i:] = reversed(x[i:])
...     x[:] = reversed(x)
...     return x
... 
>>> rotate(list('abcdefgh'), 1)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']
>>> rotate(list('abcdefgh'), 3)
['d', 'e', 'f', 'g', 'h', 'a', 'b', 'c']
>>> rotate(list('abcdefgh'), 8)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> rotate(list('abcdefgh'), 9)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']

Answer 2

Следующая функция копирует отправленный список во временный список, чтобы функция pop не влияла на исходный список:

def shift(lst, n, toreverse=False):
    templist = []
    for i in lst: templist.append(i)
    if toreverse:
        for i in range(n):  templist = [templist.pop()]+templist
    else:
        for i in range(n):  templist = templist+[templist.pop(0)]
    return templist

Тестирование:

lst = [1,2,3,4,5]
print("lst=", lst)
print("shift by 1:", shift(lst,1))
print("lst=", lst)
print("shift by 7:", shift(lst,7))
print("lst=", lst)
print("shift by 1 reverse:", shift(lst,1, True))
print("lst=", lst)
print("shift by 7 reverse:", shift(lst,7, True))
print("lst=", lst)

Выход:

lst= [1, 2, 3, 4, 5]
shift by 1: [2, 3, 4, 5, 1]
lst= [1, 2, 3, 4, 5]
shift by 7: [3, 4, 5, 1, 2]
lst= [1, 2, 3, 4, 5]
shift by 1 reverse: [5, 1, 2, 3, 4]
lst= [1, 2, 3, 4, 5]
shift by 7 reverse: [4, 5, 1, 2, 3]
lst= [1, 2, 3, 4, 5]

Answer 3

Какой вариант использования? Часто нам не нужен полностью смещенный массив - нам просто нужно получить доступ к нескольким элементам в смещенном массиве.

Получение фрагментов Python - это время выполнения O (k), где k - это срез, поэтому вращение срезов - это время выполнения N. Команда вращения deque также O (k). Можем ли мы сделать лучше?

Рассмотрим массив, который очень большой (скажем, настолько большой, что его нарезка будет вычислительно медленной). Альтернативным решением было бы оставить исходный массив в покое и просто вычислить индекс элемента, который существовал бы в нашем желаемом индексе после какого-либо сдвига.

Таким образом, доступ к смещенному элементу становится O (1).

def get_shifted_element(original_list, shift_to_left, index_in_shifted):
    # back calculate the original index by reversing the left shift
    idx_original = (index_in_shifted + shift_to_left) % len(original_list)
    return original_list[idx_original]

my_list = [1, 2, 3, 4, 5]

print get_shifted_element(my_list, 1, 2) ----> outputs 4

print get_shifted_element(my_list, -2, 3) -----> outputs 2 

Answer 4

для аналогичной функциональности, как shift на других языках:

def shift(l):
    x = l[0]
    del(l[0])
    return x