How can I Identifi the position between Star_posi and end_posi

Question

biojet 0 Junior Poster in Training

15 Years Ago

Hi everyone,

Coul you please help me to find the position between Star_poso and end_posi.

I have two data

Data 1:

Num Posi
1 2
2 5
3 9
4 16
5 19
.. ..
Data 2:

Num Star_posi End_posi
1 1 10
2 15 18
3 26 30
.. ... ...

I want to identifi Data 1 contain in Data 2 or not?
I make the script with perl in below but I just only sort with the Sta_posi. I hope I can check Data 1 between Star_posi and end _posi.
I would appreciate if you could give some pointers.

(Toggle Plain Text)

#1 #!/usr/bin/perl -w
use strict;
use warnings;
use Data::Dump qw(dump);

#Sort the position**************

my (@posi1, $Num2, @Num2, @Num1);
open(POS1,"<posi.txt");
@posi1=<POS1>;
@Num1=@posi1;
open(LIST,">list.txt"); {
@Num2= sort {$a <=> $b} @Num1;
$Num2 = join( '', @Num2);
print $Num2;
print LIST $Num2."\n";
}
close(LIST);

data-structure perl

2 Contributors
8 Replies
402 Views
3 Days Discussion Span
Latest Post 15 Years Ago Latest Post by d5e5

Dani AI

Generated 9 Months Ago

As already showed, the core task is mapping each position from one file to a start–end interval in the other file. The notes below add practical, durable improvements: deterministic matching order, much better performance for large files, and handling of edge cases that rarely get tested (overlaps, non-numeric rows, inclusive/exclusive bounds, and proper file cleanup).

Common gaps to watch for

Iterating a hash for the “first” match gives non-deterministic results; sort ranges when the order matters.
Overlapping ranges: decide whether you want the first match, all matches, or merged ranges. If ranges overlap and you need every match, return all candidates; if you want a single canonical match, sort and choose by rule (e.g., smallest start).
Input robustness: skip headers/comments, trim whitespace, validate numbers, and force numeric context (e.g., +0). Always close output handles.

Faster, deterministic approach (sort + binary search)

Read ranges into an array of [start,end,id], sort by start.
For each position, binary-search the array for the rightmost range whose start <= pos; then check pos <= end.
Complexity: O(M log M) to sort M ranges, then O(N log M) for N lookups (much faster than O(N*M) linear scans).

Example sketch (Perl) — sorts ranges and uses a binary search helper:

