[Jprogramming] Memoizing (Project Euler problem 14)

[greg heil]

>An interesting alternative to the verbs Roger expressed on page
http://jsoftware.com/jwiki/Essays/Collatz%20Conjecture)

   collatz=: -:`(>:@(3&*))`1: @. (1&= + 2&|)
   collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y'

are

   cg=:-:`(>:++:)`1:@.(1&=+2&|)
   cgv=:  13 : '(2|y)}  (<.-:)`(>:++:)`:0 y'

>They are only slightly faster (0%? maybe Dan can do the same analysis he did earlier:) but maybe clearer as to the algorithm of Collatz' conjecture, ie
   -:`(>:++:) NB. even`odd

>If one wants to accomodate a 1 argument one can extend cgv like so:
   cgvp=:  13 : '((1&= + 2&|)y)}  (<.-:)`(>:++:)`1:`:0 y'

greg
~krsnadas.org

--

from: Michal D. <michal.dobrogost at gmail.com>
to: programming at jsoftware.com
date: 4 August 2014 16:08
subject: Re: [Jprogramming] Memoizing (Project Euler problem 14)

>Good point, it's probably there solely for the type cast, allowing later operations to work on integers.  On my machine it's ~10% faster:

?   collatzv=: 3 : '(2|y)} 0 1 + 0.5 3 */y'
   ts 'cnv 1e6'
2.03499 5.97765e7
   ts 'cnv 1e6'
2.04466 5.97765e7
   ts 'cnv 1e6'
2.08829 5.97765e7

?   collatzv=: 3 : '<. (2|y)} 0 1 + 0.5 3 */y'
   ts 'cnv 1e6'
1.81025 6.03008e7
   ts 'cnv 1e6'
1.83654 6.03008e7
   ts 'cnv 1e6'
1.87314 6.03008e7?

--

from: Raul Miller <rauldmiller at gmail.com>
to: Programming forum <programming at jsoftware.com>
date: 4 August 2014 15:45
subject: Re: [Jprogramming] Memoizing (Project Euler problem 14)

That's an interesting thought.

>As near as I can tell, the only thing it does is convert the result from floating point representation to integer representation.

>Whether that's good, bad, relevant or irrelevant is ... not something I know how to decide for the general case.

Thanks,
Raul

--

from: Michal D. <michal.dobrogost at gmail.com>
to: programming at jsoftware.com
date: 4 August 2014 14:13
subject: Re: [Jprogramming] Memoizing (Project Euler problem 14)

Is it just me or is the <. in collatzv unnecessary?

(I'm referring to http://jsoftware.com/jwiki/Essays/Collatz%20Conjecture)

Cheers,

Mike

--

from: Dan Bron <j at bron.us>
to: programming at jsoftware.com
date: 4 August 2014 05:12
subject: Re: [Jprogramming] Memoizing (Project Euler problem 14)

>If you're OK with spoilers, have you seen Roger's Collatz Conjecture essay on the Wiki?

http://jsoftware.com/jwiki/Essays/Collatz%20Conjecture

>In particular, he develops a vector approach to the problem which greatly outperforms the scalar solution (a common pattern in J programs).

>On my laptop, cnv is the clear winner; here is a comparison of Roger's cn (scalar solution) to cnv (vector solution), both verbatim and against an argument of 1e6:

Algo Time  Space
cn   10.85  1.00
cnv   1.00  3.58

>The vector approach is an order of magnitude faster (but the scalar solution is somewhat leaner).

>I even tried "improving" the scalar solution by memoizing it, but somehow that hurt performance. Here, cn and cnv are as above, and cnM is cn with M. applied to the "collatz" subfunction, all against a much smaller argument, 1e3 (you'll see why in a moment):

Algo   Time Space
cn     5.17  1.00
cnM  127.88 12.44
cnv    1.00  1.26

>Here, the memoized version is two orders of magnitude slower than the vector solution, and also (somehow) an order of magnitude slower than its unmemoized counterpart.

>Takeaway: work simultaneously on as much data as you can (or, as Hnery would put it "Let J's primitives see as much data as possible").

-Dan

--

Subject: [Jprogramming] Memoizing (Project Euler problem 14)
From: mvillarino <mvillarino at gmail.com>
Date: Mon, 4 Aug 2014 13:18:03 +0200
To: programming at jsoftware.com

Good day:

>I've been struggling a couple weeks long to solve Project Euler problem 14 in a reasonable time, but the best I can get takes much much longer in my machine. Several hours.

Well, my current solution is this:


collatz =. verb define
if. 1= y do. y return. end.
if. 0= 2|y do. y=. -:y else. y=.>:3*y end.
)

reduceTable=. verb define
NB.    y is expected to be a 2-row table
NB.       with starting numbers on first row
NB.       and a number in the collatz sequence on the 2nd.
   if. 1= $1{y do. y return. end.
   NB. nmemonics / definicions
   range =. 0{y
   seq   =. 1{y
   NB. operations
   NB. compute the following number in the collatz sequence for each of
   NB.    the candidates. Take off the table a candidate if it appears in
the
   NB.    sequence of any other candidate (as they are for sure not the
   NB.    ones with the longest sequence).
   seq  =. (aux=: -.(range e. aux)+.(aux e. 1 2 4))# aux=: collatz"0 seq
   range=. aux#range
   NB. reconstruction
   range ,: seq
)

reduceTable^:_  ,:~ >:i.1e6

NB. another attempt

reducirLista =. verb define
   memo =. 1 1
   list =. }. list=.>:i.y
   while. 1<#list do.
         NB. compute the collatz sequence for the next number
      c =. collatz^:(<_) {. list
         NB. take out of the list of candidates ... (vid supra).
      list =. (list -.@:e. c)#list
         NB. remember the canditate and it's collatz sequence lenght.
      memo =. memo, ,: ({.,#)c
   end.
)


>By reading spoilers, it seems the way to go is through memoization. Despite my attempts with M. here and there, I have found no satisfying solution (satisfying = fast). Can someone point me to a different approach and to a memoization with J tutorial?

Regards,