Python中高效旋转列表的方法

Question

在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]

有更好的方法吗？

- D R

---

numpy.roll 函数用于将数组沿指定轴滚动。该函数接受两个参数：a 是需要滚动的数组，shift 是滚动的偏移量。import numpy as np a = np.array([1, 2, 3, 4, 5]) print(np.roll(a, 2)) # [4 5 1 2 3]在上面的示例中，原始数组 [1, 2, 3, 4, 5] 沿着其第一个轴滚动了 2 个位置。因此，最后两个元素 4 和 5 移动到了数组开头，而前三个元素 1、2 和 3 则被推到了数组的末尾。 - BoltzmannBrain

我认为“rotate”是正确的词，而不是“shift”。 - codeforester

“真正”正确的答案是，在首次使用列表时，您不应该旋转它。创建一个“指针”变量，指向您想要“头部”或“尾部”所在的逻辑位置，并更改该变量，而不是移动列表中的任何项。查找“模数”运算符%以高效地将指针“包裹”在列表的开头和结尾。 - cnd

根据旋转的频率和需要迭代的次数，单个“真实”的旋转可以优于反复计算索引。按照要求，这是实际旋转列表的唯一方法。是否需要旋转列表，或者是否应该使用不同的数据结构，需要更多上下文才能回答。 - chepner

@cnd 如果列表需要传递给我们无法修改的Python模块，您的建议是否仍然有效？ - root

Answer 1

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]

- Ignacio Vazquez-Abrams

---

针对未来的读者：根据 https://wiki.python.org/moin/TimeComplexity，`collections.deque` 的 rotate() 操作比切片更快。 - Geoff

需要注意的是，使用deque.rotate需要先将列表转换为deque对象，这比l.append(l.pop(0))慢。因此，如果你一开始就有一个deque对象，那么使用它是最快的。否则，使用l.append(l.pop(0))。 - Purrell

具体而言，deque.rotate 的时间复杂度为 O(k)，但是从列表转换到双向队列的类型转换时间复杂度为 O(n)。因此，如果你从一个列表开始，使用 deque.rotate 的时间复杂度为 O(n)+O(k)=O(n)。另一方面，l.append(l.pop(0)) 的时间复杂度为 O(1)。 - Purrell

@Purrell，弹出列表的第一个元素的时间复杂度为O（n）。在wiki.python.org/moin/TimeComplexity中，它被列为O（k），其中k是跟随弹出项的列表中元素的数量，因为数据结构将所有后续元素向列表前移。由于这个原因，只有最后一个元素可以在O(1)时间内弹出。 - Kirk Boyer

Answer 2

那么只使用 pop(0) 怎么样？

list.pop([i])

移除列表中给定位置的元素，并返回该元素。如果没有指定索引，a.pop() 则会移除并返回列表中的最后一个元素。（在方法签名中方括号内的i表示该参数是可选的，而不是你应该在该位置输入方括号。你将经常在Python库参考手册中看到这种记法。）

- Jamgold

---

每次从列表中移除一个元素都需要O(k)的成本，其中k是剩余元素的数量。因此总时间复杂度将为O(n^2)。参考链接：http://wiki.python.org/moin/TimeComplexity - Pramod

这并没有回答问题。问题不是关于按顺序返回项目，而是关于创建一个新列表，该列表以不同的顺序排列。 - user650261

不，使用pop方法回答这个问题的答案应该是 l.append(l.pop(0))。如果我没有错的话，时间复杂度为O(1)。 - Purrell

list.pop 内部调用 list_ass_slice 函数，该函数使用 memmove 函数快速移动所有项目，但时间复杂度仍为 O(n)。参见 https://github.com/python/cpython/blob/master/Objects/listobject.c 和 https://wiki.python.org/moin/TimeComplexity。在 Python 列表中唯一可以以常数时间删除的项是最后一项。 - DRayX

被踩了。来自 https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-queues还可以将列表用作队列，其中添加的第一个元素是检索到的第一个元素（“先进先出”）；但是，列表不适合此目的。尽管从列表末尾进行附加和弹出很快，但是从列表开头进行插入或弹出很慢（因为必须将所有其他元素向右移动一个位置）。 - SantaXL

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])

- Richard

---

我喜欢 Stack Overflow 的原因是有时候在回答列表下方，你可以发现一些很棒的新宝藏，就像这个一样 :) - noamgot

这个在我测试时非常非常慢。 - Peter Harrison

@PeterHarrison：由于您没有提供测试细节，很难知道您到底是什么意思。这个答案 提供了完整的测试细节和时间比较。 - Richard

它很慢，因为每次操作后都返回更改后的列表。解决此问题的最快方法是创建一个新类，其中包括原始列表和“旋转器”位置。您可以进行旋转但不返回列表。然后需要制定特定的“返回列表”过程。因此，它将看起来像：x = rotator（list）。x.rotate（5）x.rotate（6）x.rotate（-10）。x.getlist（） - user2473664

@user2473664：为什么不将这个写成一个答案并进行基准测试呢？ - Richard

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]

- jcdyer

---

注意：对于空列表会导致程序崩溃。 - meawoppl

n = n % len(seq)返回值 = seq[-n:] + seq[:-n] - user3303020

你能解释一下为什么 n = n%len(seq) 吗？ - Minh-Long Luu

@AerysS 要考虑到移位量大于列表长度的情况，例如 7%5 = 2，因此我们将其减少为移位量为 2，这与移位 7 次相同。 - A_Arnold

