Is there any efficient way to generating the non-associative binary products ?

#1

I want to generate all the non-associative product for any ordered list. The code is following

struct X<: Number
first
second
function X(a,b)
new(a,b)
end
end
function XProduct(TL::Vector)
if length(TL)>1
h=vcat(X(TL[1],TL[2]),TL[3:end]);
for i = 2:length(TL)-1
a=TL[1:i-1]
b=X(TL[i],TL[i+1])
c=TL[i+2:end]
h=hcat(h,vcat(a,b,c))
end
return(h)
else
return(TL)
end
end

function binaryProduct(n::Int64)
TL=Vector(1:n)
XP = XProduct(TL)
while length(XP[:,1])>1
h=XProduct(XP[:,1])
for i = 2:size(XP)[2]
h=hcat(h,XProduct(XP[:,i]))
end
XP=h
end
return XP
end

Then I call the function binaryProduct(9). It takes nearly 9 seconds
image .
While same program in Mathematica only need 0.8 seconds.
WeChatff6a91e1b296157f9a49dcfc3d402149 .

I am a newer in Julia. Are there any way to improve the efficiency of the Julia code?

#2

Yes, it should definitely be possible to improve the speed of your Julia code. However, it will be much easier to help you if you can follow the directions here: PSA: how to quote code with backticks so that your code will be more readable. You should also take a look at the general Julia performance tips: https://docs.julialang.org/en/v1/manual/performance-tips and in particular the section about avoiding fields with abstract type, which is a problem with your current code: https://docs.julialang.org/en/v1/manual/performance-tips/index.html#Avoid-fields-with-abstract-type-1

#3

Not sure if that’s true. If I understand OP correctly, they are trying to represent a tree of varying depth. Avoiding abstract types will lead to something like

struct X{T1, T2}
   a::T1
   b::T2
end

or, more succinctly, to X = tuple. But in that way, the entire computation will actually be a compile time problem, because you’ll get e.g. (for n=3)

Tuple{Int, Tuple{Int, Int}}
Tuple{Tuple{Int, Int}, Int}

for the element types. This represents the answer of the computation completely.

It’s possible to “cheat” in this way and let the compiler take care of what you’re trying to do, but whether that’s fair/helpful for a comparison to Mathematica depends on what @gangchern is hoping to do with this result array next. @gangchern, could you help us understand?