Re: checking for overlap
- To: mathgroup at smc.vnet.net
- Subject: [mg20098] Re: [mg20065] checking for overlap
- From: "David Park" <djmp at earthlink.net>
- Date: Thu, 30 Sep 1999 02:43:10 -0400
- Sender: owner-wri-mathgroup at wolfram.com
>I am looking for an elegant way of checking for overlap.
>
>Suppose I have a set of time intervals given by
>ints = {{t1,t2},{t3,t4},{t5,t6}. ...} and another set of times
>tvals = {u1,u2,u3, ...}.
> What is a fast, elegant way of checking which of the tvals is within any of
>the ints time intervals?
>
>Thanks,
>Dennis
>
>
Dennis,
Perhaps I should know better than to touch these kinds of problems, but here is my
try. You will probably get some better methods from the real mathematicians in
MathGroup.
Here is a test case.
ints = Table[{2n, 2n + 1}, {n, 0, 4}];
Create ints2 by applying Interval to ints.
ints2 = Interval @@ ints
Interval[{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}]
Here is a random set of tvals.
tvals = Table[Random[Real, {0, 10}], {10}]
{7.28844, 7.97387, 1.4635, 8.27075, 4.35604, 0.938894, 6.27754, 3.95451, 4.18765,
3.76676}
It is not clear whether you just want True or False answers for each value, want a
list of the positions, or want to select out the values. This selects the values that
lie in the intervals.
Select[tvals, IntervalMemberQ[ints2, #] &]
{8.27075, 4.35604, 0.938894, 6.27754, 4.18765}
Here is the timing for a longer case on a 166 Mh Pentium. 100 values with 50
intervals.
ints2 = Interval @@ Table[{2n, 2n + 1}, {n, 0, 49}];
tvals = Table[Random[Real, {0, 100}], {1000}];
Select[tvals, IntervalMemberQ[ints2, #] &]; // Timing
{1.32 Second, Null}
The timing appears to be linear with the number of tvals and the number of intervals.
David Park
djmp at earthlink.net
http://home.earthlink.net/~djmp/