What you can do is define a simple function dig=. [: (+ i.@:(9&*)) 10^<: that gives you all the numbers with y digits and loop over that. Since 10&#.^:_1 is indeed faster than "."0@":"0 (which I did not expect, as the latter is listed under special code), this gives the fastest execution yet. The memory use should also only be O(nlogn) for numbers up to n, which is pretty negligible.
Marshall -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Alex Gian Sent: Sunday, August 29, 2010 2:49 PM To: Programming forum Subject: Re: [Jprogramming] Splitting an integer into its digits Thanks for the tip about the precomputed values, I should have done it to be fair, since I use it in my Perl comparison, but I forgot as I'm concentrating on learning J here... It does indeed bring a big speedup, although I'm pretty sure that my integer-splitting method is a quite a bit faster than the one you suggest. I like the idea of using rank 1 rather than transpose. Anyway, fastest I've got so far, and quite an acceptable result to me would now be specialX -. = +/"1@({&f)@(10&#.inv) if only I could sort out the leading zero problem. Your character-oriented splitting fixes it, but doubles+ the execution time. Finding specialX <10e5 now <2 seconds on my ARM 260 (vs 28 for Perl) (6" using char-splitting) Finding specialX <10e6 now <2 seconds on my desktop (4" using char-splitting) Anyway, been quite an experience thanks to all for their input. On Sun, 2010-08-29 at 13:32 -0400, Marshall Lochbaum wrote: > By the way, if you want to add up the array of (+!)s of digits, you > should use +/"1 instead of +/@:|: . It's much faster and prettier. > > Marshall > > -----Original Message----- > From: [email protected] > [mailto:[email protected]] On Behalf Of Alex Gian > Sent: Sunday, August 29, 2010 12:05 PM > To: Programming forum > Subject: Re: [Jprogramming] Splitting an integer into its digits > > Hi Ric and all, > > There's one more thing I'd like to mention, now that I got this 'rank' > thing sorted: > > I don't know if you noticed, but adding "0 to the 'digits' verb, has > some interesting, and IMHO not very acceptable effects on time and space taken. > > For instance, finding specials <10e5 is instantaneous on my desktop > machine without the "0, yet takes about 7 seconds when done the other > way. in the process it uses all of my 2Gb memory! > (OK, without the "0 means using the ugly transpose method AND getting > the wrong results for leading zeros, but still. I guess J really does > prefer big arrays!!) Trying to find all specials <10e6, eats up all > mem PLUS my 6Gb swap space without achieving a result. Without the "0 > I get the result 1n 2 seconds, albeit with the wrong value for numbers with leading-zeros. > > On my PDA (Acer n30, which is my main J learning platform), it doesn't > even finish without the "0, complains it's out of memory. > I dragged out my old Jornada 928 (J502) and it managed to finish here, > probably a bit more memory available. Took 18 seconds on what is > basically a 206MHz ARM. > In comparison, my Nokia 770, with a 260MHZ ARM, solves the same > problem iteratively, in Perl, in 28 seconds, without taking any space at all. > > I don't think this reflects too well on J. I suppose what I'm asking > is: is there another (neat J-like) way to do searches, other than > using # over huge arrays, that would take up little (preferably > constant) space for this class of problems? > > > > > On Sun, 2010-08-29 at 02:35 +1200, Sherlock, Ric wrote: > > > If you add the "0 to digits, you don't need to use the transpose > > because > +/ is only ever getting fed a list (rank 1). > > > > digits=: 10&#.^:_1"0 > > fp1=: + ! > > spsum=: +/@f...@digits > > special=: = spsum > > (#~ special) 1974 123 85837 408297 > > 85837 408297 > > > > special f. > > = +/@(+ !)@(10&#.^:_1"0) > > > > IOW a one-liner for special would be: > > special2=: = +/@(+ !)@(10&#.^:_1"0) > > (#~ special2) 1974 123 85837 408297 > > 85837 408297 > > > > -------------------------------------------------------------------- > > -- 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
