# Fastest way to partition array, given a condition

**URL:** <https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243>\
**Category:** Performance\
**Tags:** sort\
**Created:** [July 24, 2021, 6:55pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243 "2021-07-24T18:55:47Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 6:55pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/1 "2021-07-24T18:55:47Z")

</div>

I need to sort (usually small, i. e. 5 to 20 elements, but the algorithm cannot scale badly) arrays, but only partially. That is, I need that the elements get split into elements smaller than a cutoff, and elements greater than a cutoff, and I need the number of elements smaller than the cutoff. It must be inplace, and single-threaded.

The fastest I could do for now is this:

```julia
julia> function partialsort_cutoff!(x,cutoff)
         iswap = 1
         for i in eachindex(x)
           if x[i] <= cutoff
             if iswap != i
               x[iswap], x[i] = x[i], x[iswap]
             end
             iswap = iswap + 1
           end
         end
         return iswap - 1
       end
partialsort_cutoff! (generic function with 1 method)

julia> @benchmark partialsort_cutoff!(y,0.5) setup=(y=rand(20)) evals=1
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max): 88.000 ns … 444.000 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 172.000 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 172.809 ns ± 25.730 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

                         ▂ ▄▁▁▆▂▇▃█▃▃█▃█▂▆▁▂▄ ▃                  
  ▂▂▂▁▂▂▂▂▂▂▃▃▃▃▄▄▅▄▆▅▆▇▇██████████████████████▇█▆▅▇▅▆▄▅▃▃▄▃▃▃▂ ▅
  88 ns Histogram: frequency by time 236 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

Anyone can think of a faster alternative?

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [July 24, 2021, 7:03pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/2 "2021-07-24T19:03:10Z")

</div>

Small style suggestion, you can use `x[iswap], x[i] = x[i], x[iswap]` instead of three lines.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 7:09pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/3 "2021-07-24T19:09:11Z")

</div>

accepted 🙂

---

<div class="post-metadata">

**Author:** ![eliassno](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eliassno/32/18917_2.png) [@eliassno](https://discourse.julialang.org/u/eliassno)\
**Post date:** [July 24, 2021, 7:29pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/4 "2021-07-24T19:29:15Z")

</div>

Why do I get different timing results? On Julia Version 1.5.3:

```julia
julia> @btime partialsort_cutoff!(y,0.5) setup=(y=copy($x)) evals=1
  0.001 ns (0 allocations: 0 bytes)
7

```

EDIT:  
Timings are the same until `length(x) == 134`:

```julia
julia> x = rand(134);

julia> @btime partialsort_cutoff!(y,0.5) setup=(y=copy($x)) evals=1
  100.000 ns (0 allocations: 0 bytes)
65

```

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 7:33pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/5 "2021-07-24T19:33:40Z")

</div>

That is a strange result, and certainly it is not meaningful. I’m in Julia 1.6.2, for if that matters.

Anyway, it is probably better to benchmark the function with:

```julia
julia> @benchmark partialsort_cutoff!(y,0.5) setup=(y=rand(20)) evals=1
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max): 88.000 ns … 444.000 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 172.000 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 172.809 ns ± 25.730 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

                         ▂ ▄▁▁▆▂▇▃█▃▃█▃█▂▆▁▂▄ ▃                  
  ▂▂▂▁▂▂▂▂▂▂▃▃▃▃▄▄▅▄▆▅▆▇▇██████████████████████▇█▆▅▇▅▆▄▅▃▃▄▃▃▃▂ ▅
  88 ns Histogram: frequency by time 236 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

(updated the original post)

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [July 24, 2021, 7:44pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/6 "2021-07-24T19:44:19Z")

</div>

Is the initial distribution on number totally random ?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 7:57pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/7 "2021-07-24T19:57:49Z")

</div>

Yet, it is.

What, on the other side, might be useful, is that I don’t need the values greater than the cutoff. I would be happy if I got the elements smaller than the cutoff, and the number of elements smaller than the cutoff. But I don’t know if something can be faster than swapping the elements directly.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [July 24, 2021, 7:59pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/8 "2021-07-24T19:59:24Z")

