_siftup and _siftdown implementation

Sven R. Kunze srkunze at mail.de
Fri Feb 5 11:35:37 EST 2016


again for the list:
###################


import random

from xheap import RemovalHeap


class X(object):
     c = 0
     def __init__(self, x):
         self.x = x
     def __lt__(self, other):
         X.c += 1
         return self.x < other.x

n = 100000

for jj in range(5):
     items = [X(i) for i in range(n)]
     random.shuffle(items)
     heap = RemovalHeap(items)

     random.shuffle(items)
     for i in items:
         heap.remove(i)

     print(X.c)
     X.c = 0


(note to myself: never copy PyCharm formatting strings to this list).

On 05.02.2016 17:27, Sven R. Kunze wrote:
> Hi srinivas,
>
> I wrote this simple benchmark to measure comparisons:
>
> import random
>
> from xheapimport RemovalHeap
>
>
> class X(object):
>     c =0 def __init__(self, x):
>         self.x = x
>     def __lt__(self, other):
>         X.c +=1 return self.x < other.x
>
> n =100000 for jjin range(5):
>     items = [X(i)for iin range(n)]
>     random.shuffle(items)
>     heap = RemovalHeap(items)
>
>     random.shuffle(items)
>     for i  in items:
>         heap.remove(i)
>
>     print(X.c)
>     X.c =0
>
>
> old version:
> 430457
> 430810
> 430657
> 429971
> 430583
>
> your pull request version:
> 426414
> 426045
> 425437
> 425528
> 425522
>
>
> Can we do better here?
>
> Best,
> Sven



More information about the Python-list mailing list