[Python-3000] range() issues

[Richard Boulton]

Martin v. Löwis wrote:
>> These numbers aren't ridiculously large.  I just tried
>>
>> for i in range(2**31): pass
>>
>> on my (32-bit) laptop: it took 736.8 seconds, or about 12 and a bit minutes.
>> (An aside: in contrast,
>>
>> for i in range(2**31-1): pass
>>
>> took only 131.1 seconds;  looks like there's some potential for optimization
>> here....)

There's always potential for optimization ... just a question of whether
it's worth the increased coding (and maintenance) effort.

> No, it means the optimization has already been implemented:
> 
> py> iter(range(2**31-1))
> <range_iterator object at 0xb7a9b9f8>
> py> iter(range(2**31))
> <longrange_iterator object at 0xb7a9b968>
> 
> IOW, you can iterate over very long ranges, but doing so will be much
> slower (per element) than iterating over a short range.

In the slow example given, only one of the returned items needs to be a
long, so a possible further optimisation which would work well for this
case would be to automatically split the range into two parts - the part
which only needs short integers, and the part which needs longs, and
have a "mixedrange_iterator" type which returned all the items from one
of these, followed by all the items from the other.  In the general
case, there might need to be three such sub-iterators used:
range(-2**32, 2**32), for example, would be decomposed into
range(-2**32, -2**31-1) + range(-2**31, 2**31-1) + range(2**31, 2**32)

Not saying it's worth doing this optimisation, particularly, but I'm
going to guess that these are the lines the grandparent poster was
thinking along.

-- 
Richard