Question on tuple


#1

Hi,
From an arbitrary sized tuple of int like

t=(3,4,5,7)

I dont know how to create a function returning

(prod(t),prod(t[2:end]),prod(t[3:end]),prod(t[4:end]))

that is
(420, 140, 35, 7)
Any hints ?


#2

A generated function? But if your tuple is long, the efficiency gains may not materialize (benchmark). FWIW, since * is type stable, I would go with vectors even for short ones.


#3

This works but it would be better if cumprod would accept tuple as prod.

julia> (reverse(cumprod([reverse(t)...]))...,)
(420, 140, 35, 7)

#4

Nice. Thank you very much


#5

This only infers up to tuple-length of 3:

f(out, t::Tuple{}) = (out, ())
f(out, t) = f( (out..., prod(t)), Base.tail(t) )
f(t) = f((), t)[1]
f((3,4,5,7))
@code_warntype f((3,4,5)) # good
@code_warntype f((3,4,5,7)) # bad

Is there a way to avoid that?


#6

I have to warn you that this is not an efficient way. As @Tamas_Papp suggests it can be better to use Vector as t.


#7

No idea, I was trying this simultaneously and it does infer, although you have to reverse the tuple first…

function tuplecumprod(p,t::NTuple{N,Int}) where N
  m = t[1]*p
  (m,tuplecumprod(m,Base.tail(t))...)
end
tuplecumprod(p,t::Tuple{})=()
tuplecumprod(t)=tuplecumprod(1,t)

#8

Ah, yes, that’s better and nicer:

g(t::NTuple{1}) = t
g(t) where M = (prod(t), g(Base.tail(t))...)

However, it does far too many multiplications, and for some reason still allocates.

Yours is much faster:

julia> t = Tuple(1:20);

julia> @btime g($t)
  1.032 ÎĽs (39 allocations: 3.73 KiB)
(2432902008176640000, 2432902008176640000, 1216451004088320000, 405483668029440000, 101370917007360000, 20274183401472000, 3379030566912000, 482718652416000, 60339831552000, 6704425728000, 670442572800, 60949324800, 5079110400, 390700800, 27907200, 1860480, 116280, 6840, 380, 20)

julia> @btime reverse(tuplecumprod(reverse($t)))
  14.642 ns (0 allocations: 0 bytes)
(2432902008176640000, 2432902008176640000, 1216451004088320000, 405483668029440000, 101370917007360000, 20274183401472000, 3379030566912000, 482718652416000, 60339831552000, 6704425728000, 670442572800, 60949324800, 5079110400, 390700800, 27907200, 1860480, 116280, 6840, 380, 20)

Looks like that is the best solution. (Maybe you could do a PR to add your method to cumprod?)


#10

You often don’t need a generated function for this kind of thing: you can just splat the tuple into arguments and then use recursion that inlines at compile-time. For example, the following seems to generate fast inlined code with no loops:

revcumprod() = ()
revcumprod(x) = (x,)
function revcumprod(x, rest...)
    prest = revcumprod(rest...)
    return (x*first(prest), prest...)
end

revcumprod((3,4,5,7)...)

Of course, you probably wouldn’t want to do this for very long tuples, but if you have very long tuples then you might be using the wrong data structure anyway.


#11

Whow, the last two versions are really fast (and produce the same assembly code).
Thank you very much for your help. I learn a lot from this.

In particular, inspired by the proposed solutions, I have obtain a strong acceleration for my computations by replacing sub-tuple computation from shape[2:end] to Base.tail(shape) (more than 10x faster).