Python中创建嵌套列表的时间复杂度

Question

我在使用Python 2.6.6创建嵌套列表时遇到了一些问题。

考虑以下两个函数:

def lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = []
    print time.time() - start_time

def simple_lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = False
    print time.time() - start_time

它们都分配了一个大小为n*n的数组。一个将所有值分配为“False”，而另一个将所有值分配为空列表。就我所见，它们应该以O(n^2)的速度运行。然而，情况似乎并非如此... 观察以下测试运行：

>>> for i in [4000, 8000, 16000]: simple_lists(i)
2.11170578003
8.67467808723
34.0958559513
>>> for i in [1000, 2000, 4000]: lists(i)
1.13742399216
7.39806008339
78.0808939934

正如您所看到的，simple_lists()函数似乎增长大约是O(n^2)，而lists()函数似乎增长超过了O(n^3)！

这是怎么回事？这个怪癖完全毁了我的代码复杂度，我无法解释它为什么会表现出这样的行为。有没有人有什么想法？

编辑：列表推导式似乎引起了相同的复杂度问题。

将lists()重新定义为

def lists(n):
    start_time = time.time()
    lists = [[[] for y in xrange(n)] for x in xrange(n)]
    print time.time() - start_time

导致以下结果。

>>> for i in [1000, 2000, 4000]: lists(i)
0.388785839081
4.45830011368
65.6449248791

...这个问题仍然以比O(n^2)更快的速度增长（甚至比O(n^3)更快 - 哎呀）。

编辑2：进一步研究后，似乎是由垃圾收集器引起的。在运行gc.disable()之后，这是使用原始lists()定义的结果：

>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266

这个算法的时间复杂度相当高，为O(n^2)。

故事的寓意是：不要信任垃圾回收器！

- quakes

---

[[E for y in xrange(N)] for x in xrange(N)] - Cat Plus Plus

@CatPlusPlus：尝试了你的建议（见编辑），但并没有解决复杂性问题。 - quakes

哦，我不知道复杂度，但它肯定有更好的语法。如果你想要高效的固定大小的多维数组，你应该使用NumPy。 - Cat Plus Plus

Answer 1

在我的电脑上

for i in [1000, 2000, 4000]: lists(i)

提供

0.994000196457
4.31200003624
17.9900000095

这是一个漂亮的，整洁的O(n^2)算法。最后一个算法消耗了1GB的内存，因此lists(8000)会导致硬盘卡顿并使机器运行不正常。delnan可能是正确的，我建议在操作期间检查您计算机的可用内存和Python的内存消耗情况。

- James Moughan

Answer 2

原来奇怪的行为是由垃圾回收机制引起的。使用 gc.disable() 关闭它后，产生了以下结果:

>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266

适用于O(n^2)的完美解决方案。

- quakes

Answer 3

先生成第一个列表，它将在O(n)时间内完成。

def simple_list(n):
    import time
    start_time = time.process_time()
    k=[[] for y in range(n)]
    lists = [k for x in range(n)]
    end_time=time.process_time()
    print (end_time - start_time)

- Dean Yang