Re: [Tcllib-devel] pheap - alternate prioqueue ipmlementation

[Murr, F. <flo...@si...>]

I use pheap in the context of some Dijkstra search algorithms, where
'contains', 'insert', 'promote' and 'popmin' are heavily used.
To compare performance, I do sorting of random numbers using

proc pheap::cmp-numeric-count {a b} {
    incr ::pheap::cmpCount   ;# for Testing!
    expr {($a<$b)?-1:(($a==$b)?0:1)}
} 

So that I know how many calls to the compare-callback have been made and
I measure milliseconds.
Since sorting 

proc pheap::sort {alist args} {
    set q [::pheap::pheap {*}$args ::pheap[incr ::pheap::counter]]
    foreach i $alist { $q insert [incr cnt] $i }

    set rval {}
    while {[$q popmin cnt i]} { lappend rval $i }
    $q destroy
    set rval
}

just uses 'insert', but not the *very* important 'promote' (a major
reason for using a priority queue), it is no fair test!
(But it gives some indication whether pheap0.1 or pheap0.2 is faster
with respect to 'insert' and 'popmin')

To compare two prioques one should define a (big!) random number of
'setp' ('insert' | 'promote', but *not* 'demote' (nobody needs that))
and 'popmin' operations and let both prioques perform them.
Repeat that any number of times and calculate the average time used.

That probably might indicate a way of how to find out which
priority-queue outperforms the other.

Regards,
- Florian

-----Original Message-----
From: Andreas Kupries [mailto:and...@ac...] 
Sent: Friday, February 06, 2009 5:50 PM
To: Tcllib Developers
Cc: Andreas Kupries Home; Murr, Florian
Subject: pheap - alternate prioqueue ipmlementation

pheap - Priority Queue
	A Pairing-heap [1] priority queue in Tcl

[0]	http://wiki.tcl.tk/22428
[1]	http://en.wikipedia.org/wiki/Pairing_heap

<quote [0]>
Comparison with package struct::prioqueue: Prioqueue lacks the sometimes
essential functionality of setp or promote and its implementation seems
to be a bubblesort in disguise, which is detrimental to performance if
one is dealing with many items. Pheap on the other hand, reflects more
closely the intention and performance characteristics of a priority
queue and it seems to be more versatile, too. (The interface of get and
peek in struct::prioqueue makes me frown, too. Imho the distinction of
lists and strings should not be blurred more, but less.) </quote>

Hm. We have no benchmarks for the struct::prioqueue code ...
	Time to write some it seems ...
	However, what are sensible benchmarks for prioqueue ...

Andreas