Pushing all non empty items to the end of a list

Question

I have a list like this

list_ = [" ", " ", "X", " ", " ", "Z", " ", "Y", " "]

I am writing a function that will result in

list_ = [" ", " ", " ", " ", " ", " ", "X", "Z", "Y"] 

Basically it will push all the non-empty (I'll call " " as empty here for simplicity) to the end of the list while retaining their orders

My solution as follow

def push(list_):
    def find_current_element(list_, from_):
        for i in range(from_+1, len(list_)):
            if list_[i] != " ":
                return i
        return None

    list_ = list_[::-1]
    good_index = list_.index(" ")
    current_element_index = find_current_element(list_, 0)
    while(current_element_index is not None):
        for i in range(good_index, len(list_)):
            if list_[i] != " ":
                list_[good_index], list_[i] = list_[i], " "
                good_index += 1
                current_element_index = find_current_element(list_, current_element_index)
    return reversed(list_)

It works, but it seems too long and using too much resource (reverse the list twice and bunch of for loops). I wouldn't care if the items were just simple character, but I plan to have some big objects as items of the list. I am wondering is there a simpler approach

Answer 1

Your code is incorrect, for example for input [' ', 'X', 'Y'] you get into an infinite loop.

You could just sort by emptiness, which with your apparent definition can be done like this:

>>> list_ = [" ", " ", "X", " ", " ", "Z", " ", "Y", " "]
>>> list_.sort(key=' '.__ne__)
>>> list_
[' ', ' ', ' ', ' ', ' ', ' ', 'X', 'Z', 'Y']

Or more generally (though slower) with a lambda or other self-made function:

list_.sort(key=lambda x: x != ' ')
list_.sort(key=is_non_empty)
list_.sort(key=is_empty, reverse=True)

If you actually had empty strings instead of strings containing a space character, or in general if your objects followed Python's usual thing of empty objects being false and non-empty objects being true, then you could also do this:

list_.sort(key=bool)

Answer 2

(EDITED to include a better analysis and improve the partition-based alternative)

Take-home message

def push_side_part(seq):
    seq = list(seq)  # remove this for inplace
    n = len(seq)
    j = n - 1
    for i in range(n - 1, -1, -1):
        if seq[i] != ' ':
            seq[j], seq[i] = seq[i], seq[j]
            j -= 1
    return seq

This is an efficient (both time O(1) and memory O(N)) and simple alternative for solving the problem. It is based on a variation of Lomuto partitioning used in QuickSort. None of the other proposed solution gets to both. The solution based on sorting is, at best, O(N log N) in time and O(1) in memory.

For the input sizes I tested, the code runs approximately as fast as the list.sort()-based alternative, but can be made roughly one order of magnitude faster by compiling it as is with Cython.

---

Analysis of Original Code

First, lets comment your code:

• The code fails right at the start with the .index() call, if the input does not contain empty strings ' '
• The code gets into infinite loop if, for whatever reason (e.g. for input [' ', 'b', ' ', 'b', 'b']), it does not enter the for loop, so this should be properly handled
• Your code for find_current_element() is not type-stable. Particularly, if the function fails it returns None. However, without loss in functionality, you could return a negative index, say -1. This is a matter of taste in Python but in light of future optimization, it may be relevant. Note that some built-in functions in Python (like e.g. string.find()) are type-stable in a similar fashion and some other built-in functions are not (e.g. string.index()) so you have both choices even within the standard library.
• I am not sure what is the reason for you to use return reversed(...) which returns an iterator, but I would rather return the reversed list via slicing

A safer version of your code, while still retaining your approach is:

def find_current_element(seq, index):
    for i in range(index + 1, len(seq)):
        if seq[i] != " ":
            return i
    return -1


def push_side_OP(seq):
    result = seq[::-1]
    try:
        good_index = result.index(" ")
    except ValueError:
        return seq
    else:
        curr_index = find_current_element(result, 0)
        while curr_index >= 0:
            for i in range(good_index, len(result)):
                if result[i] != " ":
                    result[good_index], result[i] = result[i], " "
                    good_index += 1
                    curr_index = find_current_element(result, curr_index)
            else:
                curr_index = -1
        return result[::-1]

---

A more polished way of writing essentially this same algorithm is:

def neg_rfind(seq, item, index=-1):
    n = len(seq)
    index %= n
    for i in range(index, -1, -1):
        if seq[i] != item:
            return i
    return -1


def rfind(seq, item, index=-1):
    n = len(seq)
    index %= n
    for i in range(index, -1, -1):
        if seq[i] == item:
            return i
    return -1
    # try:
    #     return len(seq) - seq[::-1].index(item, index) - 1
    # except ValueError:
    #     return -1



def push_side_loop(seq):
    seq = list(seq)  # remove this for inplace
    j = rfind(seq, ' ')
    i = neg_rfind(seq, ' ')
    while i >= 0:
        for l in range(j - 1, -1, -1):
            if seq[l] != ' ':
                seq[j], seq[l] = seq[l], ' '
                j -= 1
                i = neg_rfind(seq, ' ', i - 1)
        else:
            i = -1

Now, the algorithm itself is memory efficient (O(1)) but it is not very time efficient (O(N²)? -- I am not 100% sure). In particular, this is updating index i (with a rather expensive neg_rfind() call_ in a loop where i is not required to be updated. Additionally, there seems to be an unnecessary nested loop. Somehow, this resembles bubble-sort which is an inefficient sorting algorithm.

But even if you were to implement an efficient sorting algorithm (which is sort of reinventing the wheel, as Python already has sorted() and list.sort()), the problem you are trying to solve is simpler than that.

---

Alternatives

For simpler comparison, the functions provided here are all preserving the input, but some could be easily made in-place, by simply skipping the line seq = list(seq) or similar.

Some alternatives, while in principle very efficient, contain explicit looping, which is somewhat slow in Python. However, they can be easily made very fast with Cython (with the _cy suffix in benchmarks), and will be comparable to those pure Python solutions that avoid explicit looping (and recursion).

Using partitioning

You could use a variation of the partitioning functions used in sorting algorithms. Here is a variation / generalization of Lomuto partitioning used in QuickSort:

def partition_inplace(seq, condition, start=0, stop=-1):
    n = len(seq)
    start %= n
    stop %= n
    step = 1 if start < stop else -1
    for i in range(start, stop + step, step):
        if condition(seq[i]):
            seq[start], seq[i] = seq[i], seq[start]
            start += step
    if step > 0:
        return start
    else:
        return start + 1

This both separates the sequence inplace (according to the condition) and returns the index at which this separation occurs).

Since partitioning retain the order of the elements on only one side (the side of the elements satisfying the condition) one needs to run it backward with the non-empty condition. Also the separating index is not needed.

Hardcoding all this for speed (essentially one needs to avoid the expensive call to condition inside the main loop), one would get:

def push_side_part(seq):
    seq = list(seq)  # remove this for inplace
    n = len(seq)
    j = n - 1
    for i in range(n - 1, -1, -1):
        if seq[i] != ' ':
            seq[j], seq[i] = seq[i], seq[j]
            j -= 1
    return seq

This is both time and memory efficient. Note that this is essentially the same as @Peilonrayz' first answer except that it avoids using unnecessary generators.

Using sorting (from @HeapOverflow's answer)

def push_side_sort(seq):
    result = list(seq)
    result.sort(key=' '.__ne__)
    return result

This will have time and memory efficiency of sorting (which is typically worse than the problem you are trying to solve).

Using functools.reduce() (from @Opus' answer)

def push_side_reduce_slow(seq):
    def sided_join(items, item):
        if item == ' ':
            return [item] + items
        else:
            return items + [item]
    return functools.reduce(sided_join, seq, [])

While this is a very elegant approach for functional-style programming, it is in practice quite inefficiently creating temporary lists all the time (it is so slow it will go off charts and it is not included in the benchmarks) A slightly more efficient approach will use list.insert(), e.g.:

def push_side_reduce(seq):
    def sided_join(items, item):
        items.insert(0 if item == ' ' else len(items), item)
        return items
    return functools.reduce(sided_join, seq, [])

However, inserting at the beginning of a list is an O(N) (N being the number of elements of the list) for Python lists, because they are implemented as dynamic arrays.

Using filter() (essentially the same as @Peilonrayz' second answer)

def push_side_filt2(seq):
    return (
        list(filter(lambda x: x == ' ', seq))
        + list(filter(lambda x: x != ' ', seq)))

uses filter() instead of a comprehension, but it is otherwise the same. This can be further improved because the first filtering can be omitted and replaced with a quicker list repetition, given that it will always be repeating the empty string.

def push_side_filt(seq):
    non_empty = list(filter(lambda x: x != ' ', seq))
    return [' '] * (len(seq) - len(non_empty)) + non_empty

Using a buffer (essentially @Graipher's answer)

def empty_first(items):
    buffer = []
    for item in items:
        if item == " ":
            yield item
        else:
            buffer.append(item)
    yield from buffer


def push_side_buff(seq):
    return list(empty_first(seq))

This is the computationally most efficient approach for keeping the order of both the empty and the non-empty elements. However, it is not quite as much memory efficient because of the extra memory required by the buffer.

---

Benchmarks

Generating Input

def gen_input(n, k=0.5, tokens=string.ascii_letters + string.digits):
    picks = tokens + ' ' * int(len(tokens) * k)
    m = len(picks)
    return [picks[random.randint(0, m - 1)] for _ in range(n)]

Checking for Valid Output

def equal_output(a, b, with_order=True):
    if with_order:
        return a == b
    else:
        n = a.count(' ')
        m = b.count(' ')
        return a[:n] == b[:m]

Results

Input sizes generated using:

input_sizes = tuple(int(2 ** (2 + (3 * i) / 4)) for i in range(4, 21))
# N = (32, 53, 90, 152, 256, 430, 724, 1217, 2048, 3444, 5792, 9741, 16384, 27554, 46340, 77935, 131072)

and with 40x and 10x zoom on the faster methods, respectively:

This shows that push_side_part() is as fast as a list.sort()-based solution (which would be otherwise the fastest non-Cython-accelerated solution) and compiling this in Cython results in much faster timings than any of the proposed solutions.

---

Full code available here.

Answer 3

• find_current_element is a poor name, find_nonempty would better describe what it's doing.
• find_current_element is a strange form of iteration where you constantly resume the function from where it left off. This would be better described using a generator function.
• Your function is good as you're swapping items in the list rather than list.insert(0, value).
• You don't need to invert the list twice as you can just work backwards, appending to the end.
• Since we can do this by mutating the original list, I won't return the new list.

def find_nonempty(values, is_empty):
    for i in reversed(range(len(values))):
        if not is_empty(values[i]):
            yield i

def push(values, is_empty):
    good_index = len(values) - 1
    for i in find_nonempty(values, is_empty):
        values[i], values[good_index] = values[good_index], values[i]
        good_index -= 1

>>> list_ = [" ", " ", "X", " ", " ", "Z", " ", "Y", " "]
>>> push(list_, lambda i: i == " ")
>>> list_
[' ', ' ', ' ', ' ', ' ', ' ', 'X', 'Z', 'Y']

Personally I would just use two list comprehensions, if I were to not use list.sort, as the logic would be much clearer.

def push(values, is_empty):
    return (
        [v for v in values if is_empty(v)]
        + [v for v in values if not is_empty(v)]
    )

Answer 4

If you want to go for readability, I would prefer a plain generator approach. This one uses only \$\mathcal{O}(n)\$ time but uses \$\mathcal{O}(k)\$ additional space, where \$n\$ is the number of elements in the list and \$k\$ is the number of non-empty values. This is in contrast to sorting (\$\mathcal{O}(n \log n)\$ time \$\mathcal{O}(1)\$ space) and using two independent list comprehensions (\$\mathcal{O}(2n)\$ time and \$\mathcal{O}(n)\$ space).

Note that for speed only the number of elements in the list matters, not how big each element is, because a Python list only stores pointers to the objects.

def empty_first(it):
    buffer = []
    for x in it:
        if x == " ":
            yield x
        else:
            buffer.append(x)
    yield from buffer

Just wrap the calling code with a list:

list_ = [" ", " ", "X", " ", " ", "Z", " ", "Y", " "]
print(list(empty_first(list_)))
# [' ', ' ', ' ', ' ', ' ', ' ', 'X', 'Z', 'Y']

Performance wise, all of these approaches might be easier and more readable, but if you need raw speed, you should time the different approaches.

Answer 5

The most elegant and declarative approach in my opinion is using reduce.

>>> from functools import reduce
>>> list_ = [" ", " ", "X", " ", " ", "Z", " ", "Y", " "]
>>> reduce(lambda xs, x: xs + [x] if x.strip() != "" else [x] + xs, list_, [])
[' ', ' ', ' ', ' ', ' ', ' ', 'X', 'Z', 'Y']

How it works: reduce takes 3 arguments: a function, a list, and an initial value. It then calls the function consistently for each element in the list, and each time replaces the saved initial value with return of this function, which is called with the current version of (now not initial, but accumulated) value as a first argument, and current element of a list as a second argument, and then returns accumulated value.

With this we can using a single line loop through the list and conditionally append or prepend values to the new list, returning it at the end.

More: https://docs.python.org/3/library/functools.html#functools.reduce

Answer 6

Peilonrayz said:

Personally I would just use two list comprehensions, if I were to not use list.sort, as the logic would be much clearer.

I agree with this, this is the Pythonic way, short and straight to the point. And if you don't need a fancy function for evaluating what qualifies as non-empty then you could even strip down the code proposed by Peilonrayz and summarize it to a one-liner:

[i for i in list_ if i == " "] + [i for i in list_ if i != " "]

returns:

[' ', ' ', ' ', ' ', ' ', ' ', 'X', 'Z', 'Y']

which could be just enough for your purpose, based on your example containing strings. Although I feel his answer should be the accepted answer as it is more elegant and provides more flexibility, since your criteria can change. A good function should be flexible and reusable.

---

Additional notes:

Since the OP seems to be concerned with possible performance issues with large lists it may be worth mentioning that a list comprehension will load the whole output list to memory. There is an alternative and that is using a generator expression. A generator expression can be iterated over but yields one item at a time on demand.

Generator Expressions are somewhat similar to list comprehensions, but the former doesn’t construct list object. Instead of creating a list and keeping the whole sequence in the memory, the generator generates the next element in demand.

Source: Python List Comprehensions vs Generator Expressions

The performance improvement from the use of generators is the result of the lazy (on demand) generation of values, which translates to lower memory usage. Furthermore, we do not need to wait until all the elements have been generated before we start to use them. This is similar to the benefits provided by iterators, but the generator makes building iterators easy.

Source: wiki.python.org - Generators

They are slightly different than lists, for instance you cannot merge them like lists using + as shown above. One way of doing it could be:

from itertools import chain
list_empty=(i for i in list_ if i == " " )
list_not_empty=(i for i in list_ if i != " " )
list_full = chain(list_empty, list_not_empty) 

>>> type(list_full)
<class 'itertools.chain'>

There may be a better way. Note that the result is an object of type itertools.chain.
Disclaimer: I still lack familiarity with some of the aspects but I nonetheless want to share my findings for the benefit of others and of course the OP can further research the idea.

Answer 7

there is a lot of way to do this...as people answered before but there is easy and simplified code..but easy understandable code

 def push_non_empty_items(given_list):

    pushed_list=[]
    for i in range(len(given_list)):
        if given_list[i] != " ":
            pushed_list.append(given_list[i])


    no_non_empty_items = len(given_list) - len(pushed_list)


    empty_list = [" "] * no_non_empty_items
    return (empty_list + pushed_list)


print(push_non_empty_items([" ", " ", "X", " ", " ", "Z", " ", "Y", " "]))