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 <[email protected]> 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<./\ inserted (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 <[email protected]> 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 >>>>> <[email protected]> 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
