Solving this without a loop (learning purposes)

General Usage Performance
, ,
1

I’m trying to get more familiar with using Transducers.jl or related functions that avoid loops - just to learn. Let’s say I have this simple vector
x = Bool[1,1,0,0,1,1,0,1]
and I want to find the indices of adjacent True, so in this case, get:

(1,2)
(5,6)
(8,8)

I came this far:
collect(Enumerate(), x) |> Filter(x->x[2]==1) |> Map(x -> x[1]) |> collect
Which gives:

5-element Vector{Int64}:
 1
 2
 5
 6
 8

Then I should basically “loop” through these to get the adjacent values I thought of fold but that needs the same output format as the input. Would be curious to see how this can be solved without writing a loop :slight_smile:

EDIT
Maybe findall would be easier to get the indexes haha:
findall(x->x==true, z)

5-element Vector{Int64}:
 1
 2
 5
 6
 8

But the latter step I’m not sure how to solve without a loop

2

Somehow your examples don’t work and why do you want the index 8 ?

Here is my first approach:

julia> x = Bool[1,1,0,0,1,1,0,1]
8-element Vector{Bool}:
 1
 1
 0
 0
 1
 1
 0
 1

julia> findall( x .& append!(x[2:end],false) )
2-element Vector{Int64}:
 1
 5

And you should define what you mean with “without loops”. At the end there will be a loop executed.

3

I want to get the indices of the 1s or interval when multiple adjacent 1s are present. Hence all intervals for ones would be [ [1,2], [5,6], [8,8] ] the last one is not really an “interval” but there is no adjacent value.

Not sure what your code answers with 1, 5?

4 
julia> findall( x .&& append!(x[2:end],true) )
3-element Vector{Int64}:
 1
 5
 8

I still don’t get the index 8.
Would be trivial to generate the second index here, but with the 8 it’s a problem.

5

Does this also only work for two adjacent values? I actually meant it to also work in the case of:

 1
 1
 1
 0
 1
 1
 0
 1

For example

6

True.
Not a solution than.
And now I understand the 8…

7

One-shot:

tuple.(findall(diff([0; x]) .== 1), findall(diff([x; 0]) .== -1))

PS:
Splitting it into two lines and using views, does allocate less:

d = diff([0; x; 0])
@views tuple.(findall(d[1:end-1] .== 1), findall(d[2:end] .== -1))
4 Likes
8

for

do you mean this?

using IterTools
x = Bool[0,1,1,1,0,0,1,1,0,1]
twin=collect(partition(x,2,1))
p=findall(==((1,1)),twin)
tuple.(p,p.+1)
9

That indeed solves that part of the question

3-element Vector{Tuple{Int64, Int64}}:
 (2, 3)
 (3, 4)
 (7, 8)

But I want to connect the (2,3) - (3,4) → (2,4) to find the “true” stretches basically like the other answer

10

Found a way using Tranducers.jl, not entirely sure if this elegant :joy:
collect(Enumerate(), x) |> PartitionBy(x -> x[2] == true) |> Filter(x -> x[1][2] == true) |> Map(x-> (x[argmin(x)][1], x[argmax(x)][1])) |> collect

Not that bad with 49 allocs, but I guess pretty bad for readability lol

11

This is kind of like a run-length encoding, so you could use rle from StatsBase:

julia> x = Bool[1,1,0,0,1,1,0,1];

julia> vals, lens = rle(x)
(Bool[1, 0, 1, 0, 1], [2, 2, 2, 1, 1])

julia> run_starts = cumsum(lens) .- lens .+ 1
5-element Vector{Int64}:
 1
 3
 5
 7
 8

julia> run_stops = cumsum(lens)
5-element Vector{Int64}:
 2
 4
 6
 7
 8

julia> inds = findall(vals)
3-element Vector{Int64}:
 1
 3
 5

julia> collect(zip(run_starts[inds], run_stops[inds]))
3-element Vector{Tuple{Int64, Int64}}:
 (1, 2)
 (5, 6)
 (8, 8)

(of course, all these solutions are just putting the loop somewhere else :slight_smile:).

12 
map(vt->range(first.(vt)...),extrema.(filter(v->v[1][2],collect(IterTools.groupby(e->last(e),enumerate(x))))))

map(vt->first.(vt),extrema.(Iterators.filter(v->v[1][2],IterTools.groupby(e->last(e),enumerate(x)))))

julia> @btime map(vt->first.(vt),extrema.(Iterators.filter(v->v[1][2],IterTools.groupby(e->last(e),enumerate(x)))))
  942.857 ns (29 allocations: 2.09 KiB)
3-element Vector{Tuple{Int64, Int64}}:
 (2, 4)
 (7, 8)
 (10, 10)

julia> @btime collect(Enumerate(), x) |> PartitionBy(x -> x[2] == true) |> Filter(x -> x[1][2] == true) |> Map(x-> (x[argmin(x)][1], x[argmax(x)][1])) |> collect
  1.440 μs (59 allocations: 2.91 KiB)
3-element Vector{Tuple{Int64, Int64}}:
 (2, 4)
 (7, 8)
 (10, 10)

using IterTools
fvt(x)=first.(x)
fvt.(extrema.(Iterators.filter(v->v[1][2],groupby(e->last(e),enumerate(x)))))
1 Like
13

500×880 146 KB

-Programming history

2 Likes
14

Quite helpful in many cases though, things like findall, findfirst, map etc are easy to read and make code more compact.

15

Sorry if my joke wasn’t clear – the history of programming has been hiding GOTOs with loops and if-else because it adds clarity and brevity to the code. Functional programming hides loops and if-else to add further clarity and brevity.

This is almost always good!

4 Likes