search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
36 stars 16 forks source link

More efficient implementation of median #2418

Closed HeuristicLab-Trac-Bot closed 8 years ago

HeuristicLab-Trac-Bot commented 9 years ago

Issue migrated from trac ticket # 2418

milestone: HeuristicLab 3.3.13 | component: Common | priority: medium | resolution: done

2015-07-07 12:34:35: @gkronber created the issue

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-19 10:57:28: @gkronber commented

  • 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."
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-19 16:14:16: @gkronber commented

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

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-19 16:30:43: @gkronber changed status from new to accepted

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-21 12:28:13: @gkronber changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-21 12:28:13: @gkronber changed owner from @gkronber to @mkommend

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-23 11:27:36: @mkommend changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-23 11:27:36: @mkommend changed owner from @mkommend to @gkronber

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-23 11:27:36: @mkommend commented

r13059: corrected spelling mistake in median implementation.

Reviewed r13033.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-13 20:59:58: @gkronber commented

r13150: merged r13033 and r13059 from trunk to stable branch

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-13 21:00:13: @gkronber changed status from readytorelease to closed

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-13 21:00:13: @gkronber removed resolution