another bug fix, and an even faster version,
permC3 =: */@:(({. ! +/)\.)@:x:@:(#/.~)
permC4 =: */@:( !@:x:@:(+/)@:(1&=) , (({. ! +/)\.)@:x:@:((+/)@:(1&=) ,
-.&1))@:(#/.~)
permC4 takes advantage of the fact that items with frequency 1, can be grouped
together into their own "classification" with total frequency the sum of 1
frequency items. Then add as multiplicative parameter the factorial of that
number.
20 timespacex 'permC4 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000392368 209920
20 timespacex 'permC3 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000751679 213120
20 timespacex 'permC2 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000611071 208000
over 50% faster than permC2. It would lose speed advantage if all those 1
items were 2s and 3s.
20 timespacex 'permC4 (] # i.@#) 133 122 77 55 22 88 , 20 # 2'
0.000798223 213504
20 timespacex 'permC3 (] # i.@#) 133 122 77 55 22 88 , 20 # 2'
0.000867007 212096
20 timespacex 'permC2 (] # i.@#) 133 122 77 55 22 88 , 20 # 2'
0.000684271 206976
but because frequency distribution that includes many small frequencies would
tend to have more 1s than 2s and 3s, permC4 is likely the best when there are
mostly concentrated classifications
20 timespacex 'permC4 (] # i.@#) 5, (5 # 4) ,(10 # 2) , (20 # 2) , 30 # 1'
0.000695359 49280
20 timespacex 'permC2 (] # i.@#) 5, (5 # 4) ,(10 # 2) , (20 # 2) , 30 # 1'
0.000178352 50432
20 timespacex 'permC3 (] # i.@#) 5, (5 # 4) ,(10 # 2) , (20 # 2) , 30 # 1'
0.00147664 52608
when frequencies are sparse, permC2 is much faster. But then there is an
improvement to original permC that speeds this last form up even more.
Memoization.
permC =: (# %&(*/)&:(!M.@x:) 1 -.~ #/.~)
20 timespacex 'permC (] # i.@#) 5, (5 # 4) ,(10 # 2) , (20 # 2) , 30 # 1'
0.000167872 115584
when there are just a few classifications (and high frequencies of each) then
permC3 is best, with specialization of few classifications + other outliers,
then permC4.
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: "[email protected]" <[email protected]>
Sent: Monday, May 9, 2016 2:30 PM
Subject: Re: [Jprogramming] challenge: optimizing permutations with repeat count
bug fixes,
del1 =: i.~ ({. , >:@[ }. ]) ]
permC2 =: (] ((] + >:@i.@((-~ +/)~)) ([ ({."1@[ */@:^&x: -/@:,:&:({:"1))&:(~.
,. #/.~)&:(/:~)&(;@:(q:&.>)) ;@:((2 + i.@<:)&.>)@:]) 1 -.~ del1~) >./)@:(#/.~)
f.
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: "[email protected]" <[email protected]>
Sent: Monday, May 9, 2016 2:02 PM
Subject: Re: [Jprogramming] challenge: optimizing permutations with repeat count
First permC can be sped up by removing 1s from factorial of right hand side
permC =: (# %&((*/))&:(!@x:) 1 -.~ #/.~)
this gets at least 20% or so consistent speed improvement
permC2 =: (] ((] + >:@i.@((-~ +/)~)) ([ ({."1@[ */@:^&x:
(-/@:,:)&:({:"1))&:(~. ,. #/.~)&:(/:~)&(;@:(q: each)) ;@:((2 + i.@<:)
each)@:]) 1 -.~ -.) >./)@:(#/.~)
an easier to follow model of permC2 through more linear code. Basically the q:
of each side's digits are taken, and consolidated into the q: exponent table
format. Each side is guaranteed to have at least 1 copy of every consecutive
prime (with right side having fewer primes than left), and so the exponents can
just be subtracted.
(({."1 every@:{.) */@:^&x: -/@:({:"1 every)) (~. ,. #/.~) each /:~@:;@:(q:
each) each ((2 + i.@<:)@:(+/) ; ;@:((2 + i.@<:) each)) 8 8 8 1 2 3 1 1 1 13
1123431404579781579567208123200000
timespacex 'permC (] # i.@#) 133 122'
0.000542399 94208
timespacex 'permC2 (] # i.@#) 133 122'
0.00020096 70912
20 timespacex '(# !~ x:@{.@(#/.~)) (] # i.@#) 133 122'
7.62079e_5 112512
The last example takes advantage of calculating boolean list permutations is
the same formula as dyadic !. Its 3x faster, even after converting back from
list format, and suggests another possible technique to extend to 3 +
classifications as repeated application of the boolean/combination formula.
items are 0 or not 0, then for those not 0, are 1 or 2.
permC3 =: */@:({. ! +/)\.@:x:@:(#/.~)
this is faster as long as there is a reasonable number of "classifications"
with relatively high frequencies
20 timespacex 'permC3 (] # i.@#) 133 122 77 55 22 88'
0.00040688 202624
20 timespacex 'permC2 (] # i.@#) 133 122 77 55 22 88'
0.000535343 194688
20 timespacex 'permC3 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000709327 213120
20 timespacex 'permC2 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000590591 208000
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: Programming Forum <[email protected]>
Sent: Monday, May 9, 2016 11:10 AM
Subject: [Jprogramming] challenge: optimizing permutations with repeat count
permC =: (# %&((*/))&:(!@x:) #/.~)
this takes a list as argument, and the innerverb takes the factorials of the
count, and divides with the product of the factorials of item frequencies.
I notice that there is not much difference between these 2 functions:
20 timespacex '*/ 2 + i. <: 500x'
0.000897903 156928
20 timespacex '!500x'
0.000890463 88448
The permutation count of a list is guaranteed to be an integer which means that
every single term on the right hand side is combinable into a term that exists
on the left hand side.
permC 8 # 0 1 2
9465511770
the left and right product lists,
((2 + i.@<:) 24) ; ;@:((2 + i.@<:) each) 8 8 8
so find f such that,
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 f 2 3 4 5 6 7 8 2
3 4 5 6 7 8 2 3 4 5 6 7 8
is faster than permC, likely resulting in no division step.
One quick optimization may be: (removing largest frequency from left hand side)
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 f 2 3 4 5 6 7 8 2 3 4 5 6 7 8
----------------------------------------------------------------------
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
