在python中转换列表的有效方法。

What is the most efficient way to shift a list in python? Right now I have something like this:

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

Is there a better way?

有更好的办法吗?

21 个解决方案

#1

A collections.deque is optimized for pulling and pushing on both ends. They even have a dedicated rotate() method.

一个集合。deque被优化为拉动和推动两端。他们甚至有一个专用的旋转()方法。

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]

#2

What about just using pop(0)?

使用pop(0)怎么样?

list.pop([i])

list.pop([我])

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list. (The square brackets around the i in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

删除列表中给定位置的项，并返回它。如果没有指定索引，.pop()删除并返回列表中的最后一个项。(方法签名中i的方括号表示参数是可选的，而不是在该位置输入方括号。您将经常在Python库引用中看到这个符号。

#3

It depends on what you want to have happen when you do this:

这取决于你想要发生的事情:

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

You might want to change your:

你可能想要改变你的:

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

to:

:

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

#4

Numpy can do this using the roll command:

Numpy可以使用滚动命令来实现:

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

#5

If you just want to iterate over these sets of elements rather than construct a separate data structure, consider using iterators to construct a generator expression:

如果您只想遍历这些元素集，而不是构造一个单独的数据结构，那么可以考虑使用迭代器来构造一个生成器表达式:

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

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

#6

This also depends on if you want to shift the list in place (mutating it), or if you want the function to return a new list. Because, according to my tests, something like this is at least twenty times faster than your implementation that adds two lists:

这还取决于您是否想要将列表转换到适当的位置(改变它)，或者您希望函数返回一个新的列表。因为，根据我的测试，类似这样的东西至少要比你的实现快20倍。

def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

In fact, even adding a l = l[:] to the top of that to operate on a copy of the list passed in is still twice as fast.

实际上，即使添加一个l = l[:]到该操作的顶部，操作的列表的副本仍然是速度的两倍。

Various implementations with some timing at http://gist.github.com/288272

不同的实现，在http://gist.github.com/288272的时间点。

#7

Simplest way I can think of:

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

a.append(a.pop(0))

#8

For an immutable implementation, you could use something like this:

对于一个不可变的实现，您可以使用如下的方法:

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)

#9

Just some notes on timing:

只是一些关于时间的注释:

If you're starting with a list, l.append(l.pop(0)) is the fastest method you can use. This can be shown with time complexity alone:

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

• deque.rotate is O(k) (k=number of elements)
• 双端队列。旋转是O(k) (k=元素个数)
• list to deque conversion is O(n)
• O(n)
• list.append and list.pop are both O(1)
• 列表。附加和列表。流行音乐都是O(1)

So if you are starting with deque objects, you can deque.rotate() at the cost of O(k). But, if the starting point is a list, the time complexity of using deque.rotate() is O(n). l.append(l.pop(0) is faster at O(1).

因此，如果您从deque对象开始，您可以以O(k)的代价进行deque.rotate()。但是，如果起始点是一个列表，那么使用deque.rotate()的时间复杂度是O(n)。l.append(l.pop(0))在O(1)上更快。

Just for the sake of illustration, here are some sample timings on 1M iterations:

为了便于说明，这里有一些100万次迭代的样本计时:

Methods which require type conversion:

需要类型转换的方法:

• deque.rotate with deque object: 0.12380790710449219 seconds (fastest)
• 双端队列。以deque对象旋转:0.12380790710449219秒(最快)
• deque.rotate with type conversion: 6.853878974914551 seconds
• 双端队列。使用类型转换旋转:6.853878974914551秒。
• np.roll with nparray: 6.0491721630096436 seconds
• np。使用nparray: 6.0491721630096436秒。
• np.roll with type conversion: 27.558452129364014 seconds
• np。类型转换:27.558452129364014秒。

List methods mentioned here:

这里提到的列表方法:

• l.append(l.pop(0)): 0.32483696937561035 seconds (fastest)
• l.append(l.pop(0)):0.32483696937561035秒(最快)
• "shiftInPlace": 4.819645881652832 seconds
• “shiftInPlace”:4.819645881652832秒
• ...
• …

Timing code used is below.

使用的计时代码如下。

---

collections.deque

Showing that creating deques from lists is O(n):

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

If you need to create deque objects:

如果您需要创建deque对象:

1M iterations @ 6.853878974914551 seconds

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)

If you already have deque objects:

如果你已经有了deque对象:

1M iterations @ 0.12380790710449219 seconds

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

If you need to create nparrays

如果你需要创建nparray。

1M iterations @ 27.558452129364014 seconds

100万次迭代@ 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
"""

If you already have nparrays:

如果你已经有nparray:

1M iterations @ 6.0491721630096436 seconds

100万次迭代@ 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)

"Shift in place"

Requires no type conversion

不需要类型转换

1M iterations @ 4.819645881652832 seconds

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

Requires no type conversion

不需要类型转换

1M iterations @ 0.32483696937561035

1米迭代@ 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)

#10

If efficiency is your goal, (cycles? memory?) you may be better off looking at the array module: http://docs.python.org/library/array.html

如果效率是你的目标，(循环?)你最好看看数组模块:http://docs.python.org/library/array.html。

Arrays do not have the overhead of lists.

数组没有列表的开销。

As far as pure lists go though, what you have is about as good as you can hope to do.

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

#11

Possibly a ringbuffer is more suitable. It is not a list, although it is likely that it can behave enough like a list for your purposes.

可能一个环形缓冲区更合适。它不是一个列表，尽管它很可能会像列表一样为您的目的而运行。

The problem is that the efficiency of a shift on a list is O(n), which becomes significant for large enough lists.

问题是列表上的转换效率是O(n)，这对于足够大的列表来说是非常重要的。

Shifting in a ringbuffer is simply updating the head location which is O(1)

在ringbuffer中移动仅仅是更新头部位置，也就是O(1)

#12

I think you are looking for this:

我想你是在找这个:

a.insert(0, x)

#13

Another alternative:

另一个选择:

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

#14

I take this cost model as a reference:

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

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

http://scripts.mit.edu/ 6.006 / fall07 / wiki / index . php ?标题= Python_Cost_Model

Your method of slicing the list and concatenating two sub-lists are linear-time operations. I would suggest using pop, which is a constant-time operation, e.g.:

你的切片列表和连接两个子列表的方法是线性时间操作。我建议使用pop，它是一个常量时间操作，例如:

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

#15

I don't know if this is 'efficient', but it also works:

我不知道这是否“有效”，但它也有效:

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

EDIT: Hello again, I just found a big problem with this solution! Consider the following code:

编辑:你好，我刚刚发现这个解决方案有一个大问题!考虑下面的代码:

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!'

The shift_classlist() method executes the same code as my x.insert(0,x.pop())-solution, otherlist is a list indipendent from the class. After passing the content of otherlist to the MyClass.classlist list, calling the shift_classlist() also changes the otherlist list:

shift_classlist()方法执行与我的x.insert(0,x.pop())-解决方案相同的代码，其他列表是来自类的列表。将其他列表的内容传递给MyClass。classlist列表，调用shift_classlist()也会改变其他列表:

CONSOLE OUTPUT:

控制台输出:

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!

I use Python 2.7. I don't know if thats a bug, but I think it's more likely that I missunderstood something here.

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

Does anyone of you know why this happens?

你们当中有人知道为什么会这样吗?

#16

I have similar thing. For example, to shift by two...

我也有类似的事情。例如，要转换两个…

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

#17

The following method is O(n) in place with constant auxiliary memory:

下面的方法是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

Note that in python, this approach is horribly inefficient compared to others as it can't take advantage of native implementations of any of the pieces.

请注意，在python中，与其他方法相比，这种方法的效率非常低，因为它不能利用任何块的本机实现。

#18

I think you've got the most efficient way

我认为你的方法是最有效的。

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

#19

What is the use case? Often, we don't actually need a fully shifted array --we just need to access a handful of elements in the shifted array.

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

Getting Python slices is runtime O(k) where k is the slice, so a sliced rotation is runtime N. The deque rotation command is also O(k). Can we do better?

获取Python切片是运行时O(k)，其中k是切片，因此切片旋转是运行时N. deque旋转命令也是O(k)。我们可以做得更好吗?

Consider an array that is extremely large (let's say, so large it would be computationally slow to slice it). An alternative solution would be to leave the original array alone and simply calculate the index of the item that would have existed in our desired index after a shift of some kind.

考虑一个非常大的数组(比方说，这么大的数组在计算上要慢一些)。另一种解决方案是，仅保留原始数组，并简单地计算在某种类型转换之后，在我们期望的索引中存在的项的索引。

Accessing a shifted element thus becomes O(1).

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

#20

Following function copies sent list to a templist, so that pop function does not affect the original list:

下面的函数将列表发送到templist，这样pop函数不会影响原始列表:

def shift(lst, n, toreverse=False):
    templist = []
    for i in lst: templist.append(i)
    if toreverse:
        for i in range(n):  templist = [templist.pop()]+templist
    else:
        for i in range(n):  templist = templist+[templist.pop(0)]
    return templist

Testing:

测试:

lst = [1,2,3,4,5]
print("lst=", lst)
print("shift by 1:", shift(lst,1))
print("lst=", lst)
print("shift by 7:", shift(lst,7))
print("lst=", lst)
print("shift by 1 reverse:", shift(lst,1, True))
print("lst=", lst)
print("shift by 7 reverse:", shift(lst,7, True))
print("lst=", lst)

Output:

输出:

lst= [1, 2, 3, 4, 5]
shift by 1: [2, 3, 4, 5, 1]
lst= [1, 2, 3, 4, 5]
shift by 7: [3, 4, 5, 1, 2]
lst= [1, 2, 3, 4, 5]
shift by 1 reverse: [5, 1, 2, 3, 4]
lst= [1, 2, 3, 4, 5]
shift by 7 reverse: [4, 5, 1, 2, 3]
lst= [1, 2, 3, 4, 5]

#21

for similar functionality as shift in other languages:

与其他语言的转换功能类似:

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