Perl快速检查重叠区间？

Question

我正在尝试找到区间的重叠部分。我有一个区间1000到5000（只是举例）。这将在下面给出的区间中进行检查。此脚本确实可以工作，但检查成千上万个区间时非常缓慢。有没有办法使其更快？谢谢。

#!/usr/bin/perl
use warnings;
use strict;
use v5.16;
use List::MoreUtils qw/ any /;

my $start = 1000;
my $end   = 5000;

while ( my $line = <DATA> ) {
    chomp $line;
    my @element = split "\t", $line;
    my @checking_array = "";
    for my $checking_no ( $element[0] .. $element[1] ) {
        push @checking_array, $checking_no;
    }
    for my $value ( $start .. $end ) {
        if ( any { $_ eq $value } @checking_array ) {
            print "$start to $end found in $line\n";
            last;
        }
        else { next }
    }
}

__DATA__
780895  781139
3707570 3707794
13753925    13754168
2409582 2409790
6360880 6361084
8261045 8261250
4133539 4133772
7731897 7732188
8660252 8660539
12156253    12156504
9136875 9137168
16657849    16658107
5000    6000
4133539 4133772
7731897 7732188
8660252 8660539
4999    10000
12156253    12156504
3707570 3707794
13753925    13754168
2409582 2409790
6360880 6361084

输出：

1000 to 5000 found in 5000  6000
1000 to 5000 found in 4999  10000

- SSh

Answer 1

你只需要检查边界，不需要考虑边界之间的数字！！！请与边界相比较。

         S---------E
 L-----H                      No overlap
      L-----H                 Overlap
           L-----H            Overlap
                L-----H       Overlap
                     L----H   No overlap
      L---------------H       Overlap

所以它们重叠，除非H<S或L>E。

while ( my $line = <DATA> ) {
    chomp $line;
    my ($lo, $hi) = split "\t", $line;
    if ( $lo <= $end && $hi >= $start ) {
        print "$start to $end found in $line\n";
    }
}

- ikegami

---

谢谢！太棒了。我在想这是怎么工作的。请给我解释一下。 - SSh

添加了解释 - ikegami

谢谢，我明白了。 - SSh

Answer 2

无需检查 $start 和 $end 之间的每个值；您可以直接比较两个范围的限制。我认为这段代码非常简单明了。

#!/usr/bin/perl

use strict;
use warnings 'all';

my $start = 1000;
my $end   = 5000;

while ( my $line = <DATA> ) {

    my ($low, $high) = split ' ', $line;

    unless ( $high < $start or $low > $end ) {
        chomp $line;
        print qq{$start to $end found in "$line"\n};
    }
}

__DATA__
780895  781139
3707570 3707794
13753925    13754168
2409582 2409790
6360880 6361084
8261045 8261250
4133539 4133772
7731897 7732188
8660252 8660539
12156253    12156504
9136875 9137168
16657849    16658107
5000    6000
4133539 4133772
7731897 7732188
8660252 8660539
4999    10000
12156253    12156504
3707570 3707794
13753925    13754168
2409582 2409790
6360880 6361084

输出

1000 to 5000 found in "5000    6000"
1000 to 5000 found in "4999    10000"

- Borodin

---

抱歉，我无法理解。 - SSh

你不明白什么？ - Borodin

这可能很简单，但我感觉很愚蠢。这里的 unless 如何检查两个区间之间的每个重叠？ - SSh

@SSh：这两个范围是$start到$end和$low到$high。唯一的情况是两者不重叠，即第一个范围的末尾在第二个范围的开头之前，或者第一个范围的开头在第二个范围的末尾之后。在所有其他情况下，两者都会重叠。如果您不喜欢unless，则可以使用if ( not ... )或将表达式反转为if ( $high >= $start and $low <= $end )，但我认为这样做不太直观。它与ikegami的答案相似，但不会进行不必要的比较。 - Borodin