Stream: helpdesk (published)

Topic: Creating a variable-length list comprehension using a macro


view this post on Zulip 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!

view this post on Zulip 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)

view this post on Zulip Or Golan (Apr 25 2023 at 12:15):

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)]

view this post on Zulip Sebastian Pfitzner (Apr 25 2023 at 12:15):

collect(zip([s:s-k+n for s in 1:k]...))?

view this post on Zulip 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)

view this post on Zulip 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.

view this post on Zulip 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.

view this post on Zulip 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.

view this post on Zulip 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)

view this post on Zulip Mason Protter (Apr 25 2023 at 16:46):

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

view this post on Zulip 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."

view this post on Zulip 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

view this post on Zulip Mason Protter (Apr 25 2023 at 17:37):

Your combs is a Vector{Any}, you should give it a concrete eltype

view this post on Zulip 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)

view this post on Zulip Gunnar Farnebäck (Apr 25 2023 at 17:44):

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.

view this post on Zulip Gunnar Farnebäck (Apr 25 2023 at 17:50):

Or you could just use Combinatorics.combinations of course. :-)

view this post on Zulip Mason Protter (Apr 25 2023 at 17:51):

Or Golan said:

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.

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)

view this post on Zulip Mason Protter (Apr 25 2023 at 17:53):

Looks like you want the upper-triangle of what the macro is making

view this post on Zulip 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?

view this post on Zulip 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

view this post on Zulip Mason Protter (Apr 25 2023 at 18:23):

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)

view this post on Zulip aplavin (Apr 25 2023 at 18:38):

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

view this post on Zulip Or Golan (Apr 25 2023 at 18:58):

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?

view this post on Zulip Mason Protter (Apr 25 2023 at 19:02):

Why are you storing vectors instead of Tuples?

view this post on Zulip 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

view this post on Zulip Gunnar Farnebäck (Apr 25 2023 at 19:28):

So how did the performance end up compared to Combinatorics.combinations?

view this post on Zulip 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)

view this post on Zulip Mason Protter (Apr 25 2023 at 19:43):

This is of course under the assumption that you can statically know the value of k.

view this post on Zulip Or Golan (Apr 26 2023 at 07:17):

I used vec since I want to index a collection with it


Last updated: Nov 22 2024 at 04:41 UTC