On PEP 322 (ireverse)

[Raymond Hettinger]

Re: On PEP 322 (ireverse)

[Jeremy Fincher]
[color=blue]
> Why not a more
> comprehensive PEP defining a reverse iteration protocol similar the
> protocol we have now for forward iteration?[/color]

It's in there under the Custom Reverse section. The approach is so
simple it doesn't take much elaboration: Objects may define a
__ireverse__ method that returns a reverse iterator -- this allows
objects without __getitem__ and __len__ to participate in
reverse iteration.


Raymond Hettinger

[Alex Martelli]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Bengt Richter wrote:
...[color=blue][color=green]
>>Perfectly right. If you DO want a listoid container that keeps its
>>elements sorted, that's not hard to make for yourself. There are[/color][/color]
...[color=blue]
> No comments on the heapq module?[/color]

It can often offer a good _alternative_ to "a listoid container that keeps
its elements sorted" -- keeping them as a heap is cheaper than keeping them
sorted. But "if you DO want" them sorted, so that at any time accessing
mycontainer[x] gives me the x-th smallest item in mycontainer, heapq isn't
gonna be very effective.

There are many good alternatives to "keeping the elements sorted", and
heapq may well help implement some of them, but I wasn't discussing the
alternatives -- just the implementation strategies under the assumption
that the specs DO call for "always sorted".


Alex

[Anton Vredegoor]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Alex Martelli <aleax@aleax.it > wrote:
[color=blue]
>class alwayssortedlis t(list):
>
> def __init__(self, *args):
> list.__init__(s elf, *args)
> self.sort()
>
>We need to ensure sorting at creation. We _might_ make the sort
>method in this class a noop and call list.sort(self) instead,
>but, naah -- list.sort is SO fast when called on an already
>sorted list that it ain't even funny, so, choose simplicity.
>Onwards to simple mods:
>
> def append(self, *args):
> list.append(sel f, *args)
> self.sort()
>
> def __setitem__(sel f, *args):
> list.__setitem_ _(self, *args)
> self.sort()[/color]

How about this code:

a = alwaysssortedli st(range(10))
a[5] = 20

What's the use of assigning to a specific list position if the object
could end up being in some other place?

Anton

[Alex Martelli]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Anton Vredegoor wrote:
...[color=blue]
> How about this code:
>
> a = alwaysssortedli st(range(10))
> a[5] = 20
>
> What's the use of assigning to a specific list position if the object
> could end up being in some other place?[/color]

For an always-sorted list, this clearly means: replace the currently
sixth-lowest item with the value 20. More generally, a[i] always
means "the (i+1)-th lowest item" -- referencing it no doubt going
to be useful much more often than replacing it, and value of i
different from the extremes (say 0, 1, -1) are going to be rare.
But, so what? One can surely imagine use cases (if one can for any
use of an "always-sorted list" rather than sorting on request).

For example: "if there is any occurrence of 20 in the list, then
replace the immediately-smaller item (if any, i.e., unless 20 is
the smallest) with another copy of the value 20". I.e.:

try: i = a.index(20)
except ValueError:
print "value 20 is not in the list"
else:
if i==0:
print "value 20 is in the list, but it's the smallest"
else:
a[i-1] = 20

I don't think I've ever needed to code this kind of thing in
production-code, but it doesn't seem particularly far-fetched
to me. Why else, except for such kinds of uses, would one want
a listoid that's _always_ sorted, rather than a cheaper heap
(see module heapq) or a list that's sorted on request...?


Alex

[Michael Hudson]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Alex Martelli <aleax@aleax.it > writes:
[color=blue]
> For an always-sorted list, this clearly means: replace the currently
> sixth-lowest item with the value 20. More generally, a[i] always
> means "the (i+1)-th lowest item" -- referencing it no doubt going
> to be useful much more often than replacing it, and value of i
> different from the extremes (say 0, 1, -1) are going to be rare.
> But, so what?[/color]

Oh, yow. Typing

a[5] = 20

and then having

a[5] != 20

is just icky. Find another notation.

Cheers,
mwh

--
The only problem with Microsoft is they just have no taste.
-- Steve Jobs, (From _Triumph of the Nerds_ PBS special)
and quoted by Aahz on comp.lang.pytho n

[David Mertz]

Re: On PEP 322 (ireverse)

|> I'm +1 on iter.reversed, along with list.sorted.

"Raymond Hettinger" <vze4rx4y@veriz on.net> wrote previously:
|list.sorted() is entirely unrelated. It is attached to lists because that
|is what it generally returns and because its functionality is closely
|tied to list.sort().

Regardless of the connection to list.sorted(), I'm -1 on a built-in
'reversed()' (or whatever name).

But I'd be +1 on a function or method that lived in either the itertools
modules, or as a member of a classified iter().

There's been WAY too much pollution of the builtin namespace lately.
'reversed()' is nice enough to have not too far away, but not nearly
common enough to need as a builtin.

