Or Golan (Apr 25 2023 at 12:00): Or Golan (Apr 25 2023 at 12:00):I'm trying to create a list comprehension to create a list of tuples of length k, and I figured that macro is the way to do it.
An example for k = 2 of the list comprehension i'm trying to get (for some given n):
[[i, j] for i=1:(n-k+1) for j=(k+i-1):(n-k+2)]
The m-th index i_m would go from i_{m-1}+1 to n-k+m.
I tried creating the following macro, but this seems way off:
macro create_indices(n, k)
iterator_expressions = map(1:k) do s
Expr(
:(=),
Symbol("i", s),
quote $(esc(s)):$(esc(s - k + n)) end
)
end
Expr(
:comprehension,
[esc(Symbol("i", s)) for s=1:k],
iterator_expressions...,
)
end
for some reason i'm only getting a matrix of expressions, and I have no idea what i'm doing wrong. Please help!
Leandro Martínez (Apr 25 2023 at 12:13):Why do you need a macro for that?
julia> create_indices(n,k) = [(i,j) for i=1:(n-k+1) for j=(k+i-1):(n-k+2)]
create_indices (generic function with 1 method)
julia> create_indices(3,2)
3-element Vector{Tuple{Int64, Int64}}:
(1, 2)
(1, 3)
(2, 3)
because for k=3 I need
[[i, j, l] for i=1:(n-k+1) for j=(k+i-2):(n-k+2) for l=(k+j-2):(n-k+3)]
collect(zip([s:s-k+n for s in 1:k]...))?
Leandro Martínez (Apr 25 2023 at 12:21):This will not generate the correct indices, but very likely you can adapt it to do it:
julia> function create_indices(n,k)
[ ntuple(k) do i
j-k+i
end
for j in 1:n
]
end
create_indices (generic function with 1 method)
julia> create_indices(3,4)
3-element Vector{NTuple{4, Int64}}:
(-2, -1, 0, 1)
(-1, 0, 1, 2)
(0, 1, 2, 3)
(in any case I'm sure a macro will only make things more complicated. If you can write the indexing correctly in a macro, it will be easier with a standar function)
Or Golan (Apr 25 2023 at 12:30):Leandro Martínez said:
This will not generate the correct indices, but very likely you can adapt it to do it:
julia> function create_indices(n,k) [ ntuple(k) do i j-k+i end for j in 1:n ] end create_indices (generic function with 1 method) julia> create_indices(3,4) 3-element Vector{NTuple{4, Int64}}: (-2, -1, 0, 1) (-1, 0, 1, 2) (0, 1, 2, 3)(in any case I'm sure a macro will only make things more complicated. If you can write the indexing correctly in a macro, it will be easier with a standar function)
I'm not sure this is possible as the indices depend on each other:
The m-th index i_m would go from i_{m-1}+1 to n-k+m.
Leandro Martínez (Apr 25 2023 at 14:32):Getting that kind of thing right is tricky, but it is trickier with a macro. In either case you need to figure out which is the (possible recursive) algorithm that will generate the correct sequence. And then, implementing that as a function is easier than as a macro.
Kwaku Oskin (Apr 25 2023 at 16:18):I think, you can write iterator with a somewhat complicated state. Update of the state can have some overhead of course, but usually it should be overshadowed by main calculations.
Mason Protter (Apr 25 2023 at 16:43):@Or Golan It's not very clear to me what you're trying to do here, but here's me fixing the syntax errors in your macro. It at least correctly parses now, but I don't know if this is exactly the iteration layout you wanted, I left all the actual logic how you wrote it.
macro create_indices(n, k)
iterator_expressions = map(1:k) do s
:($(Symbol("i", s)) = $s:$(s - k + n))
end
Expr(
:comprehension,
Expr(:tuple, (Symbol("i", s) for s=1:k)...),
(iterator_expressions)...,
) |> esc
end
julia> @create_indices(4, 2)
3×3 Matrix{Tuple{Int64, Int64}}:
(1, 2) (1, 3) (1, 4)
(2, 2) (2, 3) (2, 4)
(3, 2) (3, 3) (3, 4)
julia> @create_indices(4, 3)
2×2×2 Array{Tuple{Int64, Int64, Int64}, 3}:
[:, :, 1] =
(1, 2, 3) (1, 3, 3)
(2, 2, 3) (2, 3, 3)
[:, :, 2] =
(1, 2, 4) (1, 3, 4)
(2, 2, 4) (2, 3, 4)
I suspect this isn't the logic you actually intended though because the example you have [[i, j] for i=1:(n-k+1) for j=(k+i-1):(n-k+2)] is different
Mason Protter (Apr 25 2023 at 16:49):But also that example you gave contracts what you said about "The m-th index i_m would go from i_{m-1}+1 to n-k+m."
Or Golan (Apr 25 2023 at 17:29):I'm trying to get all k-combinations from some collection of length n
Mason Protter said:
I suspect this isn't the logic you actually intended though because the example you have
[[i, j] for i=1:(n-k+1) for j=(k+i-1):(n-k+2)]is different
that's actually the same for k=2 - k+i-1 = i+1.
I started with a recursive function that does this, but I'm trying to reduce the number of allocations, so I thought that generating the list comprehension using a macro would be more efficient. Here is the recursive function:
function combinations(collection, k)
n = length(collection)
combs = []
for i in 1:n
el = collection[i]
if k == 1
push!(combs, [el])
else
rest = collection[i+1:end]
subcombs = combinations(rest, k-1)
for subcomb in subcombs
push!(combs, [el; subcomb])
end
end
end
combs
end
Your combs is a Vector{Any}, you should give it a concrete eltype
Gunnar Farnebäck (Apr 25 2023 at 17:39):Just for fun and not in any way efficient:
julia> create_indices(n, k) = reverse.(collect(Iterators.Filter(x -> issorted(x, lt = !<), Iterators.product(fill(1:n, k)...))))
create_indices (generic function with 1 method)
julia> create_indices(5, 3)
10-element Vector{Tuple{Int64, Int64, Int64}}:
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)
Regarding the macro approach,
julia> dump(:([[i, j, l] for i=1:(n-k+1) for j=(k+i-2):(n-k+2) for l=(k+j-2):(n-k+3)]))
Expr
head: Symbol comprehension
args: Array{Any}((1,))
1: Expr
head: Symbol flatten
args: Array{Any}((1,))
1: Expr
head: Symbol generator
args: Array{Any}((2,))
1: Expr
head: Symbol flatten
args: Array{Any}((1,))
1: Expr
2: Expr
head: Symbol =
args: Array{Any}((2,))
1: Symbol i
2: Expr
indicates that you would need to nest flatten and generator expressions.
But I tend to agree with the opinion that an iterator should be the best approach for this problem.
Gunnar Farnebäck (Apr 25 2023 at 17:50):Or you could just use Combinatorics.combinations of course. :-)
Mason Protter (Apr 25 2023 at 17:51):Or Golan said:
I'm trying to get all
k-combinations from some collection of lengthnMason Protter said:
I suspect this isn't the logic you actually intended though because the example you have
[[i, j] for i=1:(n-k+1) for j=(k+i-1):(n-k+2)]is differentthat's actually the same for
k=2-k+i-1 = i+1.
Are you sure?
julia> let n = 5, k = 2
[[i, j] for i=1:(n-k+1) for j=(k+i-1):(n-k+2)]
end
10-element Vector{Vector{Int64}}:
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]
julia> macro create_indices(n, k)
iterator_expressions = map(1:k) do s
:($(Symbol("i", s)) = $s:$(s - k + n))
end
Expr(
:comprehension,
Expr(:tuple, (Symbol("i", s) for s=1:k)...),
(iterator_expressions)...,
) |> esc
end
@create_indices (macro with 1 method)
julia> @create_indices(5, 2)
4×4 Matrix{Tuple{Int64, Int64}}:
(1, 2) (1, 3) (1, 4) (1, 5)
(2, 2) (2, 3) (2, 4) (2, 5)
(3, 2) (3, 3) (3, 4) (3, 5)
(4, 2) (4, 3) (4, 4) (4, 5)
Looks like you want the upper-triangle of what the macro is making
Or Golan (Apr 25 2023 at 18:14):Yeah, the macro I tried writing was wrong, but in two dimensions. Thanks to you it is wrong only in one way, but when I tried to correct the logic I'm still way off:
macro create_indices(n, k)
local i0 = 0
iterator_expressions = map(1:k) do s
:($(Symbol("i", s)) = ($(Symbol("i", s-1)) + 1):$(s - k + n))
end
Expr(
:comprehension,
Expr(:tuple, (Symbol("i", s) for s=1:k)...),
(iterator_expressions)...,
) |> esc
end
It's telling me that i0 is not defined, and if I define it outside, it says that i1 is not defined. I think there is something to do with hygiene here?
Mason Protter (Apr 25 2023 at 18:22):Here's how I'd do this:
julia> @generated function create_indices(n, ::Val{k}) where {k}
ex = foldr(1:k, init=:(push!(out, $(Expr(:tuple, (Symbol(:i_, s) for s ∈ 1:k)...))))) do s, old
lower = s == 1 ? 1 : :(k + $(Symbol(:i_, s-1)) - 1)
quote
for $(Symbol(:i_, s)) ∈ $lower:(n - k + $s)
$old
end
end
end
quote
out = NTuple{$k, Int}[]
$ex
out
end
end
julia> create_indices(5, Val(2))
10-element Vector{Tuple{Int64, Int64}}:
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 3)
(2, 4)
(2, 5)
(3, 4)
(3, 5)
(4, 5)
julia> create_indices(8, Val(3))
20-element Vector{Tuple{Int64, Int64, Int64}}:
(1, 3, 5)
(1, 3, 6)
(1, 3, 7)
(1, 3, 8)
(1, 4, 6)
(1, 4, 7)
(1, 4, 8)
(1, 5, 7)
(1, 5, 8)
(1, 6, 8)
(2, 4, 6)
(2, 4, 7)
(2, 4, 8)
(2, 5, 7)
(2, 5, 8)
(2, 6, 8)
(3, 5, 7)
(3, 5, 8)
(3, 6, 8)
(4, 6, 8)
Also something along these lines may help:
Base.Cartesian.@nloops 3 i m->(k+i_{m+1}-2:n-k+m) begin
push!(res, Base.Cartesian.@ntuple 3 i)
end
Thanks @Mason Protter ! I was able to build exactly what I needed from this code.
In case anyone else is interested:
@generated function create_indices(n, ::Val{k}) where {k}
ex = foldr(1:k, init=:(push!(out, $(Expr(:vect, (Symbol(:i_, s) for s ∈ 1:k)...))))) do s, old
lower = s == 1 ? 1 : :($(Symbol(:i_, s-1)) + 1)
quote
for $(Symbol(:i_, s)) ∈ $lower:(n - k + $s)
$old
end
end
end
quote
out = Vector{Int}[]
$ex
out
end
end
By the way, why did you need to use Val?
Mason Protter (Apr 25 2023 at 19:02):Why are you storing vectors instead of Tuples?
Mason Protter (Apr 25 2023 at 19:03):By the way, why did you need to use Val?
That's because generated functions operate on types rather than values, so to generate a different number of loops depending on k, I needed to lift k into the type domain using Val
Gunnar Farnebäck (Apr 25 2023 at 19:28):So how did the performance end up compared to Combinatorics.combinations?
Mason Protter (Apr 25 2023 at 19:43):julia> using Combinatorics
julia> @generated function create_indices_tup(n, ::Val{k}) where {k}
ex = foldr(1:k, init=:(push!(out, $(Expr(:tuple, (Symbol(:i_, s) for s ∈ 1:k)...))))) do s, old
lower = s == 1 ? 1 : :(k + $(Symbol(:i_, s-1)) - 1)
quote
for $(Symbol(:i_, s)) ∈ $lower:(n - k + $s)
$old
end
end
end
quote
out = NTuple{$k, Int}[]
$ex
out
end
end;
julia> @generated function create_indices_vec(n, ::Val{k}) where {k}
ex = foldr(1:k, init=:(push!(out, $(Expr(:vect, (Symbol(:i_, s) for s ∈ 1:k)...))))) do s, old
lower = s == 1 ? 1 : :($(Symbol(:i_, s-1)) + 1)
quote
for $(Symbol(:i_, s)) ∈ $lower:(n - k + $s)
$old
end
end
end
quote
out = Vector{Int}[]
$ex
out
end
end;
julia> let n = Ref(5), k = 3
@btime collect(Combinatorics.combinations(1:$n[], $k))
@btime create_indices_vec($n[], Val($k))
@btime create_indices_tup($n[], Val($k))
end;
356.250 ns (22 allocations: 1.30 KiB)
326.026 ns (13 allocations: 1.23 KiB)
122.733 ns (2 allocations: 272 bytes)
This is of course under the assumption that you can statically know the value of k.
Or Golan (Apr 26 2023 at 07:17):I used vec since I want to index a collection with it
Last updated: Nov 06 2024 at 04:40 UTC