python - 计算范围内唯一元素数量的有效方法？

Question

我需要计算一组给定范围内唯一元素的数量。我的输入是这些范围的开始和结束坐标，我执行以下操作。

>>>coordinates
 [[7960383, 7961255],
 [15688414, 15689284],
 [19247797, 19248148],
 [21786109, 21813057],
 [21822367, 21840682],
 [21815951, 21822369],
 [21776839, 21783355],
 [21779693, 21786111],
 [21813097, 21815959],
 [21776839, 21786111],
 [21813097, 21819613],
 [21813097, 21822369]]
 [21813097, 21822369]]
>>>len(set(chain(*[range(i[0],i[1]+1) for i in coordinates])))   #here chain is from itertools

问题是速度不够快。这在我的机器上花费了 3.5 毫秒(使用 %timeit 发现)(购买新计算机不是一种选择)并且由于我需要在数百万台设备上执行此操作，所以速度并不快。

有什么建议可以证明这一点吗？

编辑:行数可以变化。在本例中有 12 行。但我不能对其设置任何上限。

Answer 1

您可以只取坐标之间的差值，然后减去重叠部分:

coordinates =[
    [ 7960383,  7961255],
    [15688414, 15689284],
    [19247797, 19248148],
    [21776839, 21786111],
    [21813097, 21819613],
    [21813097, 21822369]
]

# sort by increasing first coordinate, and if equal, by second:
coordinates.sort()

count = 0
prevEnd = 0
for start, end in coordinates:
    if end > prevEnd: # ignore a range that is sub-range of the previous one
        count += end - max(start, prevEnd)
        prevEnd = end

print (count)

这在空间和时间上都很便宜。

包含结束坐标

编辑后，很明显您希望第二个坐标包含在内。在那种情况下，像这样“正确”计算:

count = 0
prevEnd = -1
for start, end in coordinates:
    if end > prevEnd: # ignore a range that is sub-range of the previous one
        count += end - max(start - 1, prevEnd)
        prevEnd = end