Q: listsort and dictsort - official equivalents?

[Steve Howell]

--- BJörn Lindqvist <bjourne at gmail.com> wrote:

> On 6/20/07, Gabriel Genellina
> <gagsl-py2 at yahoo.com.ar> wrote:
> > > It's not true that the sort must complete (or
> that the whole file must
> > > be read for that matter), Python has cool
> generators which makes the
> > > above possible.
> >
> > That's not possible, the input must be read
> completely before sorted() can
> > output anything. Suppose the minimum element is at
> the end - until you
> > read it, you can't output the very first sorted
> element.
> 
> Doh! Yes of course. I always thought that sorted()
> returned a
> generator. Since Python's sort is based on merge
> sort, using a
> generator approach it should at least be
> theoretically possible to
> begin emitting the items before the sort operation
> completes.
> 

I think Gabriel was making the point that the *input*
to sorted() cannot be a generator, even thought
sorted() itself could in theory be a generator with
the right underlying implementation (e.g. heapsort).  

It's not unrealistic at all to have an indeterminate
sequence of events that you occasionally want to pop
results off of in sorted order, with the obvious
limitation that you haven't yet seen "future" inputs
from the input iteration.  The way to express that is
by using some kind of heap, though.  I don't really
see how you'd use the heap as a generator in that
case, though.




       
____________________________________________________________________________________
Building a website is a piece of cake. Yahoo! Small Business gives you all the tools to get online.
http://smallbusiness.yahoo.com/webhosting