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

A collections.deque оптимизирован для тяги и толкания с обоих концов.У них даже есть специальный rotate() метод.

from collections import deque
items = deque([1, 2])
items.append(3)        # deque == [1, 2, 3]
items.rotate(1)        # The deque is now: [3, 1, 2]
items.rotate(-1)       # Returns deque to original state: [1, 2, 3]
item = items.popleft() # deque == [2, 3]

Answer 2

Как насчет использования pop(0)?

list.pop([i])

Удалить элемент в заданной позиции в списке и вернуть его. Если индекс не указан, a.pop() удаляет и возвращает последний элемент в список. (Квадратные скобки вокруг i в сигнатуре метода Обозначим, что параметр является необязательным, а не то, что вы должны набрать квадрат скобки в этой позиции. Вы будете часто видеть эту запись в справочник по библиотеке Python.)

Answer 3

Numpy может сделать это с помощью команды roll:

>>> import numpy
>>> a=numpy.arange(1,10) #Generate some data
>>> numpy.roll(a,1)
array([9, 1, 2, 3, 4, 5, 6, 7, 8])
>>> numpy.roll(a,-1)
array([2, 3, 4, 5, 6, 7, 8, 9, 1])
>>> numpy.roll(a,5)
array([5, 6, 7, 8, 9, 1, 2, 3, 4])
>>> numpy.roll(a,9)
array([1, 2, 3, 4, 5, 6, 7, 8, 9])

Answer 4

Это зависит от того, что вы хотите, чтобы произошло, когда вы делаете это:

>>> shift([1,2,3], 14)

Возможно, вы захотите изменить:

def shift(seq, n):
    return seq[n:]+seq[:n]

до:

def shift(seq, n):
    n = n % len(seq)
    return seq[n:] + seq[:n]

Answer 5

Самый простой способ, которым я могу придумать:

a.append(a.pop(0))

Answer 6

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

Answer 7

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

def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

На самом деле, даже добавление l = l[:] к вершине этого для работы с копией переданного списка все равно в два раза быстрее.

Различные реализации с некоторой синхронизацией в http://gist.github.com/288272

Answer 8

Просто несколько заметок о времени:

Если вы начинаете со списка, l.append(l.pop(0)) - самый быстрый способ, который вы можете использовать. Это можно показать только с учетом сложности времени:

• deque.rotate = O (k) (k = количество элементов)
• преобразование списка в дек * O (n)
• list.append и list.pop оба являются O (1)

Так что, если вы начинаете с deque объектов, вы можете deque.rotate() за счет O (k). Но, если отправной точкой является список, временная сложность использования deque.rotate() равна O (n). l.append(l.pop(0) быстрее при O (1).

Просто для иллюстрации, вот несколько примеров времени на 1M итераций:

Методы, которые требуют преобразования типа:

• deque.rotate с объектом deque: 0.12380790710449219 секунд (быстрый)
• deque.rotate с преобразованием типов: 6,853878974914551 секунд
• np.roll с nparray: 6.0491721630096436 секунд
• np.roll с преобразованием типов: 27,558452129364014 секунд

Список методов, упомянутых здесь:

• l.append(l.pop(0)): 0,32483696937561035 секунд (самый быстрый)
• "shiftInPlace": 4,819645881652832 секунд
• ...

Используемый временной код приведен ниже.

---

collections.deque

Показывает, что создание заявок из списков - O (n):

from collections import deque
import big_o

def create_deque_from_list(l):
     return deque(l)

best, others = big_o.big_o(create_deque_from_list, lambda n: big_o.datagen.integers(n, -100, 100))
print best

# --> Linear: time = -2.6E-05 + 1.8E-08*n

Если вам нужно создать объекты deque:

1M итераций @ 6,853878974914551 секунд

setup_deque_rotate_with_create_deque = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
"""

test_deque_rotate_with_create_deque = """
dl = deque(l)
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_with_create_deque, setup_deque_rotate_with_create_deque)

Если у вас уже есть объекты deque:

1M итераций @ 0,12380790710449219 секунд

setup_deque_rotate_alone = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
dl = deque(l)
"""

test_deque_rotate_alone= """
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_alone, setup_deque_rotate_alone)

np.roll

Если вам нужно создать nparrays

1M итераций @ 27,558452129364014 секунд

setup_np_roll_with_create_npa = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
"""

test_np_roll_with_create_npa = """
np.roll(l,-1) # implicit conversion of l to np.nparray
"""

Если у вас уже есть nparrays:

1M итераций @ 6,0491721630096436 секунд

setup_np_roll_alone = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
npa = np.array(l)
"""

test_roll_alone = """
np.roll(npa,-1)
"""
timeit.timeit(test_roll_alone, setup_np_roll_alone)

"Сдвиг на месте"

Не требует преобразования типов

1M итераций @ 4,819645881652832 секунд

setup_shift_in_place="""
import random
l = [random.random() for i in range(1000)]
def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l
"""

test_shift_in_place="""
shiftInPlace(l,-1)
"""

timeit.timeit(test_shift_in_place, setup_shift_in_place)

l.append (l.pop (0))

Не требует преобразования типов

1M итераций @ 0,32483696937561035

setup_append_pop="""
import random
l = [random.random() for i in range(1000)]
"""

test_append_pop="""
l.append(l.pop(0))
"""
timeit.timeit(test_append_pop, setup_append_pop)

Answer 9

Для неизменной реализации вы можете использовать что-то вроде этого:

def shift(seq, n):
    shifted_seq = []
    for i in range(len(seq)):
        shifted_seq.append(seq[(i-n) % len(seq)])
    return shifted_seq

print shift([1, 2, 3, 4], 1)

Answer 10

Я также заинтересовался этим и сравнил некоторые из предложенных решений с perfplot (мой небольшой проект).

Оказывается,

for _ in range(n):
    data.append(data.pop(0))

на данный момент самый быстрый метод для небольших смен n.

Для больших n,

data[n:] + data[:n]

неплох.

По сути, perfplot выполняет сдвиг для увеличения больших массивов и измеряет время.Вот результаты:

shift = 1:

shift = 100:

---

Код для воспроизведения сюжета:

import numpy
import perfplot
import collections


shift = 100


def list_append(data):
    return data[shift:] + data[:shift]


def shift_concatenate(data):
    return numpy.concatenate([data[shift:], data[:shift]])


def roll(data):
    return numpy.roll(data, -shift)


def collections_deque(data):
    items = collections.deque(data)
    items.rotate(-shift)
    return items


def pop_append(data):
    for _ in range(shift):
        data.append(data.pop(0))
    return data


perfplot.save(
    "shift100.png",
    setup=lambda n: numpy.random.rand(n).tolist(),
    kernels=[list_append, roll, shift_concatenate, collections_deque, pop_append],
    n_range=[2 ** k for k in range(7, 20)],
    logx=True,
    logy=True,
    xlabel="len(data)",
)