Not quite, I have a few trivial tweaks that I think make reading it a
bit easier.
(1) I used "Paste and match style" rather than simply paste, when
inserting the code into my message, to eliminate the blank lines that
some insane programming teams decided should be inserted when using
paste.
(2) I indented the code to reflect the explicit structures.
(3) I commuted a multiplication to better show similarity with a
multiplication on the line above.
(4) I ate the whitespace to the left of copulas, because copulas are special.
These are, granted, issues of taste, which means there will always be
someone with different views. They do not help0 performance nor reduce
resource costs in any way. Nevertheless, these reflect my views.
And, (5) a nearly invisible performance improvement (eliminate one
operation) when setting up the loop.
Now... if I could just get my mailer to display messages using a fixed
width font...
finalrev=: 3 : 0 NB. good name?
m=. >./y
for_i. 2+i.<:n=. #y do.
m=. m >. i * q=. >./ y =. 2 <./\ y
if. m >: n * q do. break. end.
end.
)
I am not certain though if my (5) hurts readability, but for code like
this you sort of need to go in and see the data to really understand
it. So, here's an instrumented version - I would recommend only trying
this on small arguments (and the displayed result is meant to be used
to help understand the uninstrumented version):
show=: 1 {:: 1!:2&2@(] :(,~))
showfinalrev=: 3 : 0
show 'y';y
show 'm';m=. >./y
for_i. 2+i.<: show 'n';n=. #y do.
('q';q;'y';y) show 'm';m=. m >. i * q=. >./ y =. 2 <./\ y
if. show 'break';m >: n * q do. break. end.
end.
)
That said, thank you for the excellent treatment of this problem. You
took this a lot further than I had.
Thanks,
--
Raul
On Sun, Jun 25, 2017 at 12:55 PM, 'Mike Day' via Programming
<[email protected]> 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
