在python中旋转列表的有效方法

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

有没有更好的办法?

408310 次浏览
小开
最佳答案

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

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

数组没有列表的开销。

就纯粹的列表而言，你所拥有的就是你所希望做的。

小开

这取决于你这样做的时候想要发生什么:

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

可能更适合使用ringbuffer。它不是一个列表，尽管出于您的目的，它的行为可能足够像一个列表。

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

在环缓冲区中移动只是更新了头的位置也就是O(1)

小开

这也取决于您是想将列表移到合适的位置(改变它)，还是想让函数返回一个新列表。因为，根据我的测试，像这样的东西比你的实现(添加两个列表)至少快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处计时的各种实现

小开

如果只使用pop(0)呢?

list.pop([i])

删除列表中给定位置的项，并返回它。如果 如果没有指定索引，a.pop()将删除并返回其中的最后一项 列表中。(方法签名中i周围的方括号 表示参数是可选的，而不是您应该键入square 括号在那个位置。你会经常在 Python库引用)

小开

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

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

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

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

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

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

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(l,n):
return itertools.islice(itertools.cycle(l),n,n+len(l))


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

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

x = [1,2,3,4]
x.insert(0,x.pop())
编辑:你好，我刚刚发现这个解决方案的一个大问题! 考虑以下代码:

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())-solution相同，otherlist是一个独立于类的列表。在将otherlist的内容传递给MyClass之后。Classlist列表，调用shift_classlist()也会改变otherlist列表:

控制台输出:

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

有人知道为什么会这样吗?

小开

我想你想要的是这个:

a.insert(0, x)
小开

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

a.append(a.pop(0))
小开

下面的方法是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(*args):
return args[len(args)-2:]+args[:len(args)-2]
小开

另一个选择:

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

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

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

  • 双端队列。rotate是O (k) (k=元素数量)
  • list到deque的转换是O (n)
  • 列表。附加和列表。都是O (1)

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

为了便于说明，这里有一些1M迭代的计时示例:

需要类型转换的方法:

  • 带有deque对象的deque.rotate: 0.12380790710449219秒(最快)
  • deque.rotate类型转换:6.853878974914551秒
  • np.roll with 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

如果你需要创建nparray

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

如果你已经有nparray:

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

我认为你有最有效的方法

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

用例是什么?通常，我们并不需要完全移位的数组——我们只需要访问移位数组中的少量元素。

获取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
小开

以下函数将发送的列表复制到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

测试:

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)

输出:

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

Jon Bentley在编程的珍珠(第2列)中描述了一个优雅而高效的算法，用于将__abc0元素向量x向左旋转i位置:

让我们把这个问题看作是将数组ab转换为数组 ba，但让我们也假设我们有一个函数，反转 数组的指定部分中的元素。从ab开始，我们 reverse a得到arb, reverse b得到 arbr，然后反转整个 来获取(arbr)r， 也就是ba。这将产生以下代码 旋转:< / p > 
reverse(0, i-1)
reverse(i, n-1)
reverse(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']
小开

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

事实证明凯利·邦迪的建议

tmp = data[shift:]
tmp += data[:shift]

在所有轮班中都表现良好。

从本质上讲，perfplot执行增加大型数组的移位并测量时间。以下是调查结果:

shift = 1:

enter image description here

shift = 100:

enter image description here

代码重现情节:

import numpy
import perfplot
import collections




shift = 100




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




def list_append2(data):
tmp = data[shift:]
tmp += data[:shift]
return tmp




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):
data = data.copy()
for _ in range(shift):
data.append(data.pop(0))
return data




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

对于列表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', 'a'] list_shift(X,3)返回['d', 'e', 'f', 'a', 'b', 'c']

小开 
def solution(A, K):
if len(A) == 0:
return A


K = K % len(A)


return A[-K:] + A[:-K]


# use case
A = [1, 2, 3, 4, 5, 6]
K = 3
print(solution(A, K))

例如，给定

A = [3, 8, 9, 7, 6]
K = 3

函数应该返回[9, 7, 6, 3, 8]。进行了三次轮换:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

再举一个例子

A = [0, 0, 0]
K = 1

函数应该返回[0, 0, 0]

鉴于

A = [1, 2, 3, 4]
K = 4

函数应该返回[1, 2, 3, 4]

小开

我一直在寻找解决这个问题的方法。这就解决了O(k)的问题。

def solution(self, list, k):
r=len(list)-1
i = 0
while i<k:
temp = list[0]
list[0:r] = list[1:r+1]
list[r] = temp
i+=1
return list
小开

我是“守旧派”。我在最低延迟、处理器时间和内存使用中定义效率，我们的克星是臃肿的库。所以只有一个正确的方法:

    def rotatel(nums):
back = nums.pop(0)
nums.append(back)
return nums
小开

下面是一个高效的算法，不需要使用任何额外的数据结构:

旋转(nums: List[int]， k: int):

    k = k%len(nums)
l, r = 0, len(nums)-1
while (l<r):
nums[l], nums[r]= nums[r], nums[l]
l,r=l+1,r-1
    

l,r = 0, k-1
while (l<r):
nums[l], nums[r]=nums[r], nums[l]
l,r=l+1,r-1
        

l,r=k,len(nums)-1
while (l<r):
nums[l], nums[r]=nums[r], nums[l]
l,r=l+1,r-1

提交答案