Well, you can't sort infinite streams. I haven't read HOP, but usually streams and iterators are the same thing. Lazy lists, on the other hand, are nothing but memoized iterators. You can sort iterators without storing the entire thing in memory, but it requires multiple passes through contents of the iterator (N passes for the bubble sort, although you can trade this off for increased memory usage. That is you can do it in N/2 passes, if your bubble sort floats two items to the top at a time). | [reply] |
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] |
