在python中移动列表的有效方法

Question

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

有没有更好的办法？

Answer 1

A 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()删除并返回列表中的最后一项.(i方法签名周围的方括号表示该参数是可选的,而不是您应该在该位置键入方括号.您将在Python Library Reference中经常看到这种表示法.)

Answer 3

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 4

这取决于你执行此操作时想要发生的事情:

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

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

a.append(a.pop(0))

Answer 6

如果您只想迭代这些元素集而不是构造单独的数据结构,请考虑使用迭代器来构造生成器表达式:

def shift(l,n):
    return itertools.islice(itertools.cycle(l),n,n+len(l))

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

Answer 7

这还取决于您是否要将列表移位(改变它),或者您希望函数返回新列表.因为,根据我的测试,这样的事情至少比你的实现增加了两个列表快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 8

关于时间的一些注意事项:

如果您从列表开始,l.append(l.pop(0))则是您可以使用的最快方法.这可以单独显示时间复杂度:

• deque.rotate是O(k)(k =元素数)
• 列表到双端转换是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迭代的一些示例时序:

需要类型转换的方法:

• deque.rotate与deque对象:0.12380790710449219秒(最快)
• deque.rotate带类型转换:6.853878974914551秒
• np.roll与nparray:6.0491721630096436秒
• np.roll带类型转换:27.558452129364014秒

列出这里提到的方法:

• l.append(l.pop(0)):0.32483696937561035秒(最快)
• " shiftInPlace":4.819645881652832秒
• ...

使用的时序代码如下.

collections.deque

显示从列表创建deques是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

如果需要创建deque对象:

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

如果你需要创建nparrays

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)

"转移到位"

不需要类型转换

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

不需要类型转换

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 9

我对此也很感兴趣，并将一些建议的解决方案与perfplot（我的一个小项目）进行了比较。

原来是

for _ in range(n):
    data.append(data.pop(0))

是迄今为止小班最快的方法n。

对于较大的n，

data[n:] + data[:n]

还不错

本质上，perfplot执行移位以增加大型阵列并测量时间。结果如下：

shift = 1：

shift = 100：

复制剧情的代码：

import numpy
import perfplot
import collections


shift = 100


def list_append(data):
    return data[shift:] + data[:shift]


def shift_concatenate(data):
    return numpy.concatenate([data[shift:], data[:shift]])


def roll(data):
    return numpy.roll(data, -shift)


def collections_deque(data):
    items = collections.deque(data)
    items.rotate(-shift)
    return items


def pop_append(data):
    for _ in range(shift):
        data.append(data.pop(0))
    return data


perfplot.save(
    "shift100.png",
    setup=lambda n: numpy.random.rand(n).tolist(),
    kernels=[list_append, roll, shift_concatenate, collections_deque, pop_append],
    n_range=[2 ** k for k in range(7, 20)],
    logx=True,
    logy=True,
    xlabel="len(data)",
)

Answer 10

对于不可变的实现，您可以使用以下内容：

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)