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
----- Original Message ---------------
Subject: [Jprogramming] Memoizing (Project Euler problem 14)
From: mvillarino <[email protected]>
Date: Mon, 4 Aug 2014 13:18:03 +0200
To: [email protected]
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,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
