[Tutor] Finding more efficient ways

[Oscar Benjamin]

On 9 July 2013 21:04, HRK <rahn.no.kamikakushi at gmail.com> wrote:
>
> PROBLEM #2
>
> def is_up_down(values):
>     '''Return True if values is an up-down-sequence, otherwise
>     return False.
>     A sequence [x[0], x[1], x[2], ..., x[n]] is an up-down-sequence
>     if there is an index k such that
>     x[0] <= x[1] <= x[2] <= ... <= x[k-1] <= x[k] and
>     x[k] >= x[k+1] >= x[k+2] >= ... >= x[n-1] >= x[n] hold.
>     That is, the first part of the sequence is increasing and the
>     second part is decreasing.
>     Either part may be empty, so any increasing sequence and any
>     decreasing sequence is an up-down-sequence.
>     '''
>     flip = 0
>     value = 0

The line above assumes non-negative inputs. You could use
float('-inf') here assuming that this only needs to work for numbers.

>     for item in values:
>         if flip == 2:
>             if item > value:
>                 return False
>         elif flip == 1:
>             if item < value:
>                 flip += 1
>             value = item
>         elif flip == 0:
>             if item > value:
>                 flip += 1
>             value = item

It would be cleaner to just have a single 'value = item' line at the
end of the loop:

     for item in values:
         if flip == 2:
             if item > value:
                 return False
         elif flip == 1:
             if item < value:
                 flip += 1
         elif flip == 0:
             if item > value:
                 flip += 1
         value = item

Some would consider this an abuse of Python's bool type but I might
write that as:

     for item in values:
         if flip == 2:
             if item > value:
                 return False
         elif flip == 1:
             flip += item < value
         elif flip == 0:
             flip += item > value:
         value = item

Perhaps I'd even do:

     for item in values:
         if flip == 2:
             if item > value:
                 return False
         else:
             flip += item < value if flip else item > value
         value = item

If you use the pairwise recipe from itertools:

    from itertools import tee

    def pairwise(iterable):
        "s -> (s0,s1), (s1,s2), (s2, s3), ..."
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)  # Assumes Python 3

Then you can just do:

    pairs = pairwise(values)
    for item1, item2 in pairs:
        if item2 < item1:
            break
    for item1, item2 in pairs:  # Assumes Python 3
        if item2 > item1:
            return False
    return True

or perhaps

    pairs = pairwise(values)
    direction = 1
    for item1, item2 in pairs:
        if (item2 - item1) * direction < 0:
            if direction == 1:
                direction == -1
            else:
                return False
    return True

but this last version assumes that the items are subtractable (rather
than simply orderable).

You may prefer any of these to your original but I wouldn't say that
any of them is substantially better. I think your first approach was
pretty good (apart from not handling negative inputs).

To modify the original so that it works for any orderable types you can do

def is_up_down(values):
    '''Return True if values is an up-down-sequence, otherwise
    return False.
    A sequence [x[0], x[1], x[2], ..., x[n]] is an up-down-sequence
    if there is an index k such that
    x[0] <= x[1] <= x[2] <= ... <= x[k-1] <= x[k] and
    x[k] >= x[k+1] >= x[k+2] >= ... >= x[n-1] >= x[n] hold.
    That is, the first part of the sequence is increasing and the
    second part is decreasing.
    Either part may be empty, so any increasing sequence and any
    decreasing sequence is an up-down-sequence.


    >>> is_up_down([2,5,5,7,9,9,8])
    True
    >>> is_up_down([2,5,5,7,9,8,9])
    False
    >>> is_up_down([9,8])
    True
    >>> is_up_down([13])
    True
    '''
    flip = 0
    lastitem = sentinel = object()
    for item in values:
        if lastitem is not sentinel:
            if flip == 0:
                if item > lastitem:
                    flip += 1
            elif flip == 1:
                if item < lastitem:
                    flip += 1
            elif flip == 2:
                if item > lastitem:
                    return False
        lastitem = item
    return True

import doctest; doctest.testmod()


I find it easier to read if the order is the other way up so that flip
== 0 is at the top. Also note that by moving your examples into the
docstring you now have automatic testing.


Oscar