Python: оптимизация попарных перекрытий между интервалами ⇐ Python

[Anonymous]

У меня большое количество интервалов (от 5 до 10 тысяч). Эти элементы имеют начальную и конечную позицию; например (203, 405). Координаты интервалов сохраняются в списке.

Я хочу определить координаты и длины перекрывающихся частей между каждой парой интервалов. Это можно сделать следующим образом:

Код: Выделить всё

# a small list for clarity, with length normally around 5000s
cList = ((20, 54), (25, 48), (67, 133), (90,152), (140,211), (190,230))
for i, c1 in enumerate(cList[:-1]): # a linear pairwise combination
for c2 in cList[i + 1:]:
left =  max(c1[0], c2[0])
right = min(c1[1], c2[1])
overlap = right - left
if overlap > 0:
print "left: %s, right: %s, length: %s" % (left, right, overlap)

Результат:

Код: Выделить всё

left: 25, right: 48, length: 23
left: 90, right: 133, length: 43
left: 140, right: 152, length: 12
left: 190, right: 211, length: 21

Как видно, это работает... поскольку это может занять довольно много времени (20 секунд), мой вопрос: как мне это оптимизировать? Я попытался обрезать второй цикл for, когда начальная позиция второго цикла превышает конечную позицию первого:

Код: Выделить всё

if c1[1] < c2[0]:
break

Это резко сокращает время процедуры, но в результате количество перекрытий примерно в три раза меньше, чем раньше, и поэтому результат заведомо недействителен. Это вызвано элементами, длина которых намного превышает длину предыдущих элементов.

Я уверен, что есть какой-то математический трюк, чтобы решить эту проблему.

Подробнее здесь: https://stackoverflow.com/questions/232 ... -intervals