算法 – 在Perl中确定范围重叠的最快方法

概述我有两套范围.每个范围是一对整数(开始和结束),表示单个较大范围的某个子范围.两组范围的结构与此类似(当然……将被实际数字替换). $a_ranges ={ a_1 => { start => ..., end => ..., }, a_2 => { start => ..., end => ..., }, a_3 => { 我有两套范围.每个范围是一对整数(开始和结束),表示单个较大范围的某个子范围.两组范围的结构与此类似(当然……将被实际数字替换).

$a_ranges ={  a_1 =>  {    start => ...,end   => ...,},a_2 =>  {    start => ...,a_3 =>  {    start => ...,# and so on};$b_ranges ={  b_1 =>  {    start => ...,b_2 =>  {    start => ...,b_3 =>  {    start => ...,# and so on};

我需要确定集合A的哪个范围与集合B的哪个范围重叠.给定两个范围,很容易确定它们是否重叠.我只是使用双循环来执行此 *** 作 – 循环遍历外部循环中集合A中的所有元素,循环遍历内部循环中集合B的所有元素,并跟踪哪些元素重叠.

我对这种方法有两个问题.首先,重叠空间非常稀疏 – 即使每组中有数千个范围,我希望集A中的每个范围与集合B中的1或2个范围重叠.我的方法列举了每一种可能性,即矫枉过正.这导致了我的第二个问题 – 它的扩展非常差.当每组中有数百个范围时,代码很快完成(亚分钟),但是当每组中有数千个范围时,需要很长时间(/ – 30分钟).

有没有更好的方法可以索引这些范围,这样我就不会做那么多不必要的重叠检查？

更新：我正在寻找的输出是两个哈希值(每组范围一个),其中键是范围ID,值是另一组中与该组中给定范围重叠的范围的ID.

解决方法 这听起来像是 interval tree的完美用例,这是一种专门用于支持此 *** 作的数据结构.如果您有两组大小为m和n的区间,那么您可以在时间O(m lg m)中将其中一组构建到区间树中,然后在时间O(n lg mk)中进行n次交叉查询,其中k是您找到的交叉点总数.这给出了O((m n)lg m k)的净运行时间.请记住,在最坏的情况下k = O(nm),所以这并不比你拥有的更好,但是对于交叉点数量稀疏的情况,这可能比你拥有的O(mn)运行时间要好得多现在.

我没有太多使用区间树的经验(在Perl中没有经验,对不起！),但从描述看起来它们似乎不应该那么难建立.如果一个人不存在,我会非常惊讶.

希望这可以帮助！

总结

以上是内存溢出为你收集整理的算法 – 在Perl中确定范围重叠的最快方法全部内容，希望文章能够帮你解决算法 – 在Perl中确定范围重叠的最快方法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。