ActiveState Code

Recipe 576801: Reversed Ranges

A simple function for efficiently iterating over ranges in reverse.

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

Python 
 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
def rev_range(*args):
    """Create a reversed range.

    Equivalent to reversed(list(range(*args))), but more efficient.

    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 often done by programmers.
    """
    # 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).
    import sys
    if sys.version < "3":
        range = xrange

    if len(args) == 1:
        # start = 0, stop = args[0], step = 1
        return range(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 range(stop - ((stop-start-1) % step + 1),
                 start - (1 if step > 0 else -1),
                 -step)

Discussion

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.

Comments

  1. 1. At 10:53 p.m. on 16 jun 2009, bazooka said:

    maybe instead of

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

    use 

    try:
    range = xrange
except NameError:
    pass

Sign in to comment