[Jprogramming] largest rectangle problem

Martin Kreuzer info at airkreuzer.com
Mon Jul 3 09:04:25 UTC 2017 

Sorry, that citation "(b) saves an extra multiply 
..." obviously stems from one of Mike Day's posts.
-M

At 2017-07-03 08:28, you wrote:

>"Anyways, faster is not always better..."
>Agreed :)
>
>N: nice test data to clarify your point (using 
>qq=: 1e3?.1e6 produced no differing results, so did not alert me).
>Larger is not always better ...
>
>Seems that I missed the change in the definition 
>of (q) in one stage of the program's 
>development, to which this remark (from one of your previous posts) refers
>"(b) saves an extra multiply in the comparison 
>by using the maximum before scaling by i,"
>which implies a modified break-off condition
>and which I came to understand completely only just now.
>
>Thanks for your help.
>-M
>
>At 2017-07-03 06:59, you wrote:
>
>>Note that in cs1 m is defined as i * >./y so effectively in "lrds" you
>>have a factor of i^2
>
>>Thus:
>
>>   N=: 1 1 4 8 3 3 2 5 4 7
>>    lrds N
>>12
>>    cs1 N
>>16
>
>>Anyways, faster is not always better...
>
>>Thanks,
>
>>--
>>Raul
>
>>On Mon, Jul 3, 2017 at 2:25 AM, Martin Kreuzer <info at airkreuzer.com> wrote:
>> > Mike -
>
>> > Somewhere during the discussion, from "finalrev" an "i" somehow silently
>> > slipped away ...
>
>> > On my machine (P4 3 GHz 4 GB ) I got
>
>> > * using the (more conservative) break-off condition m >: q * n
>
>> >    (timex 'lrds qq') , (memex 'lrds qq')
>> > 0.00452488 14912
>
>> > * re-introducing the (more stringent) condition (m * i) >: (q * n)
>
>> >    (timex 'lrds qq') , (memex 'lrds qq')
>> > 0.000540292 14912
>
>> > which is about one more factor 10 in speed-up.
>
>> > (btw, 'lrds' is my abbrev for 'largest rectangle in data set'.)
>
>> > This is the code I used in testing:
>
>> > lrds=: 3 : 0                                   NB. Joint effort of RM, MD,
>> > LdF (final rev)
>> >  m=. >./ 
>> y                                     NB. initialize m with max(y),
>> > i.e. rectangle with base length 1
>> >  for_j. 2 + i. <: n=. # y do.                  NB. looping from j= 2 to n
>> > (total number of bars, const)
>> >   m=. m >. j * q=. >./ y=. 2 <./\ y            NB. q: max of running min
>> > between elements (x=2) of y
>> >   if. (m * j) >: (q * n) do. return. end.      NB. skipping unnecessary
>> > tests
>> >  end.
>> > )
>
>> > -M
>
>
>> > At 2017-06-25 16:55, you wrote:
>
>> >> Thanks.   That's a bit strange.  I'd spotted the same thing - that we
>> >> could
>> >> need only take the minimum of each pair of elements provided we replaced
>> >> the input array with the new set of 
>> minima.  But it appeared to be slower,
>> >> and I thought enough was enough, tweaking-wise!
>> >>
>> >> Also,  Raul & Henry commented later on the 
>> superfluous result line,  "m" ,
>> >> at
>> >> the end of my previous best offering,  and as in Louis' revised version,
>> >> below.
>> >> I'd only added that line when introducing the early stopping break,
>> >> assuming
>> >> that m wouldn't be available. I should have checked!
>> >>
>> >> So - here's a final (?) revised version,  which
>> >> (a) uses the rolling replacement of y a la Louis,
>> >> (b) saves an extra multiply in the comparison by using the maximum
>> >> before scaling by i,
>> >> and c) dispenses with the result line, a la Raul:
>> >>
>> >> finalrev =: 3 : 0    NB.  good name?
>> >>
>> >> m =. >./y
>> >>
>> >> for_i. }.>:i.n =. #y do.
>> >>
>> >> m =. m >. i * q =. >./ y =. 2 <./\ y
>> >>
>> >> if. m >: q * n do. break. end.
>> >>
>> >> end.
>> >>
>> >>
>> >>
>> >>
>> >>     1000 ts'finalrev qq'
>> >>
>> >> 0.00353084 29696
>> >>
>> >>     1000 ts'cs1 qq'    NB. !!! dead-heat !!!
>> >>
>> >> 0.00357644 29440
>> >>
>> >>
>> >> Enough?
>> >>
>> >> Mike
>> >>
>> >>
>> >>
>> >> On 25/06/2017 14:10, Louis de Forcrand wrote:
>> >>>
>> >>> Here is Mike’s version with 2<./\ 
>> insenserted (and >./i* replaced by i*>./
>> >>> since
>> >>> i is positive):
>> >>
>> >>
>> >>> cs1=: 3 : 0
>> >>>   m=. >./y
>> >>>   for_i. }.>:i.n=. #y do.
>> >>>    m=. m>.q=. i*>./y=. 2<./\y
>> >>>    if. (m*i)>:n*q do. break. end.
>> >>>   end.
>> >>>   m
>> >>> )
>> >>
>> >>
>> >>>     1e3 ts'cs1 qq'
>> >>> 0.00107603 29440
>> >>>     qqq=: 1e4?.1e6
>> >>>     ts'cs1 qqq'
>> >>> 0.045429 398080
>> >>>     ts'cs qqq'
>> >>> 0.180366 397440
>> >>
>> >>
>> >>> Real fast!
>> >>> Louis
>> >>
>> >>
>> >>>> On 25 Jun 2017, at 14:47, Louis de Forcrand <olius at bluewin.ch> wrote:
>> >>>>
>> >>>> Let V be a vector of real numbers, and V[i] its ith component.
>> >>>> Then
>> >>>>
>> >>>> min( V[i] Â
 V[j+1]] ) = min( min( V[i] 
>> â… V[j] ), min( V[i+1] Â
 V[j+1] )
>> >>>> ) ).
>> >>>>
>> >>>>
>> >>>>> This version is based on that:
>> >>>>
>> >>>>    ms=: #\ >./ . * [: >./@> # 2&(<./\&.>)&< ]
>> >>>>    1e3 ts 'ms qq'
>> >>>> 0.00491435 5.74234e6
>> >>>>
>> >>>> Incorporating this in Mike's explicit version with an early stopping
>> >>>> condition
>> >>>> could lead to even faster runtimes!
>> >>>>
>> >>>> Cheers,
>> >>>> Louis
>> >>>>
>> >>>>> On 25 Jun 2017, at 11:00, 'Mike Day' via Programming
>> >>>>> <programming at jsoftware.com> wrote:
>> >>>>>
>> >>>>> There must be something about breakfast.
>> >>>>> A loopy stopping condition has just 
>> presented itself.  Others might see
>> >>>>> a tacitisation:
>> >>>>>
>> >>>>> cs =: 3 : 0
>> >>>>>
>> >>>>> m =. >./y
>> >>>>>
>> >>>>> for_i. }.>:i.n =. #y do.
>> >>>>>
>> >>>>> m =. m >. q =. >./ i ([ * <./\) y
>> >>>>>
>> >>>>> if. (m * i) >: n * q do. break. end.
>> >>>>>
>> >>>>> end.
>> >>>>>
>> >>>>> m
>> >>>>>
>> >>>>> )
>> >>>>>
>> >>>>> q holds the maximum area at "width" i . No subsequent area
>> >>>>>
>> >>>>> can be greater than q*n%i where n is the maximum width, so
>> >>>>>
>> >>>>> stop if that is no greater than the current maximum, m.
>> >>>>>
>> >>>>> It's twice as fast and uses slightly less space than c, the loopy verb
>> >>>>>
>> >>>>> without an early stopping condition:
>> >>>>>
>> >>>>> ts'c qq'
>> >>>>>
>> >>>>> 0.014258 21632
>> >>>>>
>> >>>>> ts'cs qq'
>> >>>>>
>> >>>>> 0.0044897 21504
>> >>>>>
>> >>>>> ts'C qq' NB. Raul's best tacit version - so far...
>> >>>>>
>> >>>>> 0.00803071 289920
>> >>>>>
>> >>>>> Now for lunch,
>> >>>>>
>> >>>>> Mike
>> >>>>>
>> >>>>>
>> >>>>> On 24/06/2017 20:09, Raul Miller wrote:
>> >>>>>>
>> >>>>>> True, except that if you did not have 
>> the inner >./ the "0 1 would not
>> >>>>>> help.
>> >>>>>>
>> >>>>>> Thanks,
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>> ---
>> >>>>> This email has been checked for viruses by Avast antivirus software.
>> >>>>> https://www.avast.com/antivirus
>> >>>>> ----------------------------------------------------------------------
>> >>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>> >>>>
>> >>>> ----------------------------------------------------------------------
>> >>>> For information about J forums see http://www.jsoftware.com/forums.htm
>> >>>
>> >>> ----------------------------------------------------------------------
>> >>> For information about J forums see http://www.jsoftware.com/forums.htm
>> >>
>> >>
>> >> ----------------------------------------------------------------------
>> >> For information about J forums see http://www.jsoftware.com/forums.htm
>
>> > ----------------------------------------------------------------------
>> > For information about J forums see http://www.jsoftware.com/forums.htm
>>----------------------------------------------------------------------
>>For information about J forums see http://www.jsoftware.com/forums.htm
>
>----------------------------------------------------------------------
>For information about J forums see http://www.jsoftware.com/forums.htm

More information about the Programming mailing list