Subject: Re: sorting... From: Erik Naggum <erik@naggum.no> Date: 1998/12/15 Newsgroups: comp.lang.lisp Message-ID: <3122754335784936@naggum.no> * Marco Antoniotti <marcoxa@copernico.parades.rm.cnr.it> | Ahem! :) | Insertion in a priority queue should be O(lg n). Most likely, you are | doing at least O(n lg n) with ... the priority queues are supposed to be depleted very quickly, and have an average length of 1.2 elements before sorting. when a particular queue gets stuck, it normally gets unstuck before the length reaches 10. when a queue is stuck for a long time, which happens to about 1% of the queues over the course of a week, the cost of monitoring it dwarfes the cost of the insertions. so the sorting time really is irrelevant. it's useful as an example of when a simple-minded algorithm is sufficient because other parts of the system profit more from optimization than this particular part. a long queue length really is an important problem, and making the priority queue insert fast is irrelevant in the big picture. popping off the highest-priority element when the queue starts to drain, however, needs to be very fast and simple because in the event that the queue has gotten quite long, releasing it is a serious hit to the system all at once, compared to the very well distributed O(n lg n) costs of the insertions. I actually found it quite amusing that I was somewhat unnerved by this code and spent a lot of real time testing whether it was a bottle-neck, returning to it time and again to see if it could be fixed. however, as is quite often the case with optimizations, my hunch was all wrong, and it was way more important to make deletion from the queue O(1). | Here is the solution. It is old code and I will be willing to include | any changes and to change the copyright. thanks. I appreciate it. #:Erik -- man who cooks while hacking eats food that has died twice.