[New-bugs-announce] [issue13351] Strange time complexity when creating nested lists
Jonas LM
report at bugs.python.org
Sun Nov 6 00:56:42 CET 2011
New submission from Jonas LM <quakes0 at gmail.com>:
Consider the following snippets:
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
Both of these snippets seem like they should run in O(n^2), right?
Observe the following test runs:
>>> 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
While simple_lists() seem to run roughly in O(n^2), it seems like lists() runs in upwards of O(n^3) or worse! Something funky is going on, and I have no idea what.
----------
components: None
messages: 147126
nosy: quakes
priority: normal
severity: normal
status: open
title: Strange time complexity when creating nested lists
type: performance
versions: Python 2.6
_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13351>
_______________________________________
More information about the New-bugs-announce
mailing list