"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 <[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<./\ 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 <[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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
