有效的方法来移动Python中的列表

在Python中移动列表的最有效的方法是什么？ 现在我有这样的东西：

>>> def shift(l, n): ... return l[n:] + l[:n] ... >>> l = [1,2,3,4] >>> shift(l,1) [2, 3, 4, 1] >>> shift(l,2) [3, 4, 1, 2] >>> shift(l,0) [1, 2, 3, 4] >>> shift(l,-1) [4, 1, 2, 3] 

有没有更好的办法？

Answer 1

一个collections.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] 

Answer 2

那刚刚使用pop(0)呢？

list.pop([i])

删除列表中给定位置的项目，然后返回。 如果没有指定索引，则a.pop()将删除并返回列表中的最后一个项目。 （方法签名中方括号表示该参数是可选的，而不是在该位置input方括号，在Python库参考中经常会看到这种表示法。

Answer 3

这取决于你想要发生什么，当你这样做：

 >>> shift([1,2,3], 14) 

你可能想改变你的：

 def shift(seq, n): return seq[n:]+seq[:n] 

至：

 def shift(seq, n): n = n % len(seq) return seq[n:] + seq[:n] 

Answer 4

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

Answer 5

如果你只是想遍历这些元素集而不是构build一个单独的数据结构，那么考虑使用迭代器来构造一个生成器expression式：

 def shift(l,n): return itertools.islice(itertools.cycle(l),n,n+len(l)) >>> list(shift([1,2,3],1)) [2, 3, 1] 

Answer 6

这也取决于你是否想要移动列表（改变它），或者如果你想要函数返回一个新的列表。 因为根据我的testing，像这样的东西至less比你的实现快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的各种实现;

Answer 7

我能想到的最简单的方法是：

 a.append(a.pop(0)) 

Answer 8

对于不可变的实现，你可以使用这样的东西：

 def shift(seq, n): shifted_seq = [] for i in range(len(seq)): shifted_seq.append(seq[(in) % len(seq)]) return shifted_seq print shift([1, 2, 3, 4], 1) 

Answer 9

只是一些笔记时间：

如果你从列表开始， l.append(l.pop(0))是你可以使用的最快的方法。 这可以单独用时间复杂度来表示：

• deque.rotate是O（k） （k =元素数）
• list到deque的转换是O（n）
• list.append和list.pop都是O（1）

