Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Discard if present within other coordinate range

by jnarayan81 (Sexton)
on Feb 17, 2017 at 22:36 UTC ( #1182245=perlquestion: print w/replies, xml ) Need Help??

jnarayan81 has asked for the wisdom of the Perl Monks concerning the following question:

I need a solution for following computing problem for millions of ids. I have list of followings ids (sample)

SEQ1 225 275 SEQ1 200 300 SEQ1 201 299 SEQ1 250 399 SEQ1 145 244 SEQ2 120 130 SEQ2 100 150 SEQ2 101 149 SEQ2 120 230 SEQ2 99 140

I want to remove/discard those ids-range which completely fall within others range, and keep the rest.

In other word, it should print the following ids

SEQ1 200 300 SEQ1 250 399 SEQ1 145 244 SEQ2 100 150 SEQ2 120 230 SEQ2 99 140

Replies are listed 'Best First'.
Re: Discard if present within other coordinate range
by kennethk (Abbot) on Feb 17, 2017 at 22:58 UTC
    What have you tried? What worked? What didn't? See How do I post a question effectively? In your previous posts, you've always put up code.

    Does order in the output matter? The easiest solution I can see would be to sort your entries first by the first number ascending, and then by the second number descending. You can then cycle through the list, and any time the current second number is less than the biggest one you've seen so far, you know you've gotten a subset.

    #!/usr/bin/perl use strict; use warnings; use 5.10.0; my @terms; while (<DATA>) { chomp; push @terms, [split /\s+/]; } my $biggest = 0; for my $term (sort sorter @terms) { if ($term->[2] > $biggest) { say join ' ', @$term; $biggest = $term->[2]; } } sub sorter { $a->[1] <=> $b->[1] || $b->[2] <=> $a->[2] } __DATA__ SEQ1 225 275 SEQ1 200 300 SEQ1 201 299 SEQ1 250 399 SEQ1 145 244 SEQ2 120 130 SEQ2 100 150 SEQ2 101 149 SEQ2 120 230 SEQ2 99 140

    #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

      I had a different take (that makes minor changes to your solution). I thought he wanted non-subsets within each seq identifier, (where your solution finds them for the whole file not considering the first column).

      I added 2 more lines to the for loop and 1 more line to the sorter sub.

      #!/usr/bin/perl use strict; use warnings; use 5.010; open my $fh, '<', \<<EOF; SEQ1 225 275 SEQ1 200 300 SEQ1 201 299 SEQ1 250 399 SEQ1 145 244 SEQ2 120 130 SEQ2 100 150 SEQ2 101 149 SEQ2 120 230 SEQ2 99 140 EOF my @terms; while (<$fh>) { chomp; push @terms, [split /\s+/]; } my $biggest = 0; my $id = ''; for my $term (sort sorter @terms) { $biggest = 0 if $id ne $term->[0]; if ($term->[2] > $biggest) { say join ' ', @$term; $biggest = $term->[2]; } $id = $term->[0]; } sub sorter { $a->[0] cmp $b->[0] || $a->[1] <=> $b->[1] || $b->[2] <=> $a->[2] }
      The output is:
      SEQ1 145 244 SEQ1 200 300 SEQ1 250 399 SEQ2 99 140 SEQ2 100 150 SEQ2 120 230
Re: Discard if present within other coordinate range
by BrowserUk (Patriarch) on Feb 17, 2017 at 23:45 UTC
    I need a solution for following computing problem for millions of ids.

    There are a few very efficient O(1) solutions to this problem. Which is appropriate depends upon the scale of various parts of the problem. Ie.

    1. How many millions of ids?
    2. What is the maximum value of the range integers?

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Eg. Assuming that you have upto a few hundred million IDs (and enough memory to accommodate 4 bytes per ID), and that the input file is already sorted by range (as I believe is typical for this type of data; if not sort it it first using your system sort utility):

      #! perl -slw use strict; my @ids; my $tally = chr(0); while( my( $id, $start, $end ) = split ' ', <DATA> ) { my $startId = vec( $tally, $start, 32 ); my $endId = vec( $tally, $end, 32 ); next if $startId and $endId and $startId == $endId; push @ids, $id; my $idn = @ids; vec( $tally, $_, 32 ) = $idn for $start .. $end; print "$id $start $end"; } __DATA__ SEQ2 99 140 SEQ2 100 150 SEQ2 101 149 SEQ2 120 130 SEQ2 120 230 SEQ1 145 244 SEQ1 200 300 SEQ1 201 299 SEQ1 225 275 SEQ1 250 399

      Output:

      C:\test>1182245.pl SEQ2 99 140 SEQ2 100 150 SEQ2 120 230 SEQ1 145 244 SEQ1 200 300 SEQ1 250 399

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
      In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Discard if present within other coordinate range
by Cow1337killr (Monk) on Feb 18, 2017 at 00:05 UTC

    Can you please make it very clear?

    The ids (e.g., SEQ1, SEQ2) are not involved in the problem other than that they are along for the ride, i.e., they are input into the program and they get printed in the output.

    So, if one has 1,000 lines of input data, line 1,000 must be compared against whatever ranges are remaining after the elimination process.

      Yes, we only need to keep the correct name in long run.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1182245]
Approved by beech
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (1)
As of 2022-11-26 19:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?