python - improving heapq efficiency -

so find myself taking advantage of heapq calculations. however, problem working on, runs slow because heap gets pretty big.

i thought had option speed up. rather creating giant heap, make heap of heaps. but, surprisingly me, "more efficient" code slower. there's bit more overhead in more efficient code, thought win lot. having stripped down problem, i've got 2 functions same net calculation. f1 "naive" (and faster) version. f2 "improved" (but slower) version. random number generation in both, use same seed, same thing.

import random import heapq def f1():     random.seed(1)     q=[0]     while q:         value = heapq.heappop(q)         #print value         if value<0.5:             counter in range(16):                 heapq.heappush(q,value + 0.1 + (random.random()/1000))     print value  def f2():     random.seed(1)     q=[[0]]     while q:         subq = heapq.heappop(q)         value = heapq.heappop(subq)         #print value         if subq:             heapq.heappush(q,subq)         newq = []         if value<0.5:             counter in range(16):                 newq.append(value + 0.1 + (random.random()/1000))             heapq.heapify(newq)             heapq.heappush(q,newq)     print value 

why heap of heaps (f2) run slower? should call heappush same number of times, , heappop twice many times. size of heaps should smaller, expected run faster.

so wasn't pushing code hard enough. here's modified code. when subq made large, benefit after appears.

def f1(m,n):     random.seed(1)     q=[0]     counter in range(m):         value = heapq.heappop(q)         #print value         newcounter in range(n):             heapq.heappush(q,random.random())     print value #should same both methods, test  def f2(m,n):     random.seed(1)     q=[[0]]     counter in range(1000000):         subq = heapq.heappop(q)         value = heapq.heappop(subq)         #print value         if subq:             heapq.heappush(q,subq)         newq = []         newcounter in range(n):             newq.append(random.random())         heapq.heapify(newq)         heapq.heappush(q,newq)     print value #should same both methods, test 

when profile f1(1000000,10) , f2(1000000,10) run times of 10.7 seconds , 14.8 seconds. relevant details are:

f1:

ncalls tottime percall cumtime percall filename:lineno(function)

1000000 1.793 0.000 1.793 0.000 {_heapq.heappop}

10000000 3.856 0.000 3.856 0.000 {_heapq.heappush}

f2:

1000000 1.095 0.000 1.095 0.000 {_heapq.heapify}

2000000 2.628 0.000 2.628 0.000 {_heapq.heappop}

1999999 2.245 0.000 2.245 0.000 {_heapq.heappush}

10000000 1.114 0.000 1.114 0.000 {method 'append' of 'list' objects}

so net f2 loses out because of heappop, heapify , append. better on heappush.

but when go , challenge larger internal loop , run f1(1000,100000) , f2(1000,100000)

f1:

1000 0.015 0.000 0.015 0.000 {_heapq.heappop}

100000000 28.730 0.000 28.730 0.000 {_heapq.heappush}

f2:

1000 19.952 0.020 19.952 0.020 {_heapq.heapify}

2000 0.011 0.000 0.011 0.000 {_heapq.heappop}

1999 0.006 0.000 0.006 0.000 {_heapq.heappush}

100000000 6.977 0.000 6.977 0.000 {method 'append' of 'list' objects}

so better on heappush, , it's enough f2 runs faster (69 seconds versus 75 seconds).

so turns out hadn't pushed code sufficiently hard. needed things large enough many calls heappush became slower many calls heapify.