Message147126
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. |
|
Date |
User |
Action |
Args |
2011-11-05 23:56:42 | quakes | set | recipients:
+ quakes |
2011-11-05 23:56:42 | quakes | set | messageid: <1320537402.3.0.127960683982.issue13351@psf.upfronthosting.co.za> |
2011-11-05 23:56:41 | quakes | link | issue13351 messages |
2011-11-05 23:56:41 | quakes | create | |
|