Python, split list of coordinates, based on x

Question

I have a list of coordinates, and I need to split them in half based on their x value. Something like this:

l = [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
left = []
right = []
for i in l:
    if i[0] < 2:
        left.append(i)
    else:
        right.append(i)

print(left)
print(right)

output:

[(0, 0), (1, 0), (0, 1), (1, 1)]
[(2, 0), (3, 0), (2, 1), (3, 1)]

Is there a faster way to do this?

You do it in one loop, so essentially I don't think there is a much faster way. — Lev Levitsky, Apr 28 '13 at 20:34
Might want to look at this one too: http://stackoverflow.com/questions/4578590/python-equivalent-of-filter-getting-two-output-lists-i-e-partition-of-a-list — Alexander Kuzmin, Apr 28 '13 at 20:42
You could get `log n` complexity if the list was sorted. Can you influence how the coordinates are produced? — phipsgabler, Apr 28 '13 at 20:43
another way of writing it `(left if i[0] < 2 else right).append(i)` — jamylak, Apr 29 '13 at 03:59

score 5 · Answer 1 · answered Apr 28 '13 at 20:55

You do it in O(n). If you had the list sorted, you could do it in O(log(n)), by searching for the pivot element with binary search. Sorting it yourself beforehand just to use binary search would not pay off, because sorting is O(n*log(n))

On the other hand... does it really matter? If this is your bottleneck, then maybe reconsider whole algorithm or the data structure. For instance, if you have a complex problem where you need to operate on points in some area, you can consider using kd-trees

score 1 · Accepted Answer · answered Apr 28 '13 at 20:49

This is not faster(2n) but maybe more elegant, the best you can get is log n if the list is sorted by using binary search.

>>> l = [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
>>> left = [ x for x in l if x[0] < 2]
>>> right = [ x for x in l if x[0] >= 2]

score 0 · Answer 3 · answered Mar 08 '14 at 03:53

If you would prefer it to be a little more concise, pythonic and readable, without loosing the O(n) performance, this can can be one of the ways -

right = []
left = [coord for coord in l if (lambda t: True if t[0] < 2 else right.append(t) and False)(coord)]

Iterates over the list only once.

>>> l = [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
>>> right = []
>>> left = [coord for coord in l if (lambda t: True if t[0] < 2 else right.append(t) and False)(coord)]
>>> print '\n'.join([str(left), str(right)])
[(0, 0), (1, 0), (0, 1), (1, 1)]
[(2, 0), (3, 0), (2, 1), (3, 1)]
>>>

Python, split list of coordinates, based on x

3 Answers3