Move all `None` to the end of a list (python3)

Question

Given a list like

[None, None, 90, 10, None, 34, None, 108]

What's an easy way to move all Nones to the end without disturbing the order of the other elements? So, you'd get something like

[90, 10, 34, 108, None, None, None, None]

---

One possible solution is using filter with None and then just appending Nones at the end:

In [890]: l2 = list(filter(None, l))

In [891]: l2 += [None] * (len(l) - len(l2))

In [892]: l2
Out[892]: [90, 10, 34, 108, None, None, None, None]

However,

filter(None, ...) doesn't mean "filter out Nones"; None is special-cased to the identity predicate, so this will also filter out 0, False, and anything else that returns False from __bool__.

So, this isn't a good solution. Is there anything better?

Answer 1

This will preserve the sorting of the list:

>>> l = [None, None, 90, 10, None, 34, None, 108]
>>> sorted(l, key = lambda x: x is None)
[90, 10, 34, 108, None, None, None, None]

because, quoting python docs:

The built-in sorted() function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

Answer 2

I don't know Big O but this:

l2 = [x for x in l if x is not None]
l2 += [None] * l.count(None)

just works, and

l2.extend([None] * l.count(None))

is loved by many pythonists and

l2 += [None] * (len(l) - len(l2))

is better.

Answer 3

I'd build a list without Nones and pad it:

l2 = [x for x in l if x is not None]
l2 += [None] * (len(l) - len(l2))

Alternatively, there's a one-liner. I think it's theoretically O(nlogn), but I haven't observed that in practice - I think Timsort's galloping mode reduces the comparisons involved to something closer to but not quite O(n), and the data movement costs have too low a constant factor to dominate the runtime even if they're O(nlogn). In practice, the bigger disadvantage is probably that you have to think about how booleans are ordered:

sorted(l, key=lambda x: x is None)

Answer 4

A solution to keep you up at night:

>>> example = [None, None, 90, 10, None, 34, None, 108]
>>> 
>>> def some(a, *b):
...     return ([*some(*b), a] if a is None else [a, *some(*b)]) if b else [a]
... 
>>> print(some(*example))
[90, 10, 34, 108, None, None, None, None]

Explanation

We pass the the data into our function using *example so that the elements of the list become arguments. We then segment these arguments at function call using (a, *b) to place the first argument in a and the rest in b. Recursively, if a is None then the answer is:

[*some(*b), a]

which moves a to the end. Otherwise, the answer is:

[a, *some(*b)]

which keeps a in front and processes the rest of the list.

Finally, we have the if b else [a] bit which is just the base case of our recursion.

Bake-Off

We've enough solutions that it's time for a bake-off. (Let me know if I've misrepresented your solution.) We'll be summing up ten timings of a 10,000 element list in which 30% of the elements are None. I've eliminated zeros from the data so that everyone can play:

import sys
import timeit
import random

A = [random.randint(1, 1000) if random.random() > 0.3 else None for _ in range(10000)]  # ~30% None

def Rahul_comprehension(A):

    B = [x for x in A if x is not None]
    B += [None] * A.count(None)

    return B

def coldspeed_filter(A):

    B = list(filter(None, A))
    B += [None] * (len(A) - len(B))

    return B

def user2357112_comprehension(A):

    B = [x for x in A if x is not None]
    B += [None] * (len(A) - len(B))

    return B

sys.setrecursionlimit(100000)
def cdlane_recursion(A):

    def some(a, *b):
        return ([*some(*b), a] if a is None else [a, *some(*b)]) if b else [a]

    return some(*A)

from functools import reduce
def PaulMcG_reduce(A):

    return sum(reduce(lambda a,b: a[b is None].append(b) or a, A, ([], [])), [])

from itertools import zip_longest
def PaulMcG_zip_longest(A):

    non_nones = filter(lambda x: x is not None, A)
    return next(zip(*zip_longest(non_nones, A)))

def Massimiliano_sorted(A):

    return sorted(A, key=lambda x: x is None)

# sanity check to make sure everyone agrees on the answer
B = Rahul_comprehension(A)  # the accepted answer
assert B == coldspeed_filter(A)
assert B == user2357112_comprehension(A)
assert B == cdlane_recursion(A)
assert B == PaulMcG_reduce(A)
assert B == list(PaulMcG_zip_longest(A))
assert B == Massimiliano_sorted(A)

print("Rahul_comprehension:", format(timeit.timeit('B = Rahul_comprehension(A)', number=10, globals=globals()), ".2"))
print("coldspeed_filter:", format(timeit.timeit('B = coldspeed_filter(A)', number=10, globals=globals()), ".2"))
print("user2357112_comprehension:", format(timeit.timeit('B = user2357112_comprehension(A)', number=10, globals=globals()), ".2"))
print("cdlane_recursion:", format(timeit.timeit('B = cdlane_recursion(A)', number=10, globals=globals()), ".2"))
print("PaulMcG_reduce:", format(timeit.timeit('B = PaulMcG_reduce(A)', number=10, globals=globals()), ".2"))
print("PaulMcG_zip_longest:", format(timeit.timeit('B = PaulMcG_zip_longest(A)', number=10, globals=globals()), ".2"))
print("Massimiliano_sorted:", format(timeit.timeit('B = Massimiliano_sorted(A)', number=10, globals=globals()), ".2"))

Sorted Typical Best Runs: (lowest is best)

coldspeed (filter):          0.002
user2357112 (comprehension): 0.0041
Rahul (comprehension):       0.0061
PaulMcG (zip_longest):       0.024
PaulMcG (reduce):            0.025
Massimiliano (sorted):       0.026
cdlane (recursion):          5.8

Answer 5

This solution uses itertools.zip_longest to pad the shorter of two sequences with Nones. The first sequence is the non-None items from the original list, the second is the full original. zip_longest will return tuples of items from each sequence, padding with None for the shorter of the two. Then we re-zip those tuples to get back sequences, and take the first sequence, representing the filtered sequence padded with as many Nones as needed to be as long as the original.

>>> from itertools import zip_longest
>>>
>>> seq = [None, None, 90, 10, None, 34, None, 108]
>>>
>>> non_nones = filter(lambda x: x is not None, seq)
>>>
>>> reordered = next(zip(*zip_longest(non_nones, seq)))
>>>
>>> print(reordered)
(90, 10, 34, 108, None, None, None, None)

Answer 6

@cdlane's solution made me think of using reduce:

>>> seq = [None, None, 90, 10, None, 34, None, 108]
>>>
>>> from functools import reduce
>>> reordered = sum(reduce(lambda a,b: (a[0], a[1]+(b,)) 
                                       if b is None else (a[0]+(b,), a[1]), 
                           seq, ((), ())), ())
>>> print(reordered)
(90, 10, 34, 108, None, None, None, None)

EDIT: I couldn't sleep thinking about all those tuple additions, this is better:

>>>> reordered = sum(reduce(lambda a,b: a[b is None].append(b) or a, seq, ([], [])), [])