On Fri, Apr 1, 2016 at 1:52 PM, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> On Fri, Apr 1, 2016 at 2:39 PM, Rob Gaddi
> <rgaddi@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
--
https://mail.python.org/mailman/listinfo/python-list
