Anonymous Monk says:
Well, you can't sort infinite streams.
Sometimes you can sort infinite streams. It depends on the stream and the sort order. Section 6.5.3 of Higher-Order Perl discusses it in some detail. The example on page 293-300 is to sort the contents of qmail's log file while the log is being written.
One kind of cool thing about the lazy streams is that if you implement quicksort in the straightforward way, you get a reasonably good lazy sorting function that does run in O(n log n) average time. And if you're only looking at a few elements from the front of the sorted result, the time is O(n).
Put another way, we sometimes laugh when beginners write this:
my ($minimum) = sort @items;
because we know that the sort is O(n log n), and there's a straightforward algorithm for the minimum that is O(n). But if your sort algorithm is implemented lazily, as it probably is if the array is actually a lazy list, then the code above does run in O(n) time, because the sort call only sorts enough of the list to find the minimum element. Code like that above does run in linear time in Haskell, for example. Of course, as you say, the whole stream must be resident in memory.
I didn't put this into HOP because although I thought it was delightful and fascinating, it didn't seem to have any immediate practical use.
| [reply]
[d/l] |
Sometimes you can sort infinite streams. It depends on the stream and the sort order.
I guess I'm still skeptical. Can you show some code? If you can't get to the end of the list, how can you know which element is smallest, so that you can put it first in the output? I assume we're not talking something trivial like...
sorted = sort [1..]
where sort = id
| [reply]
[d/l] |
Well, you can't sort infinite streams.
Yeah, but streams need not be infinite. (At least according to HOP, which is what chb referred to. See HOP, pp. 257-259.) Streams only need to be lazy; in fact, the first example of a stream that Dominus gives (upto, p. 259) is a finite one. Since the stream in question would consist of the lines of a file at a given point in time, it goes without saying that such stream would necessarily be finite.
| [reply] |
