JuliaData / JuliaData/PooledArrays.jl
improve median for pooled vectors
Open
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 49
- Forks
- 11
- PR merge metrics
- No merged PRs in 30d
Description
If length of pool is much smaller than the number of entries we can run the following (working code):
function median_fast(x::PooledVector)
n = length(x)
p = sortperm(x.pool)
counts = zeros(Int, length(p))
for v in x.refs
counts[v] += 1
end
cum = 0
for (j,i) in enumerate(p)
cum += counts[i]
if isodd(n)
if cum >= div(n + 1, 2)
return middle(x.pool[i])
end
else
if cum >= div(n, 2)
if cum == div(n, 2)
return middle(x.pool[i], x.pool[p[j+1]])
else
return middle(x.pool[i])
end
end
end
end
error("unreachable reached")
end
Example timings:
julia> x = PooledArray(rand(1:100, 10^8));
julia> @time median_fast(x);
0.063734 seconds (4 allocations: 1.781 KiB)
julia> @time median_fast(x);
0.070556 seconds (4 allocations: 1.781 KiB)
julia> @time median(x);
0.931585 seconds (3 allocations: 762.940 MiB, 9.86% gc time)
julia> @time median(x);
0.955555 seconds (3 allocations: 762.940 MiB, 14.29% gc time)
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Locate the existing median implementation for PooledVector and compare its behavior with the supplied median_fast example. Run the provided PooledArray timing scenario and verify that the median remains correct while avoiding the large allocation shown for median(x).
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100