efficiency of range() and xrange() in for loops

[Alan Morgan]

Re: efficiency of range() and xrange() in for loops

In article <F4KdnXuGqOst1K nZnZ2dnUVZ_vudn Z2d@speakeasy.n et>,
Erik Max Francis <max@alcyone.co m> wrote:[color=blue]
>Alan Morgan wrote:
>[color=green]
>> In article <teXYf.69673$A8 3.1673324@twist er1.libero.it>,
>> Giovanni Bajo <noway@sorry.co m> wrote:
> >[color=darkred]
>>>Because you assume that the only use-case of range() is within a for-loop.
>>>range() is a builtin function that can be used in any Python expression. For
>>>instance:
>>>
>>>RED, GREEN, BLUE, WHITE, BLACK = range(5)[/color]
>>
>> Hmmm, this worked fine when I used xrange as well. Am I missing something?[/color]
>
>Not in your use case. Tuple unpacking will iterate, and so it doesn't
>matter whether it's an actual list or an iterator:
>[color=green][color=darkred]
> >>> a, b, c = xrange(3)
> >>> a[/color][/color]
>0[color=green][color=darkred]
> >>> b[/color][/color]
>1[color=green][color=darkred]
> >>> c[/color][/color]
>2
>
>There are certainly contexts where a sequence and its iterator are not
>interchangeabl e. You missed an obvious one:
>[color=green][color=darkred]
> >>> range(3) == xrange(3)[/color][/color]
>False[/color]

I thought that one was sufficiently obvious as not to need mentioning.
There was never any argument that range() and xrange() returned different
things; the question (as I understood it) was if you could generally
use the things they return in the same way and not *care* about the
difference (the answer being "Yes, except when you can't").

Alan
--
Defendit numerus

[Azolex]

Re: efficiency of range() and xrange() in for loops

Steve R. Hastings wrote:[color=blue]
> On Thu, 06 Apr 2006 09:08:45 +1000, Steven D'Aprano wrote:[color=green]
>> Yes, the above example is a good use case for xrange. Did you think that
>> anyone denied that there were good cases for it?[/color]
>
> I am now officially sorry for starting this thread.[/color]

Don't. It's quite funny, thanks.

[Steve R. Hastings]

Re: efficiency of range() and xrange() in for loops

On Thu, 06 Apr 2006 02:33:16 +0200, Azolex wrote:[color=blue]
> Don't. It's quite funny, thanks.[/color]

I guess I should laugh. :-/


When you read my original articles, did *you* think I was proposing that
range() be changed to always return an iterator? I thought what I wrote
was pretty clear...
--
Steve R. Hastings "Vita est"
steve@hastings. org http://www.blarg.net/~steveha

[Felipe Almeida Lessa]

Re: efficiency of range() and xrange() in for loops

Em Qua, 2006-04-05 às 22:24 +0200, Fredrik Lundh escreveu:[color=blue]
> the difference isn't very
> large, xrange is actually slower in some python versions, and you'll
> need the integer objects sooner or later anyway...[/color]

Some code is worth a thousand words:


