问题描述
我正在寻找一些python代码来有效地计算间隔重叠.我以前使用过bx-python包的间隔树,但是现在需要从树中删除间隔(或者更好的是修改它们).看来bx-python树不支持此功能.
I am looking for some python code to efficiently compute interval overlaps.I've used the interval tree of the bx-python package before, but now need to delete intervals from the tree (or better yet, modify them).It seems the bx-python tree doesn't support this.
有指针吗?
推荐答案
banyan
支持从树中删除间隔.例如,要从间隔列表中删除最小数量的间隔,以使剩下的间隔在O(n log n)
,banyan.SortedSet
(增强的红黑树)中不重叠:
banyan
supports deleting intervals from the tree. For example, to remove a minimal number of intervals from a list of intervals such that the intervals that are left do not overlap in O(n log n)
, banyan.SortedSet
(augmented red-black tree) could be used:
from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan
def maximize_nonoverlapping_count(intervals):
# build "interval" tree sorted by the end-point O(n log n)
tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
updator=OverlappingIntervalsUpdator)
result = []
while tree: # until there are intervals left to consider
# pop the interval with the smallest end-point, keep it in the result
result.append(tree.pop()) # O(log n)
# remove intervals that overlap with the popped interval
overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
tree -= overlapping_intervals # O(m log n)
return result
示例:
print maximize_nonoverlapping_count([[3, 4], [5, 8], [0, 6], [1, 2]])
# -> [[1, 2], [3, 4], [5, 8]]
请参见 Python-删除重叠列表.
这篇关于Python:动态间隔数据结构的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!