Hi all!
parRuskey comparison.
Mike Days new version is slightly faster than the Frank Ruskey version.
Cheers,
Erling Hellenäs
----------Project----------
ts=: 6!:2 , 7!:2@] NB. Time and space
normalize=: 3 :0
NB. The idea here is to normalize the representation so that
NB. the copies are adjacent.
NB. Sort buckets within each combination after first item in each bucket
v31=.(] /: {.&.>)"1 y
NB. Sort buckets within each combination after number of items in each
bucket
v4=.(] /: #&.>)"1 v31
NB. Sort
v5=. /:~ v4
(/: #&.> v5){ v5
)
compare=: -:&:normalize
NB. parELMDE for comparison
parELMDE=: 4 : 0
a =. ~. i.~"1 iy #: i. */ iy =. (1+i.x),(y-x)$x
a =. a#~ x = #@~."1 a
sort a </."1 i. y
)
NB. Original Frank Ruskey version.
parRuskey =: 4 : 0
a=: i. y
r=: (0,y)$0
(x-1) S y-1
r </."1 i.y
)
S =: 4 : 0
if. x=y do.
r=:r,a
else.
for_i. i.x+1 do.
a=: i y } a
x S y-1
a=: y y } a
end.
if. x > 0 do.
a=: x y } a
(x-1) S y-1
a=: y y } a
end.
end.
)
NB. Slightly modified by Erling to remove global variables.
parRuskeyE =: 4 : 0
r=. (i.y) SE (x-1);y-1
r </."1 i.y
)
SE =: 4 : 0
'k n' =. y
r=. 0{.,:x
if. k=n do.
r=.,:x
else.
for_i. i.k+1 do.
r=.r, (i n } x) SE k;n-1
end.
if. k > 0 do.
r=.r, (k n } x) SE (k-1);n-1
end.
end.
r
)
NB. Modified by Mike Day
parRuskeyMD =: 4 : 0
NB. L =: 0$~0, 2 + y NB. debug/understand array of call parameters
r=. (i.y) SMD (x-1),y-1
NB. R =: r NB. debug/understand output
r </."1 i.y
)
SMD =: 4 : 0
NB. L =: L, y, x NB. debug/understand array of call parameters
'k n' =. y
a =.x
r =. 0$~ 0, #a
if. k = n - 1 do. NB. replace repeated calls with k = n (on entry)
r =. (i.k+1) n }"0 1 (k+1)# ,:a NB. don't need to use recursion here!
else.
NB. is there a way to avoid recursion here, too?
r =. r, ,/ (SMD&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead of
do loop
end.
if. k > 0 do.
r=.r, (k n } a) SMD (k-1),n-1
end.
r
)
x=:1
y=:1
(x parELMDE y) compare x parRuskey y
(x parELMDE y) compare x parRuskeyE y
NB.(x parELMDE y) compare x parRuskeyMD y - Error
x=:1
y=:2
(x parELMDE y) compare x parRuskey y
(x parELMDE y) compare x parRuskeyE y
(x parELMDE y) compare x parRuskeyMD y
x=:2
y=:3
(x parELMDE y) compare x parRuskey y
(x parELMDE y) compare x parRuskeyE y
(x parELMDE y) compare x parRuskeyMD y
x=:3
y=:5
(x parELMDE y) compare x parRuskey y
(x parELMDE y) compare x parRuskeyE y
(x parELMDE y) compare x parRuskeyMD y
x=:3
y=:6
(x parELMDE y) compare x parRuskey y
(x parELMDE y) compare x parRuskeyE y
(x parELMDE y) compare x parRuskeyMD y
x=:5
y=:10
ts'x parRuskey y'
ts'x parRuskeyE y'
ts'x parRuskeyMD y'
-------Output-------------------
x=:1
y=:1
(x parELMDE y) compare x parRuskey y
1
(x parELMDE y) compare x parRuskeyE y
1
NB.(x parELMDE y) compare x parRuskeyMD y - Error
x=:1
y=:2
(x parELMDE y) compare x parRuskey y
1
(x parELMDE y) compare x parRuskeyE y
1
(x parELMDE y) compare x parRuskeyMD y
1
x=:2
y=:3
(x parELMDE y) compare x parRuskey y
1
(x parELMDE y) compare x parRuskeyE y
1
(x parELMDE y) compare x parRuskeyMD y
1
x=:3
y=:5
(x parELMDE y) compare x parRuskey y
1
(x parELMDE y) compare x parRuskeyE y
1
(x parELMDE y) compare x parRuskeyMD y
1
x=:3
y=:6
(x parELMDE y) compare x parRuskey y
1
(x parELMDE y) compare x parRuskeyE y
1
(x parELMDE y) compare x parRuskeyMD y
1
x=:5
y=:10
ts'x parRuskey y'
0.204245 3.89459e7
ts'x parRuskeyE y'
0.316044 3.8954e7
ts'x parRuskeyMD y'
0.173341 3.8954e7
Cheers,
Erling Hellenäs
Den 2017-10-31 kl. 20:17, skrev 'Mike Day' via Programming:
parRuskeynew =: 4 : 0
NB. L =: 0$~0, 2 + y NB. debug/understand array of call parameters
r=. (i.y) Snew (x-1),y-1
NB. R =: r NB. debug/understand output
r </."1 i.y
)
Snew =: 4 : 0
NB. L =: L, y, x NB. debug/understand array of call parameters
'k n' =. y
a =.x
r =. 0$~ 0, #a
if. k = n - 1 do. NB. replace repeated calls with k = n (on entry)
r =. (i.k+1) n }"0 1 (k+1)# ,:a NB. don't need to use recursion here!
else.
NB. is there a way to avoid recursion here, too?
r =. r, ,/ (Snew&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead of
do loop
end.
if. k > 0 do.
r=.r, (k n } a) Snew (k-1),n-1
end.
r
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
