Aai wrote:
> e.g. is it possible to avoid 'some' boxing.
Oh! Sure.
> HCF=: 1 1,[:(#(2...@#))[:;(,;@(|.@(#;.1)(],~1$~[)&.>
<@:>:;.1)&.>@{:)^:(]`(<@2:))
Let's break this up for easier reading:
HCF0 =: 1 1,[:(#(2...@#))[:;(,;@(|.@(#;.1)(],~1$~[)&.>
<@:>:;.1)&.>@{:)^:(]`(<@2:))
HCF1 =: 1 1 , [: expand tail
expand =: # (2...@#)
tail =: [: ; (, copies&.>@{:)^:powers
copies =: ;@(|.@(#;.1)(],~1$~[)&.> <@:>:;.1)
powers =: ]`(<@2:)
First let's clean up a couple of minor things before we tackle the heart of
the algorithm (copies). With an eye towards the final, fully fixed form,
let's first move that rightmost raze out of tail and into expand:
expand =: (# (2...@#))@:;
tail =: (, copies&.>@{:)^:powers
then let's rewrite HCF1 as:
HCF1 =: 1 1 , expand@:tail
Next, we could take advantage of the general definition of monad I. to write
expand a little more succinctly:
expand =: 2 + I. @:;
This formulation would also allow us to take advantage of any special code
in I.'s implementation [1].
Next, for consistency (of inputs to copies), powers should initialize tail
with a vector, not a scalar:
powers =: ]`(<@,@2:)
Though this change has no impact on the results, in general admitting this
kind of inconsistency can cause trouble and should be avoided [2].
Next, we notice that tail has the form (, f@:{:)^:g, which we can simplify
to f^:(<@:g) (a nice feature of ^:):
powers =: <@:>:`(<@,@2:) NB. Use < to keep intermediate
results
tail =: copies&.>^:powers
Having made these minor changes, we can address the heart of the solution,
copies, and its "boxiness". First, let`s define a utility conj to do "under
right":
un =: conjunction def 'v^:_1@:(u v)'
With that, we can now write:
copies =: >: #!.1 un|.~ 1 j. #;.1 #^:_1 ::1:~ ]~:{.
Note that this new formulation uses expand (#^:_1) and a fitted complex-copy
(# with j.), which allows it to avoid boxes entirely [3] (to eliminate boxes
entirely from the solution would be to implement a different algorithm,
which isn't the object of this message). The wart :: is required because
0 #^:_1: 1 is an error.
Now let's compare & contrast our new verb with the original. First, we need
to collect the final definitions:
un =: conjunction def 'v^:_1@:(u v)'
HCF1 =: 1 1 , exp...@tail
expand =: 2+I.@;
tail =: copies&.>^:powers
copies =: >: #!.1 un|.~ 1 j. #;.1 #^:_1 ::1:~ ]~:{.
powers =: <@>:`(<@,@2:)
Then, to compare it textually/stylistically to the original, we need to
write HCF1 out as a single fully-fixed verb:
NB. Original
HCF0 =: 1 1 , [: (# (2...@#)) [: ; (, ;@(|.@ #;.1 (] ,~
1$~[)&.> <@:>:;.1)&.>@{:)^:(]`(<@2:))
NB. HCF1 fully fixed
HCF1f0 =: 1 1 , 2 + I.@;@((>: #!.1 un|.~ 1 j. #;.1 #^:_1
::1:~ ] ~: {.)&.>^:(<@>:`(<@,@2:)))
NB. Or use [:
HCF1f1 =: 1 1 , 2 + [: I.@; (>: #!.1 un|.~ 1 j. #;.1 #^:_1
::1:~ ] ~: {.)&.>^:(<@>:`(<@,@2:))
Having done that, let's compare the lot for performance:
ways =: HCF0`HCF1`HCF1f0`HCF1f1
assert (-: |.)@:(ways`:0) 20 NB. Identical results
(>ways) ,"1 ' ' ,. '5.2d' 8!:2 (%"1 <./) (6!:2, 7!:2@:])&> ways
,L:0 ' 20'
HCF0 2.28 1.00
HCF1 1.00 1.17
HCF1f0 1.03 1.17
HCF1f1 1.00 1.17
As expected, none of the stylistic changes to HCF1 had an effect. More
surprising is that HCF1 is more than a factor of two faster than the
original; I'm not sure whether that's because we reduced the boxing, or
simply because we used f^:(<@:g) in lieu of (, f@:{:)^:g . It would be
easy to test.
-Dan
[1] Side note: instead of writing 1 1 , (2+I.)@:tail , we could use
overtake,
in the hope that giving the interpreter more information might allow it
to
improve performance for the prependation, as in:
(({.!.1~ -)&(+&2) #)@:I.
But my tests didn't show improved performance, so it's not worth the
extra
code complexity or loss of clarity. It may not even be possible to
improve
the performance of a prependation, anyway.
[2] Often, you'll discover this when writing the verb that consumes the
inconsistent input, as you'll find yourself handling "edge cases" (i.e.
your own inconsistencies). But the more insidious cases are where you
may not discover the error when writing the verb, but calling it (often
with rare arguments, like 0, which makes for unpleasant surprises).
[3] Though of course I had a twinge when writing #;.1 f~ ]~:{. because
;.1
so obviously also does ]~:{. that using both seems redundant. We
could
avoid duplicating this work with e.g. (f~ (- |.!:_1)I.@:-.)@:(~:{.) ,
but
again this shows no improvement (to the contrary), and yet is longer
and
harder to understand. Perhaps if we could avoid the -. it might be
competitive with the ;.1 style solution.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
