logo标签列表

Python中高效旋转列表的方法

pythonlist
349

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

有更好的方法吗？

4
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
2
我认为“rotate”是正确的词，而不是“shift”。 - codeforester
5
“真正”正确的答案是，在首次使用列表时，您不应该旋转它。创建一个“指针”变量，指向您想要“头部”或“尾部”所在的逻辑位置，并更改该变量，而不是移动列表中的任何项。查找“模数”运算符%以高效地将指针“包裹”在列表的开头和结尾。 - cnd
3
根据旋转的频率和需要迭代的次数，单个“真实”的旋转可以优于反复计算索引。按照要求，这是实际旋转列表的唯一方法。是否需要旋转列表，或者是否应该使用不同的数据结构，需要更多上下文才能回答。 - chepner
1
@cnd 如果列表需要传递给我们无法修改的Python模块，您的建议是否仍然有效？ - root
显示剩余2条评论
27个回答
4
也许环形缓冲区更适合。它不是列表，尽管它可能会对您的目的有足够的类似列表的行为。
问题在于列表上的移位效率是O(n)，对于足够大的列表来说，这变得非常重要。
在环形缓冲区中进行移位只需更新头位置，复杂度是O(1)。
3

我想你正在寻找这个：

a.insert(0, x)
1
我没有看到问题和你的回答之间的关系。你能解释一下吗？ - Wolf
3
如果您的目标是提高效率，（循环？内存？）您最好查看数组模块：http://docs.python.org/library/array.html。
数组没有列表的开销。
就纯列表而言，您所拥有的已经是最好的了。
2
另一种选择：
def move(arr, n):
    return [arr[(idx-n) % len(arr)] for idx,_ in enumerate(arr)]
2
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]

举个例子，假设

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

这个函数应该返回[0, 0, 0]

给定

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

该函数应该返回[1, 2, 3, 4]。
1
以下方法是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中，与其他方法相比，这种方法极其低效，因为它不能利用任何片段的本地实现。
其实你可以使用list.pop和list.append。如果你写了一个12行的O(n)函数，那并不是语言的问题，而是你可以只写"l.append(l.pop(0))"，这样就是常数时间了。 - Purrell
l.append(l.pop(0)) 的时间复杂度为O(n)（因为l.pop(0)必须移动每个元素），因此，如果您想要移动m个值，则复杂度实际上是O(n*m)。我提供的算法的复杂度无论移动的次数如何都是O(n)。实际上，这很慢，因为大量逻辑在Python操作中完成，而不是C（list.pop在c中实现，请参见https://github.com/python/cpython/blob/master/Objects/listobject.c）。 - DRayX
1

我有类似的东西。例如，将其向右移动两个位置...

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

我认为你已经找到了最有效的方法。

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

Jon Bentley在编程珠玑（第2篇）中描述了一种优雅且高效的算法，用于将n个元素的向量x左移i个位置：

Let's view the problem as transforming the array ab into the array ba, but let's also assume that we have a function that reverses the elements in a specified portion of the array. Starting with ab, we reverse a to get arb, reverse b to get arbr, and then reverse the whole thing to get (arbr)r, which is exactly ba. This results in the following code for rotation:

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']
1
2
更新：请参考以下链接以获取更好的参考资料：http://wiki.python.org/moin/TimeComplexity，使用`collections.dequeue`的pop和appendleft方法，它们都是O(1)操作。在我上面的第一个答案中，insert是O(n)。 - herrfz
1
应该是 collections.deque。 - herrfz
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接