Drowning in a teacup?

[Chris Kaynor]

On Fri, Apr 1, 2016 at 1:52 PM, Ian Kelly <ian.g.kelly at gmail.com> wrote:

> On Fri, Apr 1, 2016 at 2:39 PM, Rob Gaddi
> <rgaddi at highlandtechnology.invalid> wrote:
> > Fillmore wrote:
> >> Nope, wrong! contrary to what I thought I had understood about how
> >> parameters are passed in Python, the function is acting on a copy(!) and
> >> my original list is unchanged.
> >>
> >
> > Nope, that's not your problem.  Your problem is the line:
> >
> >>              mylist = [mylist[i]] + mylist[:i] + mylist[i+1:]
> >
> > Which should be read as: "Take mylist[i], all of mylist before i,
> > and all of mylist after i and create a new list from it. Store that
> > new list in a variable called mylist, overwriting the previous value."
> >
> > If instead you were using the .insert and .remove methods, you'd be
> > manipulating the existing list instead.  But you don't want to do that,
> > because those methods are O(N) on the list length; manipulating the
> > middle of lists is slow.
>
> Or use slice assignment. This should work in place of the above:
>
>     mylist[:] = [mylist[i]] + mylist[:i] + mylist[i+1:]
>
> Still O(n), but so will be any implementation that removes something
> from an arbitrary list position and inserts it at the front.
>

The overall algorithm is O(n^2), as its doing a O(n) operation in a O(n)
loop:

def bringOrderStringToFront(mylist, key):
   for i in range(len(mylist)): # O(n)
        if(mylist[i].startswith(key)):
            mylist[:] = [mylist[i]] + mylist[:i] + mylist[i+1:] # O(n)

You should get an overall O(n) with (untested):

def bringOrderStringToFront(mylist, key):
    starts = []
    other = []
    for item in mylist: # O(n)
        if item.startswith(key):
            starts.append(item) # amortized O(1)
        else:
            other.append(item) # amortized O(1)
    mylist[:] = starts[::-1] + other # O(n); slice assignment mutates input
list