</div>

> [@lmiq](#):
>
> Anyone can think of a faster alternative?

This should minimize the number of swaps but the overall higher complexity doesn’t seem to pay off unless the swaps are more expensive than in the benchmark.

```julia
function partialsort_cutoff2!(x, cutoff)
    i, j = extrema(eachindex(x))
    while true
        while i < j && x[i] <= cutoff
            i += 1
        end
        while j > i && x[j] > cutoff
            j -= 1
        end
        if j <= i
            return i - 1
        end
        x[i], x[j] = x[j], x[i]
    end
end

```

Edit: There’s a corner case bug if all elements are lower than the cutoff.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 24, 2021, 8:04pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/9 "2021-07-24T20:04:47Z")

</div>

> [@lmiq](#):
>
> I need that the elements get split into elements smaller than a cutoff, and elements greater than a cutoff,

This is called “partitioning” the array, and is a [subroutine of the quicksort algorithm](https://en.wikipedia.org/wiki/Quicksort). See the [`Base.partition!` function](https://github.com/JuliaLang/julia/blob/master/base/sort.jl#L549-L570).

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 8:04pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/10 "2021-07-24T20:04:48Z")

</div>

Thanks. But the swaps are pretty cheap, yes. They are swaps of a struct of shape:

```julia
struct S
  i::Int 
  x::Float64
  v::SVector{3,Float64}
end

```

and the sorting is on the `x` values.

Probably a little bit more expensive to swap, but still very cheap.

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [July 24, 2021, 8:13pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/11 "2021-07-24T20:13:28Z")

</div>

> [@lmiq](#):
>
> What, on the other side, might be useful, is that I don’t need the values greater than the cutoff.

`filter!` ?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 8:17pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/12 "2021-07-24T20:17:44Z")

</div>

I cannot deallocate the remaining of the array, because it will be reused. Could that be adapted to that situation?

two comments:

the `Base.partition!` is interesting, but I will have to understand exactly how to use it in this case.

Also, `filter!` seems to be fast. Another function to study how it is implemented, even if to adapt to what I need here.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [July 24, 2021, 8:19pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/13 "2021-07-24T20:19:07Z")

</div>

> [@lmiq](#):
>
> But I don’t know if something can be faster than swapping the elements directly.

If you use the `partition!` algorithm you don’t need to swap; you can just do a single assignment into the lower half.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 8:21pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/14 "2021-07-24T20:21:07Z")

</div>

Thanks all! I have some clear directions to study alternatives. I need to take care of the kid now 🙂

I will post what I get from those suggestions asap.

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [July 24, 2021, 8:29pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/15 "2021-07-24T20:29:58Z")

</div>

> [@lmiq](#):
>
> I cannot deallocate the remaining of the array, because it will be reused. Could that be adapted to that situation?
> 
> Also, `filter!` seems to be fast. Another function to study how it is implemented, even if to adapt to what I need here.

The original:

```julia
function filter!(f, a::AbstractVector)
    j = firstindex(a)
    for ai in a
        @inbounds a[j] = ai
        j = ifelse(f(ai), nextind(a, j), j)
    end
    j > lastindex(a) && return a
    if a isa Vector
        resize!(a, j-1)
        sizehint!(a, j-1)
    else
        deleteat!(a, j:lastindex(a))
    end
    return a
end

```

adapted to your needs:

```julia
function yourFilter!(f, a::AbstractVector)
    j = firstindex(a)
    for ai in a
        @inbounds a[j] = ai
        j = ifelse(f(ai), nextind(a, j), j)
    end
    return j-1
end

```

You can check if `@inbounds` is good for your swapping too.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 11:29pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/16 "2021-07-24T23:29:57Z")

</div>

Thanks for that. But I realized now that the way I have things implemented now, I actually need the swapping.

I will see how faster is the `partition!` function.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2021, 11:46pm UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/17 "2021-07-24T23:46:53Z")

</div>

