Line data    Source code

       1             : package main
       2             : 
       3             : import (
       4             :         "cmp"
       5             :         "slices"
       6             : )
       7             : 
       8             : const increment = 50 // ops/sec
       9             : 
      10             : // findOptimalSplit computes and returns a value that separates the given pass
      11             : // and fail measurements optimally, such that the number of mis-classified
      12             : // passes (pass values that fall above the split) and fails (fail values that
      13             : // fall below the split) is minimized.
      14             : //
      15             : // The following gives a visual representation of the problem:
      16             : //
      17             : //                                   Optimal partition (=550) -----> |
      18             : //                                                               |
      19             : //        Passes:   o          o        o              o o o oo  |
      20             : //        Fails:                         x             x         |x    x  x     x x        x
      21             : //        |---------|---------|---------|---------|---------|----|----|---------|---------|---------|---> x
      22             : //        0        100       200       300       400       500   |   600       700       800       900
      23             : //
      24             : // The algorithm works by computing the error (i.e. mis-classifications) at
      25             : // various points along the x-axis, starting from the origin and increasing by
      26             : // the given increment.
      27           1 : func findOptimalSplit(pass, fail []int) int {
      28           1 :         // Not enough data to compute a sensible score.
      29           1 :         if len(pass) == 0 || len(fail) == 0 {
      30           1 :                 return -1
      31           1 :         }
      32             : 
      33             :         // Maintain counters for the number of incorrectly classified passes and
      34             :         // fails. All passes are initially incorrect, as we start at 0. Conversely,
      35             :         // no fails are incorrectly classified, as all scores are >= 0.
      36           1 :         pCount, fCount := len(pass), 0
      37           1 :         p, f := make([]int, len(pass)), make([]int, len(fail))
      38           1 :         copy(p, pass)
      39           1 :         copy(f, fail)
      40           1 : 
      41           1 :         // Sort the inputs.
      42           1 :         slices.Sort(p)
      43           1 :         slices.Sort(f)
      44           1 : 
      45           1 :         // Find the global min and max.
      46           1 :         min, max := p[0], f[len(fail)-1]
      47           1 : 
      48           1 :         // Iterate over the range in increments.
      49           1 :         var result [][]int
      50           1 :         for x := min; x <= max; x = x + increment {
      51           1 :                 // Reduce the count of incorrect passes as x increases (i.e. fewer pass
      52           1 :                 // values are incorrect as x increases).
      53           1 :                 for len(p) > 0 && p[0] <= x {
      54           1 :                         pCount--
      55           1 :                         p = p[1:]
      56           1 :                 }
      57             : 
      58             :                 // Increase the count of incorrect fails as x increases (i.e. more fail
      59             :                 // values are incorrect as x increases).
      60           1 :                 for len(f) > 0 && f[0] < x {
      61           1 :                         fCount++
      62           1 :                         f = f[1:]
      63           1 :                 }
      64             : 
      65             :                 // Add a (x, score) tuple to result slice.
      66           1 :                 result = append(result, []int{x, pCount + fCount})
      67             :         }
      68             : 
      69             :         // Sort the (x, score) result slice by score ascending. Tie-break by x
      70             :         // ascending.
      71           1 :         slices.SortFunc(result, func(a, b []int) int {
      72           1 :                 if v := cmp.Compare(a[1], b[1]); v != 0 {
      73           1 :                         return v
      74           1 :                 }
      75           1 :                 return cmp.Compare(a[0], b[0])
      76             :         })
      77             : 
      78             :         // If there is more than one interval, split the difference between the min
      79             :         // and the max.
      80           1 :         splitMin, splitMax := result[0][0], result[0][0]
      81           1 :         for i := 1; i < len(result); i++ {
      82           1 :                 if result[i][1] != result[0][1] {
      83           1 :                         break
      84             :                 }
      85           1 :                 splitMax = result[i][0]
      86             :         }
      87             : 
      88           1 :         return (splitMin + splitMax) / 2
      89             : }