Python:动态间隔数据结构 [英] Python: Dynamic interval data structure

问题描述

我正在寻找一些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:动态间隔数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！