Does heapsort make more sense for EDA algorithms ?
Just a random thought - given that netlist representations of most HDL appear in the form of unbounded trees (parents with greater than 2 children), this can be most easily be represented by list of lists.
Now, if we use a custom memory manager that pre-allocates large chunks, this means that the lists which will be created, be most probably contiguous in memory.. or we can make them contiguous, without loss of great processing power. This in turn means that they are similar to arrays.
Now, heapsort will perform with O(n log(n) ) upper-bounded complexity. But, if the array like structure is enforced, it will be very easy to map it to a similar heap structure (just re-ordering). Which means that heapsort may have better cache-performance than, say quicksort (cos the temporary space required is inside the orginal array heap).
Just a thought.
Now, if we use a custom memory manager that pre-allocates large chunks, this means that the lists which will be created, be most probably contiguous in memory.. or we can make them contiguous, without loss of great processing power. This in turn means that they are similar to arrays.
Now, heapsort will perform with O(n log(n) ) upper-bounded complexity. But, if the array like structure is enforced, it will be very easy to map it to a similar heap structure (just re-ordering). Which means that heapsort may have better cache-performance than, say quicksort (cos the temporary space required is inside the orginal array heap).
Just a thought.
This entry was posted
on 9/29/2005 at 9/29/2005 08:50:00 PM.
