在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]
有没有更好的办法?
当前回答
如果你只想遍历这些元素集,而不是构造一个单独的数据结构,可以考虑使用迭代器来构造一个生成器表达式:
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]
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]
用例是什么?通常,我们并不需要完全移位的数组——我们只需要访问移位数组中的少量元素。
获取Python切片是运行时O(k),其中k是切片,因此切片旋转是运行时n。deque旋转命令也是O(k)。我们能做得更好吗?
考虑一个非常大的数组(比方说,大到切片的计算速度很慢)。另一种解决方案是保留原始数组,并简单地计算在某种移位后存在于我们所期望的索引中的项的索引。
访问移位的元素就变成了O(1)。
def get_shifted_element(original_list, shift_to_left, index_in_shifted):
# back calculate the original index by reversing the left shift
idx_original = (index_in_shifted + shift_to_left) % len(original_list)
return original_list[idx_original]
my_list = [1, 2, 3, 4, 5]
print get_shifted_element(my_list, 1, 2) ----> outputs 4
print get_shifted_element(my_list, -2, 3) -----> outputs 2
我是“老派”,我定义了最低延迟,处理器时间和内存使用效率,我们的克星是臃肿的库。所以只有一个正确的方法:
def rotatel(nums):
back = nums.pop(0)
nums.append(back)
return nums
可能更适合使用ringbuffer。它不是一个列表,尽管出于您的目的,它的行为可能足够像一个列表。
问题是列表上移位的效率是O(n),这对于足够大的列表来说非常重要。
在环缓冲区中移动只是更新了头的位置也就是O(1)