Thanks Bob. I agree that compiling often helps. I have previously
kicked around the idea of generating byte code or machine code and
interpreting it or executing it. I have called dlls in other
circumstances, but it would be nice to have everything in J.
In this case, the challenge put a 2GB constraint on memory and 60
seconds of execution time. It's an artificial constraint, which is why
I posted to chat. Those constraint wouldn't exist in the real world.
I'm scanning a 240MB text file and generating 9 character infixes and
processing them. I hit the memory limit using 9]\ so I figured I'd try
looping and using memr (15!:1). In an earlier version, about 270
seconds were spent in the looping construct and 40 seconds in memr. It
seemed like there should be a faster looping construct
Here's a simple version:
txt=: a. {~ (97&+(i. 26))
addr=: mema (# txt)
txt memw addr,0,(#txt)
6!:2 '([:<:([:0&{::(] ; smoutput&([:15!:1(addr,9,~<:@:])) ))) ^:] (<:#txt)'
yz
xyz
wxyz
vwxyz
uvwxyz
tuvwxyz
stuvwxyz
rstuvwxyz
qrstuvwxy
pqrstuvwx
opqrstuvw
nopqrstuv
mnopqrstu
lmnopqrst
klmnopqrs
jklmnopqr
ijklmnopq
hijklmnop
ghijklmno
fghijklmn
efghijklm
defghijkl
cdefghijk
bcdefghij
abcdefghi
I would need more processing of the results, but you can see roughly
how it compares to 9]\
9[\txt
abcdefghi
bcdefghij
cdefghijk
defghijkl
efghijklm
fghijklmn
ghijklmno
hijklmnop
ijklmnopq
jklmnopqr
klmnopqrs
lmnopqrst
mnopqrstu
nopqrstuv
opqrstuvw
pqrstuvwx
qrstuvwxy
rstuvwxyz
On Tue, Feb 3, 2015 at 3:05 PM, Robert Bernecky
<[email protected]> wrote:
> Compiling often helps. When I compile looping, scalar-dominated
> APL code, I generally get about a factor of 1000X speedup.
> You should get the same sort of speedup with compiled J.
> [No, I do not have a J compiler, but will be happy to create one
> if funding were to materialize.]
>
> However, you mentioned that you were "looping due to memory
> constraints...". Is it possible that a different algorithm would let
> you do less looping? E.g., looping over 1e4 elements at once,
> or using a different approach, such as dynamic programming?
>
> Bob
>
>
> On 15-02-03 02:53 PM, Joe Bogner wrote:
>>
>> I'm playing around with a coding challenge that I'm solving with a
>> loop that needs to execute over 200 million times.
>>
>> Setting aside whether that's a smart approach, what is the quickest
>> looping construct in J? I realize that J is not optimized for this
>> style of programming, but I'm still curious if it can be done
>> efficiently.
>>
>> The quickest I've found takes about 7 seconds to iterate 100 million
>> times, whereas the same loop in C takes 0.03 seconds.
>>
>> 6!:2 '(] [ ])^:] 100e6'
>> 7.00952
>>
>> The train is taking up some time, but eventually I will need it
>>
>> No train - 2.7 seconds
>>
>> 6!:2 ']^:] 100e6'
>> 2.70656
>>
>>
>> Explicit:
>>
>> loop=: 3 : 0
>> ctr=:0
>> while. 1 do.
>> ctr=:>:ctr
>> if. y < ctr do.
>> smoutput 'done'
>> return.
>> end.
>> end.
>> )
>>
>> 6!:2 'loop 100e6'
>> 122.48
>>
>> Clearly explicit isn't the way to go
>>
>> Back to the tacit:
>>
>> log=:smoutput bind ]
>>
>> ([: <: [: 0&{:: ] ; log )^:] 10
>> 10
>> 9
>> 8
>> 7
>> 6
>> 5
>> 4
>> 3
>> 2
>> 1
>> 0
>>
>> I would replace log with my function that uses the counter value
>>
>> That's pretty slow though on 100 million iterations - 88 seconds
>>
>> 6!:2 '([: <: [: 0&{:: ] ; ] )^:] 100e6'
>> 88.3644
>>
>> Let's try a new log
>>
>> log=: ] <:@:[ (smoutput bind ])
>> log 55
>> 55
>> 54
>>
>>
>> That looks like it could work. Let's put a dummy in for now
>>
>> log=: ] <:@:[ ]
>>
>> 6!:2 'log^:] 100e6'
>> 40.9542
>>
>> Still 40 seconds... Any ideas on how to speed up iteration like this?
>>
>>
>> Sidenote: I'm looping due to memory constraints placed on the coding
>> challenge
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>
>
> --
> Robert Bernecky
> Snake Island Research Inc
> 18 Fifth Street
> Ward's Island
> Toronto, Ontario M5J 2B9
>
> [email protected]
> tel: +1 416 203 0854
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
