Welcome, guest | Sign In | My Account | Store | Cart

A simple function for efficiently iterating over ranges in reverse.

This is equivalent to reversed(range(...)) but somewhat more efficient.

Python, 41 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
if sys.version_info >= (3,):
    xrange = range

def rev_range(*args):
    """Create a reversed range.

    Equivalent to reversed(list(range(*args))), but without the intermediate
    list.

    This does some simple math on the arguments instead of creating an
    intermediate list and reversing it, thus automating a simple but
    error-prone optimization.
    """
    # Before Python 3.0, range creates a list while xrange is an efficient
    # iterator. From 3.0 onwards, range does what xrange did earlier (and
    # xrange is gone).
    if len(args) == 1:
        # start = 0, stop = args[0], step = 1
        return xrange(args[0]-1, -1, -1)

    # Unpack arguments, setting 'step' to 1 if it is not given.
    start, stop, step = (args + (1,))[:3]

    # The new 'stop' is the first item of the original range plus/minus one,
    # depending on the step's sign. Specifically:
    #   new_stop = start - (1 if step > 0 else -1)
    #
    # The new 'start' is the last item of the original range, which is
    # between one and 'step' less than the original 'stop'. Specifically:
    #
    # * If 'stop' minus 'start' divides by 'step' then the last item of the
    #   original range is 'stop' minus 'step'.
    # * If 'stop' minus 'start' doesn't divide by 'step', then the last item of
    #   the original range is 'stop' minus the remainder of this division.
    #
    # A single expression which accounts for both cases is:
    #   new_start = stop - ((stop-start-1) % step + 1)
    return xrange(stop - ((stop-start-1) % step + 1),
                  start - (1 if step > 0 else -1),
                  -step)

The goal of this recipe is to help avoid common programming errors, such as:

  • writing reversed(range(10)) as range(10, 0, -1) instead of range(9, -1, -1)
  • writing reversed(range(0, 10, 3)) as range(10 - 3, -3, -3) instead of range(9, -3, -3) or range(9, -1, -3).

I find that for the examples above, reversed(range(...)) is infinitely more readable. However, it incurs a performance hit due to the creation of an intermediate list and reversing it, which programmers sometimes decide to avoid.

This simple function allows easily achieving such common optimizations without degrading code readability. In my eyes rev_range(...) is also clearer than reversed(range(...)), once you're acquainted with the function.

2 comments

bazooka 14 years, 10 months ago  # | flag

maybe instead of

import sys
if sys.version < "3":
    range = xrange

use

try:
    range = xrange
except NameError:
    pass
Tal Einat (author) 10 years, 1 month ago  # | flag

Changed to just use xrange = range on Python 3.x.

Created by Tal Einat on Tue, 9 Jun 2009 (MIT)
Python recipes (4591)
Tal Einat's recipes (2)

Required Modules

Other Information and Tasks