Re: Re: Number of interval Intersections for a large number
- To: mathgroup at smc.vnet.net
- Subject: [mg81771] Re: [mg81727] Re: [mg81679] Number of interval Intersections for a large number
- From: DrMajorBob <drmajorbob at bigfoot.com>
- Date: Wed, 3 Oct 2007 02:31:27 -0400 (EDT)
- References: <148249.53339.qm@web26014.mail.ukl.yahoo.com> <6555522.1191331695608.JavaMail.root@m35>
- Reply-to: drmajorbob at bigfoot.com
My solution plotted counts for all x in the range, rather than returning
intervals with a single given count, and the Timings I posted measured
Plot time (including Interpolation evaluations), but left out the effort
required in creating the Interpolation function. (My bad!)
If the Plot (or something like that) is wanted, here's a modification to
Carl's method that does it:
stacked[intervals_] := Module[{pts = Flatten@intervals, ord, ends},
ord = Ordering@pts;
ends = Riffle[ConstantArray[1.0, Length[intervals]],
ConstantArray[-1.0, Length[intervals]]][[ord]];
Interpolation[Transpose@{pts[[ord]], Accumulate@ends},
InterpolationOrder -> 0]]
Timing[count3 = stacked@intervals;]
Plot[count3@x, {x, Min@intervals, Max@intervals}]
This uses packed arrays only. Using integers in ConstantArray takes 60%
more time, probably because Transpose results in an unpacked array. I
think packed arrays have much to do with the "zero time" speed of Carl's
original function, as well, since pts, ord, ends, pos, and the final
result are all packed arrays.
The "stacked" function above isn't noticeably faster than my earlier
solution, BTW, but Carl UNDOUBTEDLY could think of a huge improvement if
he cared to.
Bobby
On Tue, 02 Oct 2007 04:40:48 -0500, Carl Woll <carlw at wolfram.com> wrote:
> 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.
>
>
>
>
>
--
DrMajorBob at bigfoot.com