Answer 5

我能想到的最简单方法：

a.append(a.pop(0))

- Thijs

---

这是列表最快的方法。 collections.deque 更快，但对于大多数常见情况下的单次迭代或任何多次迭代的列表长度，a.append(a.pop(0)) 比转换为 deque 更快。 - Purrell

@runDOSrun是对这个问题的完美回答，但很遗憾它被关闭为重复。也许你会投票重新开放它？ - Wolf

Answer 6

关于时间的一些注意事项：

如果你从一个列表开始，l.append(l.pop(0)) 是你可以使用的最快速的方法。这可以通过时间复杂度来证明：

• deque.rotate 的时间复杂度为 O(k) （k=元素数目）
• 从列表到 deque 的转换时间复杂度为 O(n)
• 列表的 append 和 pop 都是 O(1)

因此，如果你从 deque 对象开始，你可以以 O(k) 的代价使用 deque.rotate()。但是，如果起点是一个列表，则使用 deque.rotate() 的时间复杂度为 O(n)。 l.append(l.pop(0) 的时间复杂度为 O(1)，更快。

仅供举例，以下是 100 万次迭代的一些样本计时：

需要类型转换的方法：

• 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

展示从列表创建 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

如果您需要创建双向队列对象：

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)

如果您已经有了双端队列对象：

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)

- Purrell

---

虽然 list.pop() 是一个常数时间操作，但是 list.pop(0) 不是。它的运行时间与列表长度成线性关系。你可以通过修改 timeit 的设置来测试：l = [random.random() for i in range(100000)]。 - emu

list.pop不是一个常数时间操作。 list.pop的运行时间为O(k)，其中k是已删除元素后面的元素数量，因此list.pop(0)的时间复杂度为O(n)。在内部，list.pop使用list_ass_slice，该函数使用memmove比您使用Python更快地移动项目，但对于长列表仍然非常耗时。请参见https://github.com/python/cpython/blob/master/Objects/listobject.c和https://wiki.python.org/moin/TimeComplexity。 - DRayX

感谢您的时间（和评论@emu）。那么我们可以说l.append(l.pop(0))在将短列表（约7个元素）向右移动一个位置时表现最佳？ - Wolf

关于l.append(l.pop(0))作为答案的问题：这个问题已经被关闭为重复。也许你会投票重新打开它？ - Wolf

Answer 7

我也对此产生了兴趣，并用perfplot（我的一个小项目）与一些建议的解决方案进行了比较。

结果发现，Kelly Bundy的建议

tmp = data[shift:]
tmp += data[:shift]

在所有移位中表现非常出色。

实际上，perfplot 对逐渐增大的数组执行移位操作，并测量时间。以下是结果：

shift = 1：

shift = 100：

---

用于重现绘图的代码：

import numpy
import perfplot
import collections


shift = 100


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


def list_append2(data):
    tmp = data[shift:]
    tmp += data[:shift]
    return tmp


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):
    data = data.copy()
    for _ in range(shift):
        data.append(data.pop(0))
    return data


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

- Nico Schlömer

---

你构建的工具很不错。关于l.append(l.pop(0))作为答案：这个问题已经被关闭为重复。也许你会投票重新打开它？ - Wolf

这是更快的代码：def tmp_del(data): tmp = data[:shift]; del data[:shift]; data += tmp; return data（在n=1时与pop_append相匹配，在n=10时胜过它，在n=100时胜过collections_deque）。 - Kelly Bundy

我看到你把“小”改成了“全部”。对于“大”的移位，最好的方法可能是先复制并删除短后缀，然后将其切片到前面。因此，理想情况下，首先确定两个部分中哪个更短，然后将其移出并移回。 - Kelly Bundy

哦，我刚注意到你在data.copy()和pop_append中添加了它。这对其他解决方案来说确实更公平，但现在它并没有真正意义。如果要创建一个新列表，可以使用tmp = data[shift:] tmp += data[:shift] return tmp。 - Kelly Bundy

那只是list_append的解决方案。 - Nico Schlömer

不，它不是这样的，它更好。list_append 复制了 2n 个元素并丢弃了 n 个。我的代码（来自我上一条评论）只复制了 n+shft 个元素并丢弃了 shift。 - Kelly Bundy

Answer 8

如果您只想迭代这些元素集，而不是构建单独的数据结构，请考虑使用迭代器来构造生成器表达式：

def shift(l,n):
    return itertools.islice(itertools.cycle(l),n,n+len(l))

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

- Phil H

Answer 9

这还要取决于你是想就地（改变它）移动列表，还是希望函数返回一个新列表。因为据我的测试结果，像这样的实现比添加两个列表的实现至少快二十倍：

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中找到。

- keturn

---

我个人更倾向于使用del l[:n]，而不是l[:n] = []。这只是一种不同的替代方式。 - tzot

哦，没错，好久不见的del操作。我经常会忘记del，这是一种语句而不是方法的列表操作。py3k是否改变了这个怪癖，还是我们还保留着它？ - keturn

del 在 Py3 仍然是一个语句。但是 x.__delitem__(y) <==> del x[y]，因此如果您更喜欢使用方法，则 l.__delitem__(slice(n)) 也是等效的，并且在2和3中都可以使用。 - martineau

Answer 10

如果您需要一个不可变的实现，可以使用以下方式：

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)

- Bittercoder