python - 独特的一组范围，在需要时合并

Question

是否有数据结构可以维护一组独特的范围，合并一个连续或重叠的范围？我需要跟踪哪些范围已经被处理，但是这可能以任意顺序发生。例如：

range_set = RangeSet() # doesn't exist that I know of, this is what I need help with 

def process_data(start, end): 
    global range_set 
    range_set.add_range(start, end) 
    # ... 

process_data(0, 10) 
process_data(20, 30) 
process_data(5, 15) 
process_data(50, 60) 

print(range_set.missing_ranges()) 
# [[16,19], [31, 49]] 

print(range_set.ranges()) 
# [[0,15], [20,30], [50, 60]] 

请注意，重叠或连续范围会合并在一起。做这个的最好方式是什么？我看着使用平分模块，但它的使用似乎并不明显。

Answer 1

您可以使用pythons内置的set数据结构获得一些类似的功能;假设只有整数值对start和end有效。

>>> whole_domain = set(range(12)) 
>>> A = set(range(0,1)) 
>>> B = set(range(4,9)) 
>>> C = set(range(3,6)) # processed range(3,5) twice 
>>> done = A | B | C 
>>> print done 
set([0, 3, 4, 5, 6, 7, 8]) 
>>> missing = whole_domain - done 
>>> print missing 
set([1, 2, 9, 10, 11]) 

这仍然缺乏许多“范围”功能，但可能已足够。

一个简单的查询，如果在一定的范围已经被处理看起来是这样的：

>>> isprocessed = [foo in done for foo in set(range(2,6))] 
>>> print isprocessed 
[False, True, True, True] 

Answer 2

我只是轻轻地测试，但它听起来像你正在寻找这样的事情。您需要添加方法来自己获取范围和丢失范围，但它应该非常直接，因为RangeSet.ranges是按排序顺序维护的Range对象的列表。例如，对于更愉快的界面，您可以编写一个便利的方法，将其转换为2元组列表。

编辑：我刚刚修改它使用少于或等于比较合并。但请注意，这不会合并“相邻”条目（例如，它不会合并(1, 5)和(6, 10)）。要做到这一点，你只需要修改Range.check_merge()中的条件。

import bisect 


class Range(object): 

    # Reduces memory usage, overkill unless you're using a lot of these. 
    __slots__ = ["start", "end"] 

    def __init__(self, start, end): 
     """Initialise this range.""" 
     self.start = start 
     self.end = end 

    def __cmp__(self, other): 
     """Sort ranges by their initial item.""" 
     return cmp(self.start, other.start) 

    def check_merge(self, other): 
     """Merge in specified range and return True iff it overlaps.""" 
     if other.start <= self.end and other.end >= self.start: 
      self.start = min(other.start, self.start) 
      self.end = max(other.end, self.end) 
      return True 
     return False 


class RangeSet(object): 

    def __init__(self): 
     self.ranges = [] 

    def add_range(self, start, end): 
     """Merge or insert the specified range as appropriate.""" 
     new_range = Range(start, end) 
     offset = bisect.bisect_left(self.ranges, new_range) 
     # Check if we can merge backwards. 
     if offset > 0 and self.ranges[offset - 1].check_merge(new_range): 
      new_range = self.ranges[offset - 1] 
      offset -= 1 
     else: 
      self.ranges.insert(offset, new_range) 
     # Scan for forward merges. 
     check_offset = offset + 1 
     while (check_offset < len(self.ranges) and 
       new_range.check_merge(self.ranges[offset+1])): 
      check_offset += 1 
     # Remove any entries that we've just merged. 
     if check_offset - offset > 1: 
      self.ranges[offset+1:check_offset] = [] 

Answer 3

您已经在您的示例用例中找到了一个很好的解决方案。与其尝试维护已使用的一组范围，请跟踪尚未使用的范围。这使问题变得非常简单。

class RangeSet: 
    def __init__(self, min, max): 
     self.__gaps = [(min, max)] 
     self.min = min 
     self.max = max 

    def add(self, lo, hi): 
     new_gaps = [] 
     for g in self.__gaps: 
      for ng in (g[0],min(g[1],lo)),(max(g[0],hi),g[1]): 
       if ng[1] > ng[0]: new_gaps.append(ng) 
     self.__gaps = new_gaps 

    def missing_ranges(self): 
     return self.__gaps 

    def ranges(self): 
     i = iter([self.min] + [x for y in self.__gaps for x in y] + [self.max]) 
     return [(x,y) for x,y in zip(i,i) if y > x] 

神奇的是在add方法，该方法检查每个现有的差距，看它是否被新的范围的影响，并相应地调整间隙的列表。

请注意，此处用于范围的元组的行为与Python的range对象相同，即它们包含start值，并且不包括stop值。这个班级将而不是的行为方式与您在问题中所描述的方式完全相同，您的范围似乎包含两者。

Answer 4

另一种方法是基于sympy.sets。

>>> import sympy as sym 
>>> a = sym.Interval(1, 2, left_open=False, right_open=False) 
>>> b = sym.Interval(3, 4, left_open=False, right_open=False) 
>>> domain = sym.Interval(0, 10, left_open=False, right_open=False) 
>>> missing = domain - a - b 
>>> missing 
[0, 1) U (2, 3) U (4, 10] 
>>> 2 in missing 
False 
>>> missing.complement(domain) 
[1, 2] U [3, 4]