Эффективный способ сдвинуть список в 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

Возможно кольцевой буфер больше подходит. Это не список, хотя вполне вероятно, что он может вести себя достаточно как список для ваших целей.

Проблема в том, что эффективность сдвига в списке равна O (n), что становится значительным для достаточно больших списков.

Сдвиг в кольцевом буфере - это просто обновление местоположения головы, которое равно O (1)

Answer 2

Если ваша цель - эффективность (циклы? Память?), Вам лучше посмотреть на модуль массива: http://docs.python.org/library/array.html

Массивы не имеют служебных списков.

Что касается чистых списков, то, что у вас есть, настолько хорошо, насколько вы можете надеяться.

Answer 3

Я думаю, что вы ищете это:

a.insert(0, x)

Answer 4

Другая альтернатива:

def move(arr, n):
    return [arr[(idx-n) % len(arr)] for idx,_ in enumerate(arr)]

Answer 5

Для списка X = ['a', 'b', 'c', 'd', 'e', 'f'] и желаемого значения сдвига shift меньше длины списка мы можем определить функцию list_shift(), как показано ниже

def list_shift(my_list, shift):
    assert shift < len(my_list)
    return my_list[shift:] + my_list[:shift]

Примеры,

list_shift(X,1) возвращает ['b', 'c', 'd', 'e', 'f', 'a'] list_shift(X,3) возвращает ['d', 'e', 'f', 'a', 'b', 'c']

Answer 6

Я беру эту модель стоимости в качестве ссылки:

http://scripts.mit.edu/~6.006/fall07/wiki/index.php?title=Python_Cost_Model

Ваш метод нарезки списка и объединения двух подсписков - это операции с линейным временем. Я бы предложил использовать pop, который является операцией с постоянным временем, например ::1006

def shift(list, n):
    for i in range(n)
        temp = list.pop()
        list.insert(0, temp)

Answer 7

Я думаю, у вас есть самый эффективный способ

def shift(l,n):
    n = n % len(l)  
    return l[-U:] + l[:-U]

Answer 8

У меня похожая вещь. Например, сдвинуться на два ...

def Shift(*args):
    return args[len(args)-2:]+args[:len(args)-2]

Answer 9

Следующий метод - O (n) на месте с постоянной вспомогательной памятью:

def rotate(arr, shift):
  pivot = shift % len(arr)
  dst = 0
  src = pivot
  while (dst != src):
    arr[dst], arr[src] = arr[src], arr[dst]
    dst += 1
    src += 1
    if src == len(arr):
      src = pivot
    elif dst == pivot:
      pivot = src

Обратите внимание, что в python этот подход ужасно неэффективен по сравнению с другими, поскольку он не может использовать преимущества собственных реализаций какой-либо части.

Answer 10

Я не знаю, является ли это «эффективным», но это также работает:

x = [1,2,3,4]
x.insert(0,x.pop())

РЕДАКТИРОВАТЬ: еще раз Здравствуйте, я только что нашел большую проблему с этим решением! Рассмотрим следующий код:

class MyClass():
    def __init__(self):
        self.classlist = []

    def shift_classlist(self): # right-shift-operation
        self.classlist.insert(0, self.classlist.pop())

if __name__ == '__main__':
    otherlist = [1,2,3]
    x = MyClass()

    # this is where kind of a magic link is created...
    x.classlist = otherlist

    for ii in xrange(2): # just to do it 2 times
        print '\n\n\nbefore shift:'
        print '     x.classlist =', x.classlist
        print '     otherlist =', otherlist
        x.shift_classlist() 
        print 'after shift:'
        print '     x.classlist =', x.classlist
        print '     otherlist =', otherlist, '<-- SHOULD NOT HAVE BIN CHANGED!'

Метод shift_classlist () выполняет тот же код, что и мой x.insert (0, x.pop ()) - решение, otherlist - это список, независимый от класса. После передачи содержимого otherlist в список MyClass.classlist вызов функции shift_classlist () также изменяет список других списков:

КОНСОЛЬНЫЙ ВЫХОД:

before shift:
     x.classlist = [1, 2, 3]
     otherlist = [1, 2, 3]
after shift:
     x.classlist = [3, 1, 2]
     otherlist = [3, 1, 2] <-- SHOULD NOT HAVE BIN CHANGED!



before shift:
     x.classlist = [3, 1, 2]
     otherlist = [3, 1, 2]
after shift:
     x.classlist = [2, 3, 1]
     otherlist = [2, 3, 1] <-- SHOULD NOT HAVE BIN CHANGED!

Я использую Python 2.7. Я не знаю, является ли это ошибкой, но я думаю, что более вероятно, что я что-то здесь неправильно понял.

Кто-нибудь из вас знает, почему это происходит?