implement Statistics.median #973
Conversation
|
Any chance to push this forward? |
This implements `Statistics.median` based on the existing bitonic sorting, avoiding unnecessary allocation. While it is generally suboptimal to sort the whole array, the compiler manages to skip some branches since only the middle element(s) are used. Thus `median` is generally faster than `sort`. Using a dedicated median selection network could yield better performance and might be considered for future improvement.
stev47
force-pushed
the
feature/median
branch
from
d1f0d28 to
2461b2f
Compare
updated the MR, waiting for review |
|
This pull request implements median for While testing random static vectors is useful, defined tests would be welcome. In particular, one could replicate the the tests in Statistics.jl for |
ok, I've added the tests from Statistics.jl |
|
@mkitti , Any chance t ping another reviewer to push this? |
|
I tried benchmarking it and there seems to be an issue: julia> a = [1, 10, 2, 1.2, -19, 12];
julia> sa = SVector{length(a)}(a);
julia> @btime median($a)
24.433 ns (2 allocations: 112 bytes)
1.6
julia> @btime median($sa)
515.203 ns (5 allocations: 176 bytes)
1.6From a quick look it seems like |
Can you try in a fresh session? I cannot reproduce your timings (Julia 1.11.2): julia> using StaticArrays
julia> using Statistics
julia> a = [1, 10, 2, 1.2, -19, 12];
julia> sa = SVector{length(a)}(a);
julia> @btime median($a)
31.548 ns (2 allocations: 112 bytes)
1.6
julia> @btime median($sa)
8.529 ns (0 allocations: 0 bytes)
1.6similar for both Julia 1.10.7 and Julia 1.12.0-DEV.1793 at commit 5ee67b8551. |
This implements
Statistics.medianbased on the existing bitonicsorting, avoiding unnecessary allocation.
While it is generally suboptimal to sort the whole array, the compiler
manages to skip some branches since only the middle element(s) are used.
Thus
medianis generally faster thansort.Using a dedicated median selection network could yield better
performance and might be considered for future improvement.