0

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?

4

3 回答 3

5

你在 O(n) 中完成它。如果你对列表进行了排序，你可以在 O(log(n)) 中完成，通过使用二进制搜索来搜索枢轴元素。事先自己排序只是为了使用二进制搜索不会有回报，因为排序是 O(n*log(n))

另一方面……真的很重要吗？如果这是您的瓶颈，那么可能重新考虑整个算法或数据结构。例如，如果您有一个复杂的问题需要对某个区域的点进行操作，您可以考虑使用kd-trees

于 2013-04-28T20:55:21.300 回答
1

这不是更快（2n），但可能更优雅，如果列表使用二进制搜索排序，您可以获得的最好结果是 log n。

>>> 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]
于 2013-04-28T20:49:14.493 回答
0

如果您希望它更简洁、pythonic 和可读性，而不损失 O(n) 性能，这可以是其中一种方式 -

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

仅迭代列表一次。

>>> 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)]
>>>
于 2014-03-08T03:53:58.497 回答