In fact, I find at least the following anathema in the same way:
enumerate(), sum(), zip(), xrange(). I'm probably forgetting some more.
I'd love to have these in itertools (or maybe sum() could be in math).
But teaching extra builtins is a pain... as is explaining arbitrary
distinctions between what's builtin and what's in itertools. I think if
I had my druthers, I might even put iter() in itertools.

|Grafting this onto iter is not an option; I would rather lose the
|functionality than have the experts here twist it into something
|I can't easily explain to a client.

Hmmm... that's EXACTLY the reason that I DON'T want it as a builtin.

Yours, Lulu...

--
mertz@ | The specter of free information is haunting the `Net! All the
gnosis | powers of IP- and crypto-tyranny have entered into an unholy
..cx | alliance...idea s have nothing to lose but their chains. Unite
| against "intellectu al property" and anti-privacy regimes!
-------------------------------------------------------------------------

[Jeremy Fincher]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Alex Martelli <aleax@aleax.it > wrote in message news:<HaVnb.652 20$e5.2392011@n ews1.tin.it>...[color=blue]
> Perfectly right. If you DO want a listoid container that keeps its
> elements sorted, that's not hard to make for yourself. There are
> basically two obvious implementation strategies:
> -- ensure the underlying list is re-sorted at each insertion,
> append &c, and/or
> -- let the underlying list grow as it will on insertion &c, but
> make sure it's sorted at any method that accesses it (you can
> use a flag -- 'have there being any append/insert/... since
> the last sort?' -- to re-sort only when needed).
>
> I'll choose the first for general use because:
> -- accesses are much more frequent than modifications,
> -- list.sort is VERY fast when a list is "nearly sorted"
> -- the second approach would require sorting also on many
> kind of changes (e.g. __setitem__ -- to ensure the items
> being replaced ARE those the user expects...)
> &c.[/color]

Any reason he shouldn't just use bisect.insort?

Jeremy

[Alex Martelli]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Jeremy Fincher wrote:
[color=blue]
> Alex Martelli <aleax@aleax.it > wrote in message
> news:<HaVnb.652 20$e5.2392011@n ews1.tin.it>...[color=green]
>> Perfectly right. If you DO want a listoid container that keeps its
>> elements sorted, that's not hard to make for yourself. There are
>> basically two obvious implementation strategies:
>> -- ensure the underlying list is re-sorted at each insertion,
>> append &c, and/or[/color][/color]
...[color=blue]
> Any reason he shouldn't just use bisect.insort?[/color]

What about measuring the performance of the two approaches?

I've shown how incredibly simple the sort-after-whatever-addition-
or-replacement approach is -- the insort one will require some more
coding, but IF it's a lot faster, sure. But don't discount timsort's
performance -- it's often incredibly good.


Alex

[Ian McMeans]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Not only is it not effective, but heaps don't keep their elements in
sorted order... so if you wanted a list to stay sorted, heaps aren't
what you want. They're great for finding the smallest element
repeatedly, but not for i'th order statistics in general.
[color=blue][color=green][color=darkred]
>>> import heapq
>>> h = [1,3,2,4]
>>> heapq.heapify(h )
>>> h[/color][/color][/color]
[1, 3, 2, 4][color=blue][color=green][color=darkred]
>>> h = [4,3,1,2]
>>> heapq.heapify(h )
>>> h[/color][/color][/color]
[1, 2, 4, 3][color=blue][color=green][color=darkred]
>>> h.sort()
>>> h[/color][/color][/color]
[1, 2, 3, 4]


Alex Martelli <aleax@aleax.it > wrote in message news:<ff6ob.379 033$R32.1256681 8@news2.tin.it> ...[color=blue]
> Bengt Richter wrote:
> ...[color=green][color=darkred]
> >>Perfectly right. If you DO want a listoid container that keeps its
> >>elements sorted, that's not hard to make for yourself. There are[/color][/color]
> ...[color=green]
> > No comments on the heapq module?[/color]
>
> It can often offer a good _alternative_ to "a listoid container that keeps
> its elements sorted" -- keeping them as a heap is cheaper than keeping them
> sorted. But "if you DO want" them sorted, so that at any time accessing
> mycontainer[x] gives me the x-th smallest item in mycontainer, heapq isn't
> gonna be very effective.
>
> There are many good alternatives to "keeping the elements sorted", and
> heapq may well help implement some of them, but I wasn't discussing the
> alternatives -- just the implementation strategies under the assumption
> that the specs DO call for "always sorted".
>
>
> Alex[/color]

[Alex Martelli]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Ian McMeans wrote:
[color=blue]
> Not only is it not effective, but heaps don't keep their elements in
> sorted order... so if you wanted a list to stay sorted, heaps aren't[/color]

Please don't "top-post": somebody reading your reply can't see what
you ARE responding to. Putting your comments AFTER the phrase you're
commenting on is much kinder to readers.

I said a heap is "not effective" (as a way to sort, in Python) because
the sort method of lists is so much faster. You CAN use a heap to
sort, it's just not an _effective_ way to perform sorting in Python.


Alex

[Jeremy Fincher]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Alex Martelli <aleaxit@yahoo. com> wrote in message news:<bXdob.704 43$e5.2563561@n ews1.tin.it>...[color=blue]
> Jeremy Fincher wrote:[color=green]
> > Any reason he shouldn't just use bisect.insort?[/color]
>
> What about measuring the performance of the two approaches?[/color]

I'll do that when I get back to my own computer. It's interesting, of
course, because although the point of bisect.insort is to use O(log n)
binary search to find the place to insert an element, it's still O(n)
because list.insert is O(n). So if timsort is close to O(n) for
nearly-sorted lists, I wonder if it would actually be faster than
bisect.insort because it's coded in C.
[color=blue]
> I've shown how incredibly simple the sort-after-whatever-addition-
> or-replacement approach is -- the insort one will require some more
> coding, but IF it's a lot faster, sure. But don't discount timsort's
> performance -- it's often incredibly good.[/color]

If timsort is actually faster than bisect.insort in all cases, perhaps
it's time for bisect.insort to be deprecated? It's what I would
naturally use for this case because "that's what it's made for," and
it'd be unfortunate to point Python programmers to the *less*
efficient way to do something.

Jeremy

[Alex Martelli]

Re: alwayssortedlis t (was Re: On PEP 322 (ireverse))

Jeremy Fincher wrote:
...[color=blue][color=green]
>> I've shown how incredibly simple the sort-after-whatever-addition-
>> or-replacement approach is -- the insort one will require some more
>> coding, but IF it's a lot faster, sure. But don't discount timsort's
>> performance -- it's often incredibly good.[/color]
>
> If timsort is actually faster than bisect.insort in all cases, perhaps
> it's time for bisect.insort to be deprecated? It's what I would
> naturally use for this case because "that's what it's made for," and
> it'd be unfortunate to point Python programmers to the *less*
> efficient way to do something.[/color]

operations that modify data are a tad harder to time with timeit.py,
but not impossible with some precautions...:

[alex@lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(99,0 ,3)'
'L=LL[:]'

[alex@lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(99,0 ,3)'
'L=LL[:]; L.append(33); L.sort()'
100000 loops, best of 3: 2.3 usec per loop

alex@lancelot bo]$ timeit.py -c -s'import bisect' -s'LL=range(99,0 ,3)'
'L=LL[:]; bisect.insort(L , 33)'
100000 loops, best of 3: 4.4 usec per loop

....so, yes -- insort can't hold a candle to a list's sort method when
what you're asking them is to do the very same job. Of course,
bisect.insort_r ight, aka insort, has different specs -- e.g., if you
DO need to supply its lo and hi parameters, then you're considering
a very different problem from what the sort method is solving.

But yes, bisect is basically an EXAMPLE -- a working example of the
peculiarly-hard-to-code-RIGHT bisection algorithm; maybe we should
mention that in the docs. Lemme see if I can borrow the time machine
for the purpose... done. Now, the docs do clearly say:

"""
The source code may be most useful as a working example of the algorithm
"""

Better, hm?-)


Alex

[Aahz]

Re: On PEP 322 (ireverse)

In article <JfSnb.40886$1C 5.21668@nwrdny0 2.gnilink.net>,
Raymond Hettinger <python@rcn.com > wrote:[color=blue]
>
>No thanks. Yuck. Please do not twist this simple idea into knots.
>This is supposed to be something you can teach in the first half-hour
>and then use forever. I would sooner teach negative xrange()
>indices than immediately launch into dotted references to a static
>method attached to something that doesn't look like it should have
>a method. This is a simplification, not an exercise in being cute
>or clever just to avoid a builtin.[/color]

Counter-yuck. ;-) I just can't see reverse() by any name being one of
the first things taught about Python.
--
Aahz (aahz@pythoncra ft.com) <*> http://www.pythoncraft.com/

"It is easier to optimize correct code than to correct optimized code."
--Bill Harlan

[Aahz]

Re: On PEP 322 (ireverse)

In article <4xQnb.373812$R 32.12367046@new s2.tin.it>,
Alex Martelli <aleax@aleax.it > wrote:[color=blue]
>
>I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
>way to have builtin function iter grow a 'staticmethod' of sorts...![/color]

Raymond has vetoed this, but I don't understand why iter() needs to grow
a staticmethod. After all, it's just a function that can be decorated
with attributes....
--
Aahz (aahz@pythoncra ft.com) <*> http://www.pythoncraft.com/

"It is easier to optimize correct code than to correct optimized code."
--Bill Harlan

[Alex Martelli]

Re: On PEP 322 (ireverse)

Aahz wrote:
[color=blue]
> In article <4xQnb.373812$R 32.12367046@new s2.tin.it>,
> Alex Martelli <aleax@aleax.it > wrote:[color=green]
>>
>>I still prefer Werner Schiendl's idea of iter.reversed, IF we find a
>>way to have builtin function iter grow a 'staticmethod' of sorts...![/color]
>
> Raymond has vetoed this, but I don't understand why iter() needs to grow
> a staticmethod. After all, it's just a function that can be decorated
> with attributes....[/color]

built-in functions normally can't, and in that way they differ from
C-coded functions. So, iter would have to be changed into a different
type that _does_ support some attributes.


Alex