Path: csiph.com!usenet.pasdenom.info!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
Date: Tue, 19 May 2015 05:36:44 +1000
Subject: Re: Slices time complexity
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.112.1431977807.17265.python-list@python.org>
Lines: 47
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:90808

On Tue, May 19, 2015 at 5:23 AM, Mario Figueiredo <marfig@gmail.com> wrote:
> From the above link it seems slices work in linear time on all cases.
> And this really has a big impact on certain operations. For instance,
> the code below may surprise some people when they realize it doesn't
> run in linear time on 3.4:
>
>     def minimum(values):
>         if len(values) == 1:
>             return values[0]
>         else:
>             m = minimum(values[1:])
>             return m if m < values[0] else values[0]

https://xkcd.com/1270/

Is there really a reason to code this in such a bizarrely inefficient
way? Linear or not, it's bound to be less efficient than the more
obvious form:

def minimum(values):
    values = iter(values)
    min = next(values)
    for value in values:
        if value < min: min = value
    return min

And if you know your value domain (maybe you're working with floats,
or positive integers, or something) and can put a hard-coded base
value in, it becomes even simpler:

def minimum(values):
    min = 0 # or float("-inf") etc
    for value in values:
        if value < min: min = value
    return min

It's obvious that this code will complete in linear time. It's also
pretty obvious how it's working: it steps through the collection,
comparing each value against the current smallest. With your recursive
version, it effectively steps backward through the list, comparing
each value against the current smallest, all while unwinding the
stack. It can't even be tail-call-optimized in its current state.

What's the point of optimizing slicing to allow you to use a poor
algorithm, instead of fixing your algorithm?

ChrisA