python list sorting issue

97 views
Skip to first unread message

Virbhadra Gupta

unread,
Nov 5, 2017, 9:07:32 AM11/5/17
to Python Programming for Autodesk Maya


i was trying to sort list by only 0 and other Numbers like [2,0,0,4] to [2,4,0,0]
i come up with this code but in this code variable list is changing. i am unable to understand why ?

list = [4,0,0,4]

def re_sort(list):
    count=0
    tmp_list = list
    print list
    for i in list:
        if not i:
            tmp_list.remove(i)
            count+=1
    print list
    for n in range(count):
        tmp_list.append(0)
    return tmp_list
re_sort(list)

************************
re_sort(list)
[4, 0, 0, 4]
[4, 0, 4]
# Result: [4, 0, 4, 0] # 

Alok Gandhi

unread,
Nov 5, 2017, 9:35:12 AM11/5/17
to python_in...@googlegroups.com
use:
tmp_list = list[:]
this will create a copy instead of a reference.
Also `list` is a python object type name, use 'list_' as variable name instead of `list`

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/e4b95d9e-bda4-4499-9d94-860be6aaaf5b%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.



--

Balazs Pataki

unread,
Nov 6, 2017, 10:58:53 AM11/6/17
to Python Programming for Autodesk Maya
You could also try this, which is a bit more pythonic, also faster.

def re_sort(to_sort):
    # we need those zeroes so we check how many of them we have
    nr_of_zeroes = to_sort.count(0)
    # list comprehension that gets rid of zeroes
    filtered = [item for item in to_sort if item != 0]
    # we append together the filtered part and inplace add a list of zeroes of length nr_of_zeroes
    return filtered + [0]*nr_of_zeroes

While this has time complexity of O(n), yours is O(n^2), so the longer your list gets, the worse your performance gets.

Justin Israel

unread,
Nov 6, 2017, 1:47:27 PM11/6/17
to python_in...@googlegroups.com


On Tue, Nov 7, 2017, 4:58 AM Balazs Pataki <blaise...@gmail.com> wrote:
You could also try this, which is a bit more pythonic, also faster.

def re_sort(to_sort):
    # we need those zeroes so we check how many of them we have
    nr_of_zeroes = to_sort.count(0)
    # list comprehension that gets rid of zeroes
    filtered = [item for item in to_sort if item != 0]
    # we append together the filtered part and inplace add a list of zeroes of length nr_of_zeroes
    return filtered + [0]*nr_of_zeroes

While this has time complexity of O(n), yours is O(n^2), so the longer your list gets, the worse your performance gets.

I'm not great at big O notation. Is the original solution suggested to be O(n^2) because of the nested remove(i) call within the loop? Would that have a logarithmic complexity instead because the list becomes shorter everytime it finds a 0 and removes it? Otherwise it would not remove at all for nonzero. 

And then your solution has two O(n) calls (the count and the list comp) so that is O(n) yea? Then you have the memory complexity of needing to allocate temporary lists for the final nonzero and zero lists. 

Here is one more approach that uses a sort in place. It has both examples depending on whether you want the nonzero numbers sorted or not. 


by_nonzero = lambda i: 0 if i else 1

l = [4,0,8,0,0,2,1,-5]
l.sort(key=by_nonzero)
print l
# [4, 8, 2, 1, -5, 0, 0, 0]


import sys
maxint = sys.maxint

by_nonzero = lambda i: i or maxint

l = [4,0,8,0,0,2,1,-5]
l.sort(key=by_nonzero)
print l
# [-5, 1, 2, 4, 8, 0, 0, 0]





On Sunday, November 5, 2017 at 3:07:32 PM UTC+1, Virbhadra Gupta wrote:


i was trying to sort list by only 0 and other Numbers like [2,0,0,4] to [2,4,0,0]
i come up with this code but in this code variable list is changing. i am unable to understand why ?

list = [4,0,0,4]

def re_sort(list):
    count=0
    tmp_list = list
    print list
    for i in list:
        if not i:
            tmp_list.remove(i)
            count+=1
    print list
    for n in range(count):
        tmp_list.append(0)
    return tmp_list
re_sort(list)

************************
re_sort(list)
[4, 0, 0, 4]
[4, 0, 4]
# Result: [4, 0, 4, 0] # 

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/700827e3-cb90-4106-8da4-350e08096dbd%40googlegroups.com.

Marcus Ottosson

unread,
Nov 6, 2017, 3:55:56 PM11/6/17
to python_in...@googlegroups.com

Ooo, I’ve been waiting for a reason to use this!

# import sys
# maxint = sys.maxint

by_nonzero = lambda i: i or float("inf")

l = [4,0,8,0,0,2,1,-5]
l.sort(key=by_nonzero)

print l
# [-5, 1, 2, 4, 8, 0, 0, 0]
​

To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/CAPGFgA1k7yVorfG_sbf2Pj7%3DG4qo5X-A7vhOO0DQZseu%3DxSGjA%40mail.gmail.com.

Marcus Ottosson

unread,
Nov 6, 2017, 4:02:19 PM11/6/17
to python_in...@googlegroups.com

Though this is probably not particularly useful for the problem the OP’s was having, which is that lists in Python are mutable.

Meaning that, when you pass a list into a function, changes you make to it are also made to the original list you passed in. If you’re familiar with C++, then you can think of the list you pass as being passed by reference.

def append(a, b):
  a.append(b)

my_list = ["Hello"]
append(my_list, "World")

print(" ".join(my_list))
# Hello World

In order to pass a list, and not modify it, you can do what Alok suggested, which is to make a copy of the list inside of the function.

def append(a, b):
  copy = a[:]  
  copy.append(b)

