Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: searching a vector array

by Grimy (Monk)
on Jun 09, 2011 at 17:17 UTC ( #908961=note: print w/ replies, xml ) Need Help??


in reply to searching a vector array

If there's many more numbers than intervals, iterating over the number is indeed a bad idea. But if I understand your demand correctly, the desired can be achieved by iterating over intervals (or rather, over their min and max values: 2..5 and 4..7 is the same as 2..7 and 4..5 regarding coverage).

So you would have to create two arrays (e.g. @min and @max) holding respectively the lower and higher bounds of all intervals. Then:

my $count = 0; foreach $min (@min) { $count++ if ($_[0] >= $min) } foreach $max (@max) { $count-- if ($_[0] > $max) } return $count;
Would give the coverage of $_[0]. Of course, it can be optimized further by sorting @min and @max beforehand and using dichotomy, which would get you an O(ln(X)).


Comment on Re: searching a vector array
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://908961]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (9)
As of 2014-08-01 23:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Who would be the most fun to work for?















    Results (52 votes), past polls