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.