Python间隔相交 [英] Python interval interesction

问题描述

我的问题如下：

具有带有间隔列表的文件：

  1 5 
 2 8 
 9 12 
 20 30 
  

以及$

  0 200 
   
 
 
我想做一个这样的交点，以报告给定范围内我的间隔之间的位置[开始结束]。
 
 
 
例如：
  8 9 
 12 20 
 30200 
  
除了如何咬人的任何想法外，阅读一些关于优化的想法也很不错，因为输入文件一如既往
解决方案
此解决方案有效，只要间隔是按起点排序的，并且不需要创建列表
 
 
 
 code 
 
 
 
 打开（  0.txt），如f：
t = [x.rstrip（ \n）。split（ \t）for f.readlines（）中的x）
 interval = [ （一世nt（x [0]），int（x [1]））x in t] 
 
 def find_ints（intervals，mn，mx）：
 next_start = mn 
对于x间隔：
如果next_start< x [0]：
产生next_start，x [0] 
 next_start = x [1] 
 elif next_start< x [1]：
 next_start = x [1] 
如果next_start< mx：
 yield next_start，mx 
 
打印列表（find_ints（intervals，0，200））
  
 
 
 
输出：
 
 
 
（在您给出的示例中）
  [（0，1），（8，9），（12，20），（30，200）] 
  
 
My problem is as follows:

having file with list of intervals:
1 5
2 8
9 12
20 30
And a range of
0 200
I would like to do such an intersection that will report the positions [start end] between my intervals inside the given range.

For example:
8 9
12 20
30 200
Beside any ideas how to bite this, would be also nice to read some thoughts on optimization, since as always the input files are going to be huge.
解决方案
this solution works as long the intervals are ordered by the start point and does not require to create a list as big as the total range.

code

with open("0.txt") as f:
    t=[x.rstrip("\n").split("\t") for x in f.readlines()]
    intervals=[(int(x[0]),int(x[1])) for x in t]

def find_ints(intervals, mn, mx):
    next_start = mn
    for x in intervals:
        if next_start < x[0]:
            yield next_start,x[0]
            next_start = x[1]
        elif next_start < x[1]:
            next_start = x[1]
    if next_start < mx:
        yield next_start, mx

print list(find_ints(intervals, 0, 200))


output:

(in the case of the example you gave)
[(0, 1), (8, 9), (12, 20), (30, 200)]


                        
这篇关于Python间隔相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！