What's the efficient way to split a List to several list in python

Question

I want to split a List to several List according to some expression.

For example:

for elem in elemList:
     if elem>0 and elem<=3   add element to Partition1
     if elem>3 and elem<=6   add element to Partition2
     else                    add element to Partition3

How to do it efficiently? Is there something like erase and push_back in list in C++ whose complexity is O(1)?

Or are there some other collections that can do it?

partition1 = [elem for elem in elemList if elem > 0 and elem <= 3] list comprehension is efficient than for in , but it can only contain one if statement following one for statement — Kevin Yan, Sep 22 '15 at 02:10
Most definitely **not** a duplicate of that question. This only bears a passing resemblance to a proper use case for groupby; the groups aren't contiguous, and the grouping condition is better expressed as a sequence of predicates than as a grouping key. — user2357112, Sep 22 '15 at 02:18
@PunyTitan are all elemsn limited between 0 and 9 ? or there can be other elements? — Anand S Kumar, Sep 22 '15 at 02:23
@AnandSKumar Yes there could be other type of list. For example, the list contains a lot of string elements, and I want to split them to different list according to there length. — PunyTitan, Sep 22 '15 at 02:43
@PunyTitan assuming you are talking about time complexity, you can't accomplish `O(1)` as you'll always end up having to iterate over `elemList` no matter what. — Ozgur Vatansever, Sep 22 '15 at 03:20
@ozgur Thanks. Yeah, I don't mean to obtain O(1) complexity for the whole process. I want to know whether the split action for one element could be O(1). Since to delete an element in a List(), it will cost O(n). I am wondering whether I can avoid this. — PunyTitan, Sep 22 '15 at 03:25

score 2 · Answer 1 · answered Sep 22 '15 at 02:13

2

If I understand the question correctly, you can use list comprehensions:

Partition1 = [elem for elem in elemList if elem <= 3]
Partition2 = [elem for elem in elemList if elem > 3 and elem <= 6]
Partition3 = [elem for elem in elemList if elem > 6]

Which is the pythonic way of doing (for Partition1):

Partition1 = [] # creates an empty list
for elem in elemList: # for each element in list
    if elem > 0 and elem <= 3: # if they satisfy the condition
        Partition1.append(elem) # append them to the list

Edit: I'm assuming above that all elems are greater than zero... If some of them aren't, the list comprehensions for Partition1 and Partition3 would have to be:

Partition1 = [elem for elem in elemList if elem > 0 and elem <= 3]
Partition3 = [elem for elem in elemList if elem > 6 or elem <= 0]

answered Sep 22 '15 at 02:13

Lucas Murtinho

95
1
1
8

@JoseRicardoBustosM. "better" in which sense ? – Nir Alfasi Sep 22 '15 at 02:16
@JoseRicardoBustosM.: Hell no. groupby is completely unsuited to the task, the primary reason being that the groups aren't required to be contiguous. – user2357112 Sep 22 '15 at 02:19
@JoseRicardoBustosM.: It's just three passes, and for groupby to be any better, you'd need to formulate the grouping key in such a way that you don't end up performing three passes worth of effort. We're not dealing with a number of passes that rises with the size of the input. – user2357112 Sep 22 '15 at 02:26

score 1 · Accepted Answer · answered Sep 22 '15 at 03:56

First of all, here is a good cheat sheet for time-complexity of various operations in Python.

Given your last reply to my statement, I assume you want to consume and split given list into three separate lists without creating any intermediate lists via comprehensions. One way to accomplish this would be changing your data structure to collections.deque as list.remove() takes O(n) (because it requires shifting elements) whereas deque.popleft() takes O(1).

>>> def partition(queue):
...     partition1, partition2, partition3 = [], [], []
...     while queue:
...         ele = queue.popleft()
...         if 0 < ele <= 3:
...             partition1.append(ele)
...         elif 3 < ele <= 6:
...             partition2.append(ele)
...         else:
...             partition3.append(ele)
...     return partition1, partition2, partition3 

>>> import collections
>>> p1, p2, p3 = partition(collections.deque(range(10)))

>>> print p1
[1, 2, 3]

>>> print p2
[4, 5, 6]

>>> print p3
[0, 7, 8, 9]

What's the efficient way to split a List to several list in python

2 Answers2