my_list = ["Hello"]
append(my_list, "World")

print(" ".join(my_list))
# Hello
​

Justin Israel

unread,
Nov 6, 2017, 6:50:49 PM11/6/17
to python_in...@googlegroups.com
On Tue, Nov 7, 2017 at 9:55 AM Marcus Ottosson <konstr...@gmail.com> wrote:

Ooo, I’ve been waiting for a reason to use this!

# import sys
# maxint = sys.maxint

by_nonzero = lambda i: i or float("inf")

l = [4,0,8,0,0,2,1,-5]
l.sort(key=by_nonzero)

print l
# [-5, 1, 2, 4, 8, 0, 0, 0]
​


Ah, that's pretty hot! Nice one.

 
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/CAFRtmOA8PD%3DAMFtoyMvoQ5J3BT69GWxJotk%3DPk0yG0dh_FvCWw%40mail.gmail.com.

Alok Gandhi

unread,
Nov 7, 2017, 4:55:56 AM11/7/17
to python_in...@googlegroups.com
Being really picky, please do not use lambda in a variable (PEP8) -

Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.

Yes:

def f(x): return 2*x

No:

f = lambda x: 2*x

The first form means that the name of the resulting function object is specifically 'f' instead of the generic '<lambda>'. This is more useful for tracebacks and string representations in general. The use of the assignment statement eliminates the sole benefit a lambda expression can offer over an explicit def statement (i.e. that it can be embedded inside a larger expression)


To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsubscribe@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsubscribe@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.



--

Justin Israel

unread,
Nov 7, 2017, 5:27:23 AM11/7/17
to python_in...@googlegroups.com


On Tue, Nov 7, 2017, 10:55 PM Alok Gandhi <alok.ga...@gmail.com> wrote:
Being really picky, please do not use lambda in a variable (PEP8) -

Always use a def statement instead of an assignment statement that binds a lambda expression directly to an identifier.

Yes:

def f(x): return 2*x

No:

f = lambda x: 2*x

The first form means that the name of the resulting function object is specifically 'f' instead of the generic '<lambda>'. This is more useful for tracebacks and string representations in general. The use of the assignment statement eliminates the sole benefit a lambda expression can offer over an explicit def statement (i.e. that it can be embedded inside a larger expression)


Thanks for the suggestion, Alok.


To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.



--

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_m...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/CAPaTLMSrJKG_Vuj5PxmjScOhc_Ly%3Ds2B9KLpBLbY_wy087h6aA%40mail.gmail.com.

Marcus Ottosson

unread,
Nov 7, 2017, 5:40:05 AM11/7/17
to python_in...@googlegroups.com

Also don’t declare functions on a single line (PEP8, E704) ;)

# No
def f(x): return 2*x

# Yes
def f(x):
  return 2*x
​

To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.
--

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Python Programming for Autodesk Maya" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/CAPGFgA1L_Wvsf0bUajceGp6AgBiA6exQnOUZOy-hx-ZToz9Ffg%40mail.gmail.com.

Balazs Pataki

unread,
Nov 10, 2017, 10:28:21 AM11/10/17
to Python Programming for Autodesk Maya
I hope I'm not going too off topic with this. Just some clarifications :)

Is the original solution suggested to be O(n^2) because of the nested remove(i) call within the loop?
Exactly.
Would that have a logarithmic complexity instead because the list becomes shorter everytime it finds a 0 and removes it? 
If we have no zeroes, then a simple count would eliminate the iteration. But instead, we still try to remove values so we get O(n*n)
If we have a list of only zeroes and we reduce our list to length zero, we iterate the full length, remove an element until we have none and we would have something like this:
n + (n-1) + (n-2) ... +1)
Famous pattern that results in O(0.5n^2 + 0.5n) --> We can drop the constants as above, and also we can skip the linear part here since n*n will be way larger than just n if we have relatively large n.
Example with n = 100 and n = 1000 we can see the quadratic growth:
n=100:       5050
n=1000: 500500
Even though n increased by a factor of 10, our values increased by a factor of ~99.1 in this case.
A list is not really a good choice for removing elements from random places due to reordering, that's why its O(n).
You could time this and verify for yourself.
python -m timeit "listerine = [0]*100;listerine.remove(0)"
We have to subtract list creation from timing.
python -m timeit "listerine = [0]*100"
And just increase those numbers as we go on. 

And then your solution has two O(n) calls (the count and the list comp) so that is O(n) yea? 
Yes. O(constant*n) -> O(n) is just the canonical form of writing it. It's still linear growth. Simplest example: 2*100 && 2*1000 -> we have tenfolds increase even if remove that constant.
Then you have the memory complexity of needing to allocate temporary lists for the final nonzero and zero lists. 
I concur. This very example though has small ints which are cached by python and we can go into ranges of millions and we will still talk about a few megs.

import sys
maxint = sys.maxint
by_nonzero = lambda i: i or maxint
l = [4,0,8,0,0,2,1,-5]
l.sort(key=by_nonzero)
print l
# [-5, 1, 2, 4, 8, 0, 0, 0]
 
Yes, this is a good approach. That's where my method will fail. I just wrote it for this very example and because list comprehensions are super optimized. :) 

Also, there's the sorted method, which works not just on lists but on any iterable, but of course it does a copy of the original iterable if you don't want it altered.
e.g:
import string, operator, random
dict_compr = {letter : random.randint(0, 10) for letter in string.ascii_lowercase}
sorted_by_values = sorted(dict_compr.iteritems(), key=operator.itemgetter(1))

 
To unsubscribe from this group and stop receiving emails from it, send an email to python_inside_maya+unsub...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages