在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]
有没有更好的办法?
当前回答
我能想到的最简单的方法:
a.append(a.pop(0))
其他回答
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])
对于一个不可变的实现,你可以使用这样的东西:
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)
对于一个列表X = ['a', 'b', 'c', 'd', 'e', 'f'],并且shift值小于列表长度,我们可以如下所示定义函数list_shift()
def list_shift(my_list, shift):
assert shift < len(my_list)
return my_list[shift:] + my_list[:shift]
的例子,
list_shift (X, 1)返回(' b ', ' c ', ' d ', ' e ', ' f ', ' '] list_shift (X, 3)返回(' d ', ' e ', ' f ', ' ', ' b ', ' c ']
Jon Bentley在Programming Pearls(第2专栏)中描述了一个优雅而高效的算法,用于将n元素向量x向左旋转i个位置:
让我们把这个问题看作是把数组ab转换成数组 Ba,但我们也假设我们有一个函数,它与 数组的指定部分中的元素。从ab开始 反转a得到arb,反转b得到 Arbr,然后反转整个 得到(arbr)r, 就是。这将产生以下代码 旋转: 反向张(0) 反向(n - 1),我 反向(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']
用例是什么?通常,我们并不需要完全移位的数组——我们只需要访问移位数组中的少量元素。
获取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