Generic array scan line

General Usage
1

I have:

const w, h = 640, 480
a = rand(Float32, w, h)

and an algorithm, which requires scanning array a by row or column in all possible directions like shown here:

function scan4(a)
  scanLine = zeros(max(w, h))

  for i in 1:h
    foo!(scanLine, a[:, i])
  end

  scanLine = zeros(max(w, h))

  for i in h:-1:1
    foo!(scanLine, a[:, i])
  end

  scanLine = zeros(max(w, h))

  for i in 1:w
    foo!(scanLine, a[i, :])
  end

  scanLine = zeros(max(w, h))

  for i in w:-1:1
    foo!(scanLine, a[i, :])
  end
end

Is there a magic indexing trick, which would allow rewriting scan4 function avoiding repetitions to get something like this without dramatic loss of performance:

function scan42(a)
  for indexingScheme in [colLeftRight, colRightLeft, rowTopDown, rowBottomUp]
    scanLine = zeros(max(w, h))

    for i in magicIndex(a, indexingScheme)
      foo!(scanLine, magicSlice(a, i, indexingScheme))
    end
  end
end

I’m looking for an existing API, which does something similar, not how to write something new from scratch using macros, unless it’s fairly simple and idiomatic to Julia.

2

You can write generators like

col_left_right = ( view(a, :, i) for i in 1:size(a, 2) )
1 Like
3

Isn’t it eachcol?

4

It is for colLeftRight scan, but can I get eachcol in reverse for colRightLeft scan?

5

It looks like you can do Iterators.reverse(eachcol(xs)) (but not reverse(eachcol(xs))).

3 Likes
6

This is another option, but I don’t know if it’s efficient:

eachcol(reverse(a, dims=2))
7

reverse copies an array. It’s not efficient if you have a gigantic array.

3 Likes
8

Should be Iterators.reverse.(eachcol(xs)) from my understanding.

9

In that case, (Iterators.reverse(c) for c in eachcol(xs)) for a non-allocating version. Iterators.map(Iterators.reverse, eachcol(xs)) would also work in Julia 1.6.

1 Like
10

Read this part only after writing the below. My bad :sweat_smile:

Technically, you can do

function scan4(a)
    w, h = size(a)
    magic_iterator = (eachcol,
                      xs -> (@view(c[end:-1:1]) for c in eachcol(xs)),
                      eachrow,
                      xs -> (@view(c[end:-1:1]) for c in eachrow(xs)))

    for f in magic_iterator
        scanLine = zeros(max(w, h))
        for x in f(a)
            foo!(scanLine, x)
        end
    end
end

but this is not type stable (the type of f changes each iteration) so not that good of an idea. You can generate the 4 loops with:

@generated function scan4_gen(a)
    magic_iterator = (eachcol,
                      xs -> (@view(c[end:-1:1]) for c in eachcol(xs)),
                      eachrow,
                      xs -> (@view(c[end:-1:1]) for c in eachrow(xs)))

    expr = quote w, h = size(a) end

    for i in 1:length(magic_iterator)
        iter = quote
            scanLine = zeros(max(w, h))
            for x in $(magic_iterator[i])(a)
                foo!(scanLine, x)
            end
        end
        push!(expr.args, iter)
    end

    expr
end

which “saves typing” and is fast, but at great expense to readability… If you wanted to generalize to scanning N-D arrays, a generated function is what I would suggest. For this though :man_shrugging: ymmv. I can’t think of another way that doesn’t also incur its own costs.

I went with @view(c[end:-1:1] since Iterators.reverse doesn’t support iteration (maybe not necessary though). Note that in 1.5+, you should use @view(c[end:-1:begin]).

1 Like