在线性时间和常数空间内旋转数组（列表）

Question

如何确定这个Python算法使用恒定的内存？ 理论证明可以。

一本教科书*给出了这个练习：编写一个算法来“旋转”一个由n个整数组成的列表，换句话说，将列表值向右移动k个索引。但问题是该算法应在线性时间（与n成比例）和恒定内存（对于任何n都是相同的数量）内运行。 这个旋转可以通过切片完成：

>>> n = 5
>>> k = 3
>>> a = [i for i in range(n)]
>>> a = a[k:] + a[:k]
>>> a
[3, 4, 0, 1, 2]

我已经验证了将n加倍会使时间加倍，因此该算法的时间复杂度为线性。但是，我不确定它需要常量内存。我假设Python创建了一个新的数组作为两个切片的连接，并重新分配变量a给该数组。如果是这样的话，那么我认为所使用的内存与n成正比。但是，我如何验证呢？

练习还给出了一个对我来说很神秘的提示：“提示：反转三个子数组。”为什么需要创建三个子数组，而且为什么要反转它们？这是使用常量内存的诀窍吗？我知道你可以反转元素0到k-1的顺序，然后反转元素k到n-1的顺序，最后反转所有元素的顺序，但那似乎需要更多操作，而不是更少。

*书名为《Python编程导论》，作者为Sedgewick、Wayne和Dondero。我正在自学，不是为了学分。

- Rich006

---

它不能在常量内存中工作：在这里，您将暂时使用*O(n)*额外的内存。 - Willem Van Onsem

Answer 1

提示所指的技巧是：

将长度为N的序列向左旋转M个元素：

• 翻转整个序列
• 翻转后M个元素
• 翻转前N-M个元素

完成

例如向左旋转2个元素： 1234567 -> 7654321 -> 7654312 -> 3456712

是的，这就是使用常量内存的技巧，因为在原地执行反转数组的一部分很容易做到。我认为没有内置的方法可以反转子数组，所以您需要执行类似以下的操作：

i=0
j=n-m-1
while i<j:
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
    i+=1
    j-=1

在Python中，这种方式可能比你最初编写的方法慢，但仍然是线性时间。

- Matt Timmermans

---

@MattTimmermans 我认为这只是看起来很好...不幸的是，使用导入函数实现它会引起一些问题。当然你可以自己实现，但那有什么乐趣呢？ - Yonlif

@Yonif 在我来自的地方，自己实现正是最有乐趣的部分 :-) - Matt Timmermans

我的意思是 - 这不是“Pythonic方式”来做这件事，正如你自己所说，它会更慢 :) 您非常欢迎帮助我找到一种快速的方法，也许创建一个装饰器类并覆盖__len __()（或其他内容），以便反转函数仅反转前半部分！ - Yonlif

为了确保我理解正确：您的反转方法仅创建5个新变量，而不管n的大小，而我的切片方法会创建总长度为n的新列表。因此，您的方法使用恒定的内存，而我的方法使用线性内存。 - Rich006

输入的数组不计算。 - Matt Timmermans

Answer 2

相比于执行交换操作，你可以将单个元素保留并将其移动到下一个位置：

def rotate(array,offset): # positive offset rotates left to right
    if not array or not offset: return
    index,value = 0,array[0]
    for _ in array:
        index = (index+offset)%len(array)
        value,array[index] = array[index],value
    
A = [1,2,3,4,5,6,7]
rotate(A,3)
print(A)

# [5, 6, 7, 1, 2, 3, 4]

由于Python可以使用负数索引从数组末尾开始，因此通过给定负偏移量，该函数也可以将数组向右旋转到左侧：

A = [1,2,3,4,5,6,7]
rotate(A,-3)
print(A)

# [4, 5, 6, 7, 1, 2, 3] 

- Alain T.

Answer 3

我知道这个解决方案返回的是迭代器而不是列表，但对于其他寻找此问题答案的人来说可能很好。

我们可以使用 itertools 来实现“惰性”连接。

import os
import psutil
import itertools


process = psutil.Process(os.getpid())
print(f"initial memory: {process.memory_info().rss}")

n = 10000
k = n // 2
a = [i for i in range(n)]

print(f"memory after creating the array: {process.memory_info().rss}")

res = itertools.chain(itertools.islice(a, k, None), itertools.islice(a, k))

print(f"memory after reordering the array: {process.memory_info().rss}")

for a in res:
    print(a)
print()

print(f"memory at the end: {process.memory_info().rss}")

结果将是：

初始内存：13025280
创建数组后的内存：13328384
重新排序数组后的内存：13328384
5000
5001...
结束时的内存：13385728

使用原始解决方案，内存将更高...

同样，此结果将返回一个迭代器。

有趣的事实：一次性打印整个列表实际上会增加进程的内存，因为输出缓冲区。

- Yonlif

---

@AlainT。我知道这是一个迭代器，我在我的答案中已经多次说明了。由于“for”正在使用“next”，所以不会有第二个分配（您也可以检查内存打印）。再次强调，我知道我没有原地旋转，但这对未来的用户来说是一个相关的答案。 - Yonlif