In article <14949.19028.404458.318735@tzadkiel.efn.org>,
Steve VanDevender <stevev@efn.org> writes:
> Ton Hospel writes:
> > In article <UTC200101161350.OAA141869.aeb@ark.cwi.nl>,
> > Andries.Brouwer@cwi.nl writes:
> > > I am afraid I have missed most earlier messages in this thread.
> > > However, let me remark that the problem of assigning a
> > > file descriptor is the one that is usually described by
> > > "priority queue". The version of Peter van Emde Boas takes
> > > time O(loglog N) for both open() and close().
> > > Of course this is not meant to suggest that we use it.
> > >
> > Fascinating ! But how is this possible ? What stops me from
> > using this algorithm from entering N values and extracting
> > them again in order and so end up with a O(N*log log N)
> > sorting algorithm ? (which would be better than log N! ~ N*logN)
> >
> > (at least the web pages I found about this seem to suggest you
> > can use this on any set with a full order relation)
>
> How do you know how to extract the items in order, unless you've already
> sorted them independently from placing them in this data structure?
Because "extract max" is a basic operation of a priority queue,
which I just do N times.
>
> Besides, there are plenty of sorting algorithms that work only on
> specific kinds of data sets that are better than the O(n log n) bound
> for generalized sorting. For example, there's the O(n) "mailbox sort".
> You have an unordered array u of m integers, each in the range 1..n;
> allocate an array s of n integers initialized to all zeros, and for i in
> 1..m increment s[u[i]]. Then for j in 1..n print j s[j] times. If n is
> of reasonable size then you can sort that list of integers in O(m) time.
Yes, I know. that's why you see the "any set with a full order relation"
in there. That basically disallows using extra structure of the elements.
Notice that the radix sort you describe basically hides the log N in the
the representation of a number of max n (which has a length that is
basically log n). It just doesn't account for that because we do the
operation on processors where these bits are basically handled in parallel,
and so do not end up in the O-notation. Any attempt to make radix sort
handle arbitrary width integers on a fixed width processor will make the
log N reappear.
Having said that, in the particular case of fd allocation, we DO have
additional structure (in fact, it's indeed integers in 0..n). So I can
very well imagine the existance of a priority queue for this where the
basic operators are better than O(log N). I just don't understand how
it can exist for a generic priority queue algorithm (which the
Peter van Emde Boas method seems to be. Unfortunately I have found no
full description of the algorithm that's used to do the insert/extract
in the queue nodes yet).
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Jan 23 2001 - 21:00:14 EST