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 <https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF> 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 )) On Monday, November 6, 2017 at 7:47:27 PM UTC+1, Justin Israel wrote: > > > > On Tue, Nov 7, 2017, 4:58 AM Balazs Pataki <blaise...@gmail.com > <javascript:>> 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_maya+unsubscr...@googlegroups.com <javascript:>. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/python_inside_maya/700827e3-cb90-4106-8da4-350e08096dbd%40googlegroups.com >> >> <https://groups.google.com/d/msgid/python_inside_maya/700827e3-cb90-4106-8da4-350e08096dbd%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> For more options, visit https://groups.google.com/d/optout. >> > -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/python_inside_maya/9344e0b9-2894-413f-a628-80591bfce785%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