# build sorted ranges
my @ranges;
open my $rh, '<', 'ranges.txt' or die $!;
while (my $ln = <$rh>) {
  next if $ln =~ /^\s*(?:Num|#|\s*$)/;        # skip headers/comments/blank
  my ($id,$s,$e) = split /\s+/, $ln;
  next unless defined $e && $s =~ /^-?\d+$/ && $e =~ /^-?\d+$/;
  push @ranges, [$s+0, $e+0, $id];
}
@ranges = sort { $a->[0] <=> $b->[0] } @ranges;
close $rh;

# binary-search helper returns index of rightmost range with start <= $pos
sub bsearch_rightmost {
  my ($arr, $pos) = @_;
  my ($l,$r,$res) = (0, $#$arr, -1);
  while ($l <= $r) {
    my $m = int(($l+$r)/2);
    if ($arr->[$m][0] <= $pos) { $res = $m; $l = $m + 1; }
    else { $r = $m - 1; }
  }
  return $res;
}

Final notes

If ranges overlap and you need every containing range, scan left/right from the binary-search hit until starts are too small or ends fail.
For very large or frequent queries, use an interval-tree implementation (CPAN) to get optimal query speed.
Test with edge cases: exact boundary values, negative numbers (if applicable), duplicated ranges, and malformed lines.

All 8 Replies

d5e5 109 Master Poster

15 Years Ago

#!/usr/bin/perl;
use strict;
use warnings;

my $filename1 = 'Data_1.txt';
my $filename2 = 'Data_2.txt';
my %ranges;

open my $fh, '<', $filename2 or die "Failed to open $filename2: $!";
while (<$fh>){
    next unless m/^\d/; #skip unless line starts with number
    chomp;
    my ($num, $start, $end) = split;
    $ranges{$num}{Star_posi} = $start;
    $ranges{$num}{End_posi} = $end;
}
close $fh;

open $fh, '<', $filename1 or die "Failed to open $filename1: $!";
while (<$fh>){
    next unless m/^\d/; #skip unless line starts with number
    chomp;
    my ($num, $posi) = split;
    my $range_num = search_ranges($posi);
    if ($range_num){
        print "Data1 record number $num found in Data2 record number $range_num\n";
    }
    else{
        print "Data1 record number $num not found in Data2\n";
    }
}

sub search_ranges{
    my $pos = shift;
    foreach (keys %ranges){
        return $_ if $pos >= $ranges{$_}{Star_posi}
                    and $pos <= $ranges{$_}{End_posi};
    }
}

Outputs:

Data1 record number 1 found in Data2 record number 1
Data1 record number 2 found in Data2 record number 1
Data1 record number 3 found in Data2 record number 1
Data1 record number 4 found in Data2 record number 2
Data1 record number 5 not found in Data2

d5e5 109 Master Poster

15 Years Ago

Data_1.txt

Num Posi
1 2
2 5
3 4

Data_2.txt

Num Star_posi End_posi
1 1 10
2 15 18
3 26 30

#!/usr/bin/perl;
use strict;
use warnings;

my $filename1 = 'Data_1.txt';
my $filename2 = 'Data_2.txt';
my $filename3 = 'output.txt';
my %ranges;

open my $fh, '<', $filename2 or die "Failed to open $filename2: $!";
while (<$fh>){
    next unless m/^\d/; #skip unless line starts with number
    chomp;
    my ($num, $start, $end) = split;
    $ranges{$num}{Star_posi} = $start;
    $ranges{$num}{End_posi} = $end;
}
close $fh;

open $fh, '<', $filename1 or die "Failed to open $filename1: $!";
open my $fho, '>', $filename3 or die "Failed to open $filename3: $!";#Open file for output
while (<$fh>){
    next unless m/^\d/; #skip unless line starts with number
    chomp;
    my ($num, $posi) = split;
    my $range_num = search_ranges($posi);
    if ($range_num){
        #print to output file instead of STDOUT
        print $fho "Data1 record number $num found "
            . "at position $posi found in $ranges{$range_num}{Star_posi} "
            . "and $ranges{$range_num}{End_posi} \n";
    }
    else{
        print "Data1 record number $num not found in Data2\n";
    }
}

sub search_ranges{
    my $pos = shift;
    foreach (keys %ranges){
        return $_ if $pos >= $ranges{$_}{Star_posi}
                    and $pos <= $ranges{$_}{End_posi};
    }
}

output.txt

Data1 record number 1 found at position 2 found in 1 and 10 
Data1 record number 2 found at position 5 found in 1 and 10 
Data1 record number 3 found at position 4 found in 1 and 10

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

biojet 0 Junior Poster in Training · Answer 1 · 2011-08-26T07:06:27+00:00

thank you very much.
If I want to out put [At Posi (1) contained star_posi (1) and end Posi (10)], how can I do that.
How can I save the data result at the txt file.
could you please show me.

biojet 0 Junior Poster in Training · Answer 2 · 2011-08-26T11:22:44+00:00

thank you very much.
If I want to out put [At Posi (1) contained star_posi (1) and end Posi (10)], how can I do that.
How can I save the data result at the txt file.
could you please show me.

sorry I prepared the Print code in below.

print "at position  $posi found in $ranges{$num}{Star_posi} and $ranges{$num}{End_posi} \n";

But I have one problem. EX:

Data 1:                  Data2: 
      Num   Posi           Num    star      end
       1     2              1      1         10
       2     5              2      15        18
       3     4              3      26        30

How coould I find Num (3) posi (4) between 1 and 10?

d5e5 109 Master Poster · Answer 3 · 2011-08-26T21:23:00+00:00

sorry I prepared the Print code in below.

print "at position  $posi found in $ranges{$num}{Star_posi} and $ranges{$num}{End_posi} \n";

But I have one problem. EX:

Data 1:                  Data2: 
      Num   Posi           Num    star      end
       1     2              1      1         10
       2     5              2      15        18
       3     4              3      26        30

How coould I find Num (3) posi (4) between 1 and 10?

I'm confused by your second example. It looks like your two data sets are side by side in one input file. Is that correct? I assumed from reading your original question that you had two separate input files.

biojet 0 Junior Poster in Training · Answer 4 · 2011-08-26T21:30:56+00:00

sorry d5e5. I have a mistake at the first EX when I check it again. I hope to find the position contain between Star_posi and end_posi. It mean at the posi (a) of data 1 contained between (A) Star_posi and (B) end_posi data 2.And with that result out put in the Txt.file. Could you show me how to do that.
Thank you so much.

biojet 0 Junior Poster in Training · Answer 5 · 2011-08-27T20:23:18+00:00

biojet 0 Junior Poster in Training

15 Years Ago

thank you much.

d5e5 109 Master Poster · Answer 6 · 2011-08-27T21:41:05+00:00

You are welcome. Please don't forget to mark this thread 'solved'.

How can I Identifi the position between Star_posi and end_posi

Dani AI

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers