Python中高效旋转列表的方法

Question

Python中高效旋转列表的方法

349

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

有更好的方法吗？

- D R

4

numpy.roll 函数用于将数组沿指定轴滚动。该函数接受两个参数：a 是需要滚动的数组，shift 是滚动的偏移量。

import numpy as np

a = np.array([1, 2, 3, 4, 5])
print(np.roll(a, 2))  # [4 5 1 2 3]

在上面的示例中，原始数组 [1, 2, 3, 4, 5] 沿着其第一个轴滚动了 2 个位置。因此，最后两个元素 4 和 5 移动到了数组开头，而前三个元素 1、2 和 3 则被推到了数组的末尾。 - BoltzmannBrain

2

我认为“rotate”是正确的词，而不是“shift”。 - codeforester

5

“真正”正确的答案是，在首次使用列表时，您不应该旋转它。创建一个“指针”变量，指向您想要“头部”或“尾部”所在的逻辑位置，并更改该变量，而不是移动列表中的任何项。查找“模数”运算符%以高效地将指针“包裹”在列表的开头和结尾。 - cnd

3

根据旋转的频率和需要迭代的次数，单个“真实”的旋转可以优于反复计算索引。按照要求，这是实际旋转列表的唯一方法。是否需要旋转列表，或者是否应该使用不同的数据结构，需要更多上下文才能回答。 - chepner

1

@cnd 如果列表需要传递给我们无法修改的Python模块，您的建议是否仍然有效？ - root

显示剩余2条评论

27个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wese3112 · Answer 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())-解决方案相同，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。我不知道这是否是一个bug，但我认为更可能是我误解了某些东西。

你们中有人知道这是为什么吗？

- Light Bringer · Answer 2

我是“老派”的，我将效率定义为最低的延迟、处理器时间和内存使用率，我们的劲敌是臃肿的库。因此，只有一种正确的方法：

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

- Ankit · Answer 3

我正在寻找一个针对这个问题的就地解决方案。这个方案在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

- rnso · Answer 4

以下函数将发送列表复制到临时列表中，以便弹出函数不会影响原始列表：

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]

- helcode · Answer 5

对于一个列表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']

- Nick Lee · Answer 6

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

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

- Khaled Khairy · Answer 7

以下是一种高效的算法，不需要使用任何额外的数据结构：

def rotate(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