在Python中创建嵌套列表的时间复杂性
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了在Python中创建嵌套列表的时间复杂性，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1748字，纯文字阅读大概需要3分钟。
内容图文
我在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),而list()似乎增长了O(n ^ 3)！
这里发生了什么？这个怪癖完全破坏了我的代码的复杂性,我无法解释为什么它会这样.有人有什么想法吗？
编辑：列表理解似乎会导致相同的复杂性问题.
重新定义list()喜欢
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)-快).
edit2：进一步研究该问题后,似乎是由垃圾收集器引起的.运行gc.disable()之后,这是原始list()定义的结果：
>>> for i in [1000, 2000, 4000]: lists(i)
...
0.155457019806
0.616811990738
2.38965821266
这真是整洁的O(n ^ 2).
故事的寓意：不要相信垃圾收集器！
解决方法:
在我的机器上
for i in [1000, 2000, 4000]: lists(i)
给
0.994000196457
4.31200003624
17.9900000095
这是一个很好的整洁的O(n ^ 2).最后一个消耗1GB的内存,因此list(8000)破坏了硬盘驱动器并导致我的机器行为异常. delnan可能是正确的,我会在操作过程中检查计算机的可用内存和python的内存消耗.
内容总结
以上是互联网集市为您收集整理的在Python中创建嵌套列表的时间复杂性全部内容，希望文章能够帮你解决在Python中创建嵌套列表的时间复杂性所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。