Opened 4 years ago
Closed 3 years ago
#2418 closed enhancement (done)
More efficient implementation of median
Reported by: | gkronber | Owned by: | gkronber |
---|---|---|---|
Priority: | medium | Milestone: | HeuristicLab 3.3.13 |
Component: | Common | Version: | 3.3.11 |
Keywords: | Cc: |
Description
The current implementation of median() creates an array and uses Array.Sort to find the median element. Sorting is however not stricly necessary as the median (or any quantile) can be determined using an O(n) algorithm.
Change History (7)
comment:1 Changed 3 years ago by gkronber
- In place implementation that alters the array: see §8.5 select(), "Numerical Recipes in C"
- Non-destructive selection (is 10x slower than select()): see §8.5 selip(), "Numerical Recipes in C"
- For k << N (e.g. the 10 smallest or largest value in an array of 1000 elements): Use Heapsort "make a single pass through an array of length N while saving the m largest elements." "Only log m, rather than m, comparisons are required every time a new element is added to the candidate list."
comment:2 Changed 3 years ago by gkronber
comment:3 Changed 3 years ago by gkronber
- Status changed from new to accepted
comment:4 Changed 3 years ago by gkronber
- Owner changed from gkronber to mkommend
- Status changed from accepted to reviewing
comment:5 Changed 3 years ago by mkommend
- Owner changed from mkommend to gkronber
- Status changed from reviewing to readytorelease
comment:6 Changed 3 years ago by gkronber
comment:7 Changed 3 years ago by gkronber
- Resolution set to done
- Status changed from readytorelease to closed
Note: See
TracTickets for help on using
tickets.