#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 20 months 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 20 months ago by gkronber

r13033:

  • implemented O(n) algorithm for median (and general quantiles) determination.
  • Comparing output of new implementation with naive implementation (as well as performance) in the unit test
  • let's see if all samples still produce the same results...

merge this after #2488

comment:3 Changed 20 months ago by gkronber

  • Status changed from new to accepted

comment:4 Changed 19 months ago by gkronber

  • Owner changed from gkronber to mkommend
  • Status changed from accepted to reviewing

comment:5 Changed 19 months ago by mkommend

  • Owner changed from mkommend to gkronber
  • Status changed from reviewing to readytorelease

r13059: corrected spelling mistake in median implementation.

Reviewed r13033.

comment:6 Changed 19 months ago by gkronber

r13150: merged r13033 and r13059 from trunk to stable branch

comment:7 Changed 19 months ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.