Slices time complexity

[Chris Angelico]

On Tue, May 19, 2015 at 5:49 AM, Mario Figueiredo <marfig at gmail.com> wrote:
> On Tue, 19 May 2015 05:36:44 +1000, Chris Angelico <rosuav at gmail.com>
> wrote:
>
>>What's the point of optimizing slicing to allow you to use a poor
>>algorithm, instead of fixing your algorithm?
>>
>
> Chris, thank you for your input. But the code isn't really the
> question, is it?
>
> It's just an example. It was being used earlier to demonstrate Time
> Complexity calculations in another forum. It's not real live code.
> Never will be. Besides we already have a min() function in Python.

General rule of optimization: Do the simplest thing first, and make it
more complicated only if the speed benefit is worth it. In this case,
slicing a list is done in the obvious and simple way: construct a new
list of the appropriate length, and assign all its elements. (The
details may be optimized some at the C level, but it still constructs
a new list.) You're asking why Python doesn't have a much more
complicated system (Todd suggests views and COW; another way is to do
a LISP-style linked list, which has similar consequences to views, but
is more efficient if you do this specific thing of processing the
first element and recursing for the rest), and the answer is: There's
always a better way to write your algorithm.

So if your code is intended to demonstrate how a poor algorithm can
turn a linear task into a quadratic one, congrats! You've succeeded.
If you're trying to showcase how terrible Python is, well, I'm sure
you could do that in more effective ways, but they'll still come down
to trying to write <insert other language name here> code using the
Python interpreter. If you write idiomatic Python code, using
iterators and loops rather than recursion, you'll find your code is
cleaner and faster than it would be if you fight against the language.

ChrisA