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
