在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]
有没有更好的办法?
当前回答
这也取决于您是想将列表移到合适的位置(改变它),还是想让函数返回一个新列表。因为,根据我的测试,像这样的东西比你的实现(添加两个列表)至少快20倍:
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上有一些计时
其他回答
下面是一个高效的算法,不需要使用任何额外的数据结构:
旋转(nums: List[int], k: int):
k = k%len(nums)
l, r = 0, len(nums)-1
while (l<r):
nums[l], nums[r]= nums[r], nums[l]
l,r=l+1,r-1
l,r = 0, k-1
while (l<r):
nums[l], nums[r]=nums[r], nums[l]
l,r=l+1,r-1
l,r=k,len(nums)-1
while (l<r):
nums[l], nums[r]=nums[r], nums[l]
l,r=l+1,r-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]
如果你只想遍历这些元素集,而不是构造一个单独的数据结构,可以考虑使用迭代器来构造一个生成器表达式:
def shift(l,n):
return itertools.islice(itertools.cycle(l),n,n+len(l))
>>> list(shift([1,2,3],1))
[2, 3, 1]
我也有类似的事情。例如,移动两个…
def Shift(*args):
return args[len(args)-2:]+args[:len(args)-2]
以下函数将发送的列表复制到templist,这样pop函数不会影响原始列表:
def shift(lst, n, toreverse=False):
templist = []
for i in lst: templist.append(i)
if toreverse:
for i in range(n): templist = [templist.pop()]+templist
else:
for i in range(n): templist = templist+[templist.pop(0)]
return templist
测试:
lst = [1,2,3,4,5]
print("lst=", lst)
print("shift by 1:", shift(lst,1))
print("lst=", lst)
print("shift by 7:", shift(lst,7))
print("lst=", lst)
print("shift by 1 reverse:", shift(lst,1, True))
print("lst=", lst)
print("shift by 7 reverse:", shift(lst,7, True))
print("lst=", lst)
输出:
lst= [1, 2, 3, 4, 5]
shift by 1: [2, 3, 4, 5, 1]
lst= [1, 2, 3, 4, 5]
shift by 7: [3, 4, 5, 1, 2]
lst= [1, 2, 3, 4, 5]
shift by 1 reverse: [5, 1, 2, 3, 4]
lst= [1, 2, 3, 4, 5]
shift by 7 reverse: [4, 5, 1, 2, 3]
lst= [1, 2, 3, 4, 5]