`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 thethe representation of a number of max n (which has a length that isbasically 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 sorthandle arbitrary width integers on a fixed width processor will make thelog N reappear.Having said that, in the particular case of fd allocation, we DO haveadditional structure (in fact, it's indeed integers in 0..n). So I canvery well imagine the existance of a priority queue for this where thebasic operators are better than O(log N). I just don't understand howit can exist for a generic priority queue algorithm (which thePeter van Emde Boas method seems to be. Unfortunately I have found nofull description of the algorithm that's used to do the insert/extractin the queue nodes yet).-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgPlease read the FAQ at http://www.tux.org/lkml/`