The adapted `Base.Sort.partition!` function appears to be _slightly_ faster than what I originally had. If someone sees anything else to improve, I’ll appreciate. But I guess that if that is what is implemented by default in QuickSort, I guess it can’t get much faster.

```julia
julia> @benchmark partition!(y,0.5) setup=(y=rand(20)) evals=1
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max): 71.000 ns … 14.398 μs ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 157.000 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 159.097 ns ± 145.189 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

                            ▂ ▁▅▂▆▂▂█▄▂▇▃▆▂▁▅ ▃
  ▂▁▁▂▁▂▂▂▂▂▃▂▂▃▃▃▃▄▅▄▄▆▅█▇█████████████████████▇█▆▅▇▄▄▆▄▄▃▃▃▃▃ ▅
  71 ns Histogram: frequency by time 216 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark partialsort_cutoff!(y,0.5) setup=(y=rand(20)) evals=1
BechmarkTools.Trial: 10000 samples with 1 evaluations.
 Range (min … max): 76.000 ns … 31.006 μs ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 169.000 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 172.485 ns ± 309.801 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

                           ▁ ▃ ▄▁▆▂▇▃▇▃▇▃█▃▆▁▆▁▂ ▁
  ▂▁▁▂▂▁▂▂▂▂▂▂▂▃▃▃▃▄▃▅▄▆▅▇▆███████████████████████▆█▅▇▅▅▄▄▃▄▃▃▃ ▅
  76 ns Histogram: frequency by time 229 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

> **Code**
>
> ```julia
> using BenchmarkTools
> 
> function partition!(v::AbstractVector, cutoff)
> i, j = 0, length(v)+1
> @inbounds while true
> i += 1; j -= 1
> while 
> v[i] <= cutoff
> i += 1  
> end
> while 
> v[j] > cutoff
> j -= 1 
> end
> i >= j && break
> v[i], v[j] = v[j], v[i]
> end
> return j
> end
> 
> function partialsort_cutoff!(x,cutoff)
> iswap = 1
> @inbounds for i in eachindex(x)
> if x[i] <= cutoff
> if iswap != i
> x[iswap], x[i] = x[i], x[iswap]
> end
> iswap = iswap + 1
> end
> end
> return iswap - 1
> end
> 
> ```

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [July 25, 2021, 7:14am UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/18 "2021-07-25T07:14:15Z")

</div>

> [@lmiq](#):
>
> The adapted `Base.Sort.partition!` function appears to be _slightly_ faster than what I originally had.

Do you have guarantees that you have values both below and above the cutoff? Otherwise you will go out of bounds in one of the while loops. (The Base `partition!` avoids this with the `selectpivot!` semantics.)

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [July 25, 2021, 10:02am UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/19 "2021-07-25T10:02:09Z")

</div>

> [@eliassno](#):
>
> Why do I get different timing results?

As a rule of thumb, subnanosecond timings don’t make any sense. Usually this means there is constant propagation going on, so that the result is effectively computed at compile time and `@btime` is trying to benchmark a function which directly returns a constant value. See [Manual · BenchmarkTools.jl](https://juliaci.github.io/BenchmarkTools.jl/dev/manual/#Understanding-compiler-optimizations)

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 25, 2021, 10:09am UTC](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243/20 "2021-07-25T10:09:27Z")

</div>

Indeed, I only tested that in the toy example, so I missed that. I’ll add checking limits to the loops, as the use of a pivot does not seem to be exactly what I need. But maybe that will narrow the diference to the initial implementation even further.

@GunnarFarneback now I notice that is exactly what you posted [above](https://discourse.julialang.org/t/fastest-way-to-partially-sort-array/65243/8). Thanks for that.

> [@giordano](#):
>
> As a rule of thumb, subnanosecond timings don’t make any sense. Usually this means there is constant propagation going on,

Probably what he is seen deserves a new thread, because if he ran exactly the code I posted that should not be happening.

[Next page](https://discourse.julialang.org/t/fastest-way-to-partition-array-given-a-condition/65243.md?page=2)