所以如果你以deque对象开始，你可以deque.rotate()以O（k）为代价。 但是，如果起点是一个列表，使用deque.rotate()的时间复杂度是O（n）。 l.append(l.pop(0)在O（1）处更快。

为了说明起见，下面是一些1M迭代的示例时序：

需要types转换的方法：

• deque.rotate与deque对象： 0.12380790710449219秒 （最快）
• deque.rotate与types转换： 6.853878974914551秒
• 与nparray np.roll： 6.0491721630096436秒
• np.rolltypes转换： 27.558452129364014秒

这里提到的列表方法：

• l.append(l.pop(0)) ： 0.32483696937561035秒 （最快）
• “ shiftInPlace ”： 4.819645881652832秒
• …

使用的时序代码如下。

---

collections.deque

显示从列表创builddeques是O（n）：

 from collections import deque import big_o def create_deque_from_list(l): return deque(l) best, others = big_o.big_o(create_deque_from_list, lambda n: big_o.datagen.integers(n, -100, 100)) print best # --> Linear: time = -2.6E-05 + 1.8E-08*n 

如果你需要创builddeque对象：

1M次迭代@ 6.853878974914551秒

 setup_deque_rotate_with_create_deque = """ from collections import deque import random l = [random.random() for i in range(1000)] """ test_deque_rotate_with_create_deque = """ dl = deque(l) dl.rotate(-1) """ timeit.timeit(test_deque_rotate_with_create_deque, setup_deque_rotate_with_create_deque) 

如果你已经有了deque对象：

1M次迭代@ 0.12380790710449219秒

 setup_deque_rotate_alone = """ from collections import deque import random l = [random.random() for i in range(1000)] dl = deque(l) """ test_deque_rotate_alone= """ dl.rotate(-1) """ timeit.timeit(test_deque_rotate_alone, setup_deque_rotate_alone) 

np.roll

如果你需要创buildnparrays

1M次迭代@ 27.558452129364014秒

 setup_np_roll_with_create_npa = """ import numpy as np import random l = [random.random() for i in range(1000)] """ test_np_roll_with_create_npa = """ np.roll(l,-1) # implicit conversion of l to np.nparray """ 

如果你已经有nparrays：

1M次迭代@ 6.0491721630096436秒

 setup_np_roll_alone = """ import numpy as np import random l = [random.random() for i in range(1000)] npa = np.array(l) """ test_roll_alone = """ np.roll(npa,-1) """ timeit.timeit(test_roll_alone, setup_np_roll_alone) 

“转移到位”

不需要types转换

1M次迭代@ 4.819645881652832秒

 setup_shift_in_place=""" import random l = [random.random() for i in range(1000)] def shiftInPlace(l, n): n = n % len(l) head = l[:n] l[:n] = [] l.extend(head) return l """ test_shift_in_place=""" shiftInPlace(l,-1) """ timeit.timeit(test_shift_in_place, setup_shift_in_place) 

l.append（l.pop（0））

不需要types转换

1M迭代@ 0.32483696937561035

 setup_append_pop=""" import random l = [random.random() for i in range(1000)] """ test_append_pop=""" l.append(l.pop(0)) """ timeit.timeit(test_append_pop, setup_append_pop) 

Answer 10

如果效率是你的目标，（周期？内存？）你可能会更好看数组模块： http : //docs.python.org/library/array.html

数组没有列表的开销。

就纯粹的清单而言，你所拥有的就像你希望的那样好。

Answer 11

可能一个铃声更适合。 这不是一个列表，虽然它可能performance得足够像你的目的列表。

问题是列表中移动的效率是O（n），对于足够大的列表来说变得很重要。

在一个缓冲器中移动只是更新头部位置，即O（1）

Answer 12

我想你正在寻找这个：

 a.insert(0, x) 

Answer 13

我把这个成本模型作为参考：

http://scripts.mit.edu/~6.006/fall07/wiki/index.php?title=Python_Cost_Model

您的切片清单和连接两个子列表的方法是线性时间操作。 我会build议使用stream行，这是一个恒定时间的操作，例如：

 def shift(list, n): for i in range(n) temp = list.pop() list.insert(0, temp) 

Answer 14

我不知道这是否“高效”，但它也起作用：

 x = [1,2,3,4] x.insert(0,x.pop()) 

编辑：再次您好，我只是发现这个解决scheme的一个大问题！ 考虑下面的代码：

 class MyClass(): def __init__(self): self.classlist = [] def shift_classlist(self): # right-shift-operation self.classlist.insert(0, self.classlist.pop()) if __name__ == '__main__': otherlist = [1,2,3] x = MyClass() # this is where kind of a magic link is created... x.classlist = otherlist for ii in xrange(2): # just to do it 2 times print '\n\n\nbefore shift:' print ' x.classlist =', x.classlist print ' otherlist =', otherlist x.shift_classlist() print 'after shift:' print ' x.classlist =', x.classlist print ' otherlist =', otherlist, '<-- SHOULD NOT HAVE BIN CHANGED!' 

shift_classlist（）方法执行与我的x.insert（0，x.pop（））解决scheme相同的代码，otherlist是与类无关的列表。 将其他列表的内容传递给MyClass.classlist列表后，调用shift_classlist（）也会更改其他列表列表：

CONSOLE输出：

 before shift: x.classlist = [1, 2, 3] otherlist = [1, 2, 3] after shift: x.classlist = [3, 1, 2] otherlist = [3, 1, 2] <-- SHOULD NOT HAVE BIN CHANGED! before shift: x.classlist = [3, 1, 2] otherlist = [3, 1, 2] after shift: x.classlist = [2, 3, 1] otherlist = [2, 3, 1] <-- SHOULD NOT HAVE BIN CHANGED! 

我使用Python 2.7。 我不知道这是否是一个错误，但我认为这更可能是我在这里误解了一些东西。

你们有谁知道为什么会发生这种情况？

Answer 15

我有类似的事情。 例如，要移两个…

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

Answer 16

另一种select：

 def move(arr, n): return [arr[(idx-n) % len(arr)] for idx,_ in enumerate(arr)] 

Answer 17

下面的方法是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中，这种方法与其他方法相比效率非常低，因为它不能利用任何部分的本地实现。

Answer 18

我认为你有最有效的方法

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

Answer 19

什么是用例？ 通常，我们实际上并不需要完全移位的数组 – 我们只需要访问移位数组中的一些元素。

Python切片的运行时间是O（k）其中k是切片，所以切片旋转是运行时间N.旋转命令也是O（k）。 我们可以做得更好吗？

考虑一个非常大的数组（比方说，如此大的分片计算速度慢）。 另一种解决scheme是单独保留原始数组，并简单地计算在某种types的转换之后在我们期望的索引中存在的项目的索引。

因此访问一个移位的元素变成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 

Answer 20

与其他语言的换档function类似：

 def shift(l): x = l[0] del(l[0]) return x