Re: Is sendfile all that sexy?

[Steve VanDevender]

Ton Hospel writes:
 > In article <[e-mail]>,
 > 	[e-mail] 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?

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.