有效的方法来移动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] 

有没有更好的办法?

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

那刚刚使用pop(0)呢?

list.pop([i])

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

这取决于你想要发生什么,当你这样做:

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

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

如果你只是想遍历这些元素集而不是构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] 

这也取决于你是否想要移动列表(改变它),或者如果你想要函数返回一个新的列表。 因为根据我的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的各种实现;

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

 a.append(a.pop(0)) 

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

 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) 

只是一些笔记时间:

如果你从列表开始, 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) 

如果效率是你的目标,(周期?内存?)你可能会更好看数组模块: http : //docs.python.org/library/array.html

数组没有列表的开销。

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

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

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

在一个缓冲器中移动只是更新头部位置,即O(1)

我想你正在寻找这个:

 a.insert(0, x) 

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

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) 

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

 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。 我不知道这是否是一个错误,但我认为这更可能是我在这里误解了一些东西。

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

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

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

另一种select:

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

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

我认为你有最有效的方法

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

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

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 

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

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