Re: Number of interval Intersections for a large number
- To: mathgroup at smc.vnet.net
- Subject: [mg81727] Re: [mg81679] Number of interval Intersections for a large number
- From: Carl Woll <carlw at wolfram.com>
- Date: Tue, 2 Oct 2007 05:40:48 -0400 (EDT)
- References: <148249.53339.qm@web26014.mail.ukl.yahoo.com>
Peter van Summeren wrote:
> Hello Carl,
> in my first attempt the intervals are integers. In a second attempt
> they will be real.
Ok, here is one attempt:
stacked[intervals_, tall_] := Module[{pts, ord, ends, pos},
pts = Flatten[intervals];
ord = Ordering[pts];
ends = Riffle[ConstantArray[1, Length[intervals]],
ConstantArray[-1, Length[intervals]]][[ord]];
pos = Flatten@Position[Accumulate[ends], tall, 1];
{pts[[ord[[pos]]]], pts[[ord[[pos + 1]]]]} // Transpose
]
Here is some random data:
SeedRandom[1];
len = 1000;
max = 1200;
left = RandomReal[max, len];
right = Clip[left + RandomReal[max/100, len], {0, max}];
inputintervals = Transpose[{left, right}];
Here is a query for the intervals that are stacked 12 high:
In[352]:= stacked[inputintervals, 12] // Timing
Out[352]= {0., {{21.4082, 21.528}, {22.8809, 23.4344}, {23.5234,
23.8432}, {53.8756, 53.8975}, {384.889, 385.702}, {385.909,
386.037}, {386.733, 386.802}, {402.722, 402.889}, {403.136,
403.445}, {404.061, 404.353}, {404.626, 404.642}, {716.699,
716.814}, {716.896, 717.495}, {717.986, 718.264}, {718.383,
718.843}, {773.912, 774.066}, {775.314, 775.347}, {775.375,
776.492}, {776.529, 776.595}, {811.171, 811.284}, {811.761,
812.34}, {812.477, 812.494}, {812.761, 813.322}, {921.788,
921.887}, {921.957, 923.916}, {952.247, 952.261}}}
As you can see, the time taken is 0, so hopefully this is fast enough
for you :)
Carl
[snip]
>
>
> ----- Original Message ----
> From: Carl Woll <carlw at wolfram.com>
> To: Peter van Summeren <peter_van_summeren at yahoo.co.uk>
> Sent: Monday, 1 October, 2007 6:02:01 PM
> Subject: Re: [mg81679] Number of interval Intersections for a large
> number of intervals
>
> Peter van Summeren wrote:
>
> > Hello Carl,
> > thanks for mailing me, although you do not understand.
> > I have a few thousand intervals {e1,e2,...} each of which is like
> > {begin,end}
> > The elements e are ordered according to their begin value.
> > Some intervals do not intersect. But it also can be like this:
> > <------>
> > <------------------->
> > <------------------>
> > So, in this case the first interval can be partioned :
> > in a part which has no intersection with the other two,
> > in a part which intersects twice,
> > in a part which intersects three times,
> > in a part which intersects two times.
> > For each interval I make a Block[x] =
> > UnitStep[x-beginvalue]-UnitStep[x-endvalue]
> > I sum all the Blocks to one function and ask Reduce to find me a
> > solution for those parts which intersects three times:
> > Reduce[SumOfBlocks[x]==3,x]
> > Because it is a sum of UnitSteps and where there are three times an
> > intersection, the value is 3.
> > And so on for 1,2,4,5,etc.
>
> I agree that using Reduce here will be slow. However, before attempting
> to speed up the determination of the list of intervals of height 3, what
> will you do with this list of intervals? Also, are the interval
> endpoints integers or real numbers?
>
> Carl
>
> > It is a safe way to do it, but not so fast. Are there other
> > algorithms? Where can I find them?
> > I hope my questions are now clear. I am still learning to formulate my
> > questions in a way that I can use functions in Mathematica which solve
> > them. Sometimes the solutions from people take me to possibilities I
> > never dreamed of. I relearn math.
> > with friendly greetings,
> > Peter
> >
> > ----- Original Message ----
> > From: Carl Woll <carlw at wolfram.com>
> > To: P_ter <peter_van_summeren at yahoo.co.uk>
> > Sent: Monday, 1 October, 2007 4:01:15 PM
> > Subject: Re: [mg81679] Number of interval Intersections for a large
> > number of intervals
> >
> > P_ter wrote:
> >
> > >Hello,
> > >I have as example on the interval [0.0,12000.0] thousands of smaller
> > intervals which overlap. I construct for each interval a UnitStep up
> > and one down(a block). I order and sum them and I give it to Reduce
> > with the question Reduce[SumOfAllBlocks[x]==<number>,x]. The result
> > gives me the overlapping intervals which overlap <number>. From the
> > result I take out the length of the overlaps and Tally them. It is
> > safe, but slow.
> > >Does anyone know something about this type of problems? With better
> > algorithms?
> > >
> > >
> > A bit of working code would go a long way towards helping me understand
> > what you are trying to do. As it is, I can't figure out what you did,
> > nor what you want to achieve.
> >
> > Carl
> >
> >
> > ------------------------------------------------------------------------
> > Yahoo! Answers - Get better answers from someone who knows. Try it now
> >
> <http://uk.answers.yahoo.com/;_ylc=X3oDMTEydmViNG02BF9TAzIxMTQ3MTcxOTAEc2VjA21haWwEc2xrA3RhZ2xpbmU>.
>
>
> ------------------------------------------------------------------------
> For ideas on reducing your carbon footprint visit Yahoo! For Good
> <http://uk.promotions.yahoo.com/forgood/environment.html> this month.