$ python2.3
Python 2.3.5 (#2, Mar 6 2006, 10:12:24)
[GCC 4.0.3 20060304 (prerelease) (Debian 4.0.2-10)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.[color=blue][color=green][color=darkred]
>>> from timeit import Timer
>>> min(Timer('for i in range(1): pass').repeat(3 , 100000))/100[/color][/color][/color]
0.0009930396080 0170891[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(1): pass').repeat(3 , 100000))/100[/color][/color][/color]
0.0007741713523 8647464[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(10): pass').repeat(3 , 1000))[/color][/color][/color]
0.0016450881958 007812[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(10): pass').repeat(3 , 1000))[/color][/color][/color]
0.0013418197631 835938[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(100): pass').repeat(3 , 1000))[/color][/color][/color]
0.0101709365844 72656[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(100): pass').repeat(3 , 1000))[/color][/color][/color]
0.0073339939117 431641[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(1000): pass').repeat(3 , 1000))[/color][/color][/color]
0.0833377838134 76562[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(1000): pass').repeat(3 , 1000))[/color][/color][/color]
0.0704607963562 01172[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(10000): pass').repeat(3 , 1000))[/color][/color][/color]
0.8802762031555 1758[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(10000): pass').repeat(3 , 1000))[/color][/color][/color]
0.7105021476745 6055[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(100000): pass').repeat(3 , 1000))[/color][/color][/color]
13.938336849212 646[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(100000): pass').repeat(3 , 1000))[/color][/color][/color]
7.0900959968566 895[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(1000000): pass').repeat(3 , 100))*10[/color][/color][/color]
141.37096881866 455[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(1000000) : pass').repeat(3 , 100))*10[/color][/color][/color]
70.822579860687 256


$ python2.4
Python 2.4.3 (#2, Mar 30 2006, 21:52:26)
[GCC 4.0.3 (Debian 4.0.3-1)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.[color=blue][color=green][color=darkred]
>>> from timeit import Timer
>>> min(Timer('for i in range(1): pass').repeat(3 , 100000))/100[/color][/color][/color]
0.0008401203155 5175776[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(1): pass').repeat(3 , 100000))/100[/color][/color][/color]
0.0006901383399 9633791[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(10): pass').repeat(3 , 1000))[/color][/color][/color]
0.0014748573303 222656[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(10): pass').repeat(3 , 1000))[/color][/color][/color]
0.0014920234680 175781[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(10): pass').repeat(3 , 1000))[/color][/color][/color]
0.0012860298156 738281[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(100): pass').repeat(3 , 1000))[/color][/color][/color]
0.0079219341278 076172[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(100): pass').repeat(3 , 1000))[/color][/color][/color]
0.0069670677185 058594[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(1000): pass').repeat(3 , 1000))[/color][/color][/color]
0.0792250633239 74609[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(1000): pass').repeat(3 , 1000))[/color][/color][/color]
0.0677070617675 78125[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(10000): pass').repeat(3 , 1000))[/color][/color][/color]
0.8491289615631 1035[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(10000): pass').repeat(3 , 1000))[/color][/color][/color]
0.6791541576385 498[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(100000): pass').repeat(3 , 1000))[/color][/color][/color]
13.973598003387 451[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(100000): pass').repeat(3 , 1000))[/color][/color][/color]
6.8047640323638 916[color=blue][color=green][color=darkred]
>>> min(Timer('for i in range(1000000): pass').repeat(3 , 100))*10[/color][/color][/color]
138.38916063308 716[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(1000000) : pass').repeat(3 , 100))*10[/color][/color][/color]
68.152160644531 25


In sum, difference is as big as the function argument, but xrange was
*never* slower on Python 2.3 or Python 2.4 on x86 with Linux. I'd say
three things:

1) Probably xrange is faster than range on other architectures and
operational systems as well.
2) I can't say anything for Python < 2.3.
3) Run your own tests. If you see the same I saw, use xrange everywhere
you can.

The 3rd point is specially true if your code can be break in the middle,
for example (a really dumb example, I know):

for i in xrange(0, 10000000, 42):
if i**2 >= x:
break

This way you won't create all numbers, in this case just those less than
sqrt(x) plus one.

Cheers,

--
Felipe.

[Alex Martelli]

Re: efficiency of range() and xrange() in for loops

Steve R. Hastings <steve@hastings .org> wrote:
...[color=blue]
> Actually, for many uses of "for i in (range|xrange)" , you only need the
> value of i, and you aren't doing anything with the integer object. You[/color]

Then, the speediest approach may be completely different:

import itertools

for i in itertools.repea t(None, N):
...


Remember, when you're thinking "blazing speed", think itertools.


Alex

[Felipe Almeida Lessa]

Re: efficiency of range() and xrange() in for loops

Em Qua, 2006-04-05 às 19:15 -0700, Alex Martelli escreveu:[color=blue]
> Steve R. Hastings <steve@hastings .org> wrote:
> ...[color=green]
> > Actually, for many uses of "for i in (range|xrange)" , you only need the
> > value of i, and you aren't doing anything with the integer object. You[/color]
>
> Then, the speediest approach may be completely different:
>
> import itertools
>
> for i in itertools.repea t(None, N):
> ...
>
>
> Remember, when you're thinking "blazing speed", think itertools.[/color]

Hmmm...
[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(100000): pass').repeat(3 , 1000))[/color][/color][/color]
6.7740321159362 793[color=blue][color=green][color=darkred]
>>> min(Timer('for i in itertools.repea t(None, 100000): pass',[/color][/color][/color]
setup='import itertools').rep eat(3, 1000))
5.6378099918365 479
[color=blue][color=green][color=darkred]
>>> min(Timer('for i in xrange(100): pass').repeat(3 , 1000))[/color][/color][/color]
0.0071630477905 273438[color=blue][color=green][color=darkred]
>>> min(Timer('for i in itertools.repea t(None, 100): pass',[/color][/color][/color]
setup='import itertools').rep eat(3, 1000))
0.0065851211547 851562

It *is* faster, but by a small margin. Considering that it is IMHO less
readable, I'd use it just for *very* big loops, or in functions in
hotspots.

Anyway, it's always good to remember about itertools, it's a great
module that some people don't even know.

Cheers,

--
Felipe.

[Azolex]

Re: efficiency of range() and xrange() in for loops

Steve R. Hastings wrote:[color=blue]
> On Thu, 06 Apr 2006 02:33:16 +0200, Azolex wrote:[color=green]
>> Don't. It's quite funny, thanks.[/color]
>
> I guess I should laugh. :-/
>
>
> When you read my original articles, did *you* think I was proposing that
> range() be changed to always return an iterator? I thought what I wrote
> was pretty clear...[/color]

I just re-read your original post, and in fact this appears to have been
your drift with "is there any chance this optimization could be added
?". Anyway that wasn't really controversial (since indeed, as was noted
by John Salerno who first replied to you, it is slated for py3k - and
with good reason).

[Carl Banks]

Re: efficiency of range() and xrange() in for loops

Steve R. Hastings wrote:[color=blue]
> I wondered if the Python
> compiler could, as a special case, turn:
>
> for i in range(n)
>
> into compiled code equivalent to
>
> for i in itr
>
> where "itr" is a lightweight iterator that returns the same values as
> iter(range(n)).[/color]

Nope, out of the question for Python 2.x. Note that the the builtin
range could be rebound, or a global range could appear in the module,
at run time. There might even be a good reason to do so.... Point is,
optimizing the call to range can break compatibility even in the for
loop.


Carl Banks

[Fredrik Lundh]

Re: efficiency of range() and xrange() in for loops

Steve R. Hastings wrote:
[color=blue][color=green]
> > the difference isn't very
> > large, xrange is actually slower in some python versions, and you'll
> > need the integer objects sooner or later anyway...[/color]
>
> Actually, for many uses of "for i in (range|xrange)" , you only need the
> value of i, and you aren't doing anything with the integer object.[/color]

so you're saying that the value of i isn't an integer object?

if you don't need the index value at all, itertools.repea t is sometimes
faster than xrange.
[color=blue]
> for i in range(10**6):
> pass
>
> and produced code equivalent to this:
>
> for i in iter(range(10** 6))
> pass
>
> How would this break stuff?[/color]

how would that speed anything up?

</F>

[Georg Brandl]

Re: efficiency of range() and xrange() in for loops

Alan Morgan wrote:
[color=blue][color=green]
>>range is giving you a real list, while xrange is giving you an xrange object.
>>Have you tried to slice an xrange object? Or using .append on it?[/color]
>
> No, I hadn't. I presume these could all be defined.[/color]

How would xrange(100).rem ove(1) work?

Georg

[Paddy]

Re: efficiency of range() and xrange() in for loops

I wondered at the tone of some of the replies, re-read the repliess and
your original message. On first readings ithought that your original
message was OK and that the replies were a bit 'strong' . On second
reading I thought that the original could be interpreted a little less
nicely, but I had to go looking.

Please don't be put off using this news group. I guesss we all have to
be extra careful about tone when no one can see your facial expressions
:-)

- Pad.

P.S. I was having problems with the Google server - sorry if this is
replicated.

[Steve R. Hastings]

Re: efficiency of range() and xrange() in for loops

On Wed, 05 Apr 2006 22:08:29 -0700, Carl Banks wrote:[color=blue][color=green]
>> for i in range(n)
>>
>> into compiled code equivalent to
>>
>> for i in itr
>>
>> where "itr" is a lightweight iterator that returns the same values as
>> iter(range(n)).[/color][/color]
[color=blue]
> Nope, out of the question for Python 2.x. Note that the the builtin
> range could be rebound, or a global range could appear in the module,
> at run time.[/color]

Ah! Of course.

Thank you very much for explaining this.
--
Steve R. Hastings "Vita est"
steve@hastings. org http://www.blarg.net/~steveha

[Fredrik Lundh]

Re: efficiency of range() and xrange() in for loops

Carl Banks wrote:
[color=blue][color=green]
> > I wondered if the Python compiler could, as a special case, turn:
> >
> > for i in range(n)
> >
> > into compiled code equivalent to
> >
> > for i in itr
> >
> > where "itr" is a lightweight iterator that returns the same values as
> > iter(range(n)).[/color]
>
> Nope, out of the question for Python 2.x. Note that the the builtin
> range could be rebound, or a global range could appear in the module,
> at run time. There might even be a good reason to do so.... Point is,
> optimizing the call to range can break compatibility even in the for
> loop.[/color]

that could of course be addressed by turning for-in into a special method
on the range object... map

for variable in expression:
block

to

_value = expression
try:
_for = _value.__for__
except AttributeError:
_for = iter(_value).__ for__
_for(variable, block)

and tweak as necessary.

</F>

[Alan Morgan]

Re: efficiency of range() and xrange() in for loops

In article <e12b4s$vcd$1@n ews.albasani.ne t>,
Georg Brandl <g.brandl-nospam@gmx.net> wrote:[color=blue]
>Alan Morgan wrote:
>[color=green][color=darkred]
>>>range is giving you a real list, while xrange is giving you an xrange object.
>>>Have you tried to slice an xrange object? Or using .append on it?[/color]
>>
>> No, I hadn't. I presume these could all be defined.[/color]
>
>How would xrange(100).rem ove(1) work?[/color]

One way is by first converting the xrange to a list. If we think of
the xrange as an efficient and space lean way to store certain types
of lists then it isn't unreasonable to return a regular list when
the conditions no longer hold.

Or extend the xrange object to allow multiple ranges and return the
union of xrange(0,1) and xrange(2,100). No reason why you can't
define the whole range of list operations over xrange and still leave
it as a nice, lazy list (other languages do). It's possible that no
one needs it enough to make it worthwhile (although having full fledged
lazy structures can really helpful when you need them) but it could
be done.

Alan
--
Defendit numerus

[Fredrik Lundh]

Re: efficiency of range() and xrange() in for loops

Alan Morgan wrote:
[color=blue][color=green]
> >How would xrange(100).rem ove(1) work?[/color]
>
> One way is by first converting the xrange to a list. If we think of
> the xrange as an efficient and space lean way to store certain types
> of lists then it isn't unreasonable to return a regular list when
> the conditions no longer hold.[/color]

do you understand Python's object model to be able to suggest how such
a conversion could be done, or is that someone else's problem ?

</F>