在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]
有没有更好的办法?
在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]
有没有更好的办法?
当前回答
我以这个成本模型作为参考:
http://scripts.mit.edu/~6.006/fall07/wiki/index.php?title=Python_Cost_Model
切片列表和连接两个子列表的方法是线性时间操作。我建议使用pop,这是一个常数时间操作,例如:
def shift(list, n):
for i in range(n)
temp = list.pop()
list.insert(0, temp)
其他回答
可能更适合使用ringbuffer。它不是一个列表,尽管出于您的目的,它的行为可能足够像一个列表。
问题是列表上移位的效率是O(n),这对于足够大的列表来说非常重要。
在环缓冲区中移动只是更新了头的位置也就是O(1)
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]
我能想到的最简单的方法:
a.append(a.pop(0))
如果你只想遍历这些元素集,而不是构造一个单独的数据结构,可以考虑使用迭代器来构造一个生成器表达式:
def shift(l,n):
return itertools.islice(itertools.cycle(l),n,n+len(l))
>>> list(shift([1,2,3],1))
[2, 3, 1]
另一个选择:
def move(arr, n):
return [arr[(idx-n) % len(arr)] for idx,_ in enumerate(arr)]