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

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

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

Существует ли лучший путь?

244
задан jameshfisher 3 August 2019 в 08:08
поделиться

6 ответов

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

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]
260
ответ дан 23 November 2019 в 03:09
поделиться
def solution(A, K):
    if len(A) == 0:
        return A

    K = K % len(A)

    return A[-K:] + A[:-K]

# use case
A = [1, 2, 3, 4, 5, 6]
K = 3
print(solution(A, K))

, Например, учитывая

A = [3, 8, 9, 7, 6]
K = 3

функция должна возвратиться [9, 7, 6, 3, 8]. Три вращения были сделаны:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

Для другого примера, учитывая [1 110]

A = [0, 0, 0]
K = 1

функция должна возвратиться [0, 0, 0]

, Учитывая [1 112]

A = [1, 2, 3, 4]
K = 4

, функция должна возвратиться [1, 2, 3, 4]

0
ответ дан 23 November 2019 в 03:09
поделиться

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

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

11
ответ дан 23 November 2019 в 03:09
поделиться

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

Arrays не имеют накладных расходов списков.

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

3
ответ дан 23 November 2019 в 03:09
поделиться

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

>>> 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]
33
ответ дан 23 November 2019 в 03:09
поделиться

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

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

Переключение в рингбуфере просто обновляет местоположение головы, которое является O (1)

4
ответ дан 23 November 2019 в 03:09
поделиться
Другие вопросы по тегам:

Похожие вопросы: