Module: KnnBall::Stat

Defined in:
lib/knnball/stat.rb

Class Method Summary collapse

Class Method Details

.median!(data, &cmp_block) ⇒ Object

sort an array with the goal of having the median at the middle.

Values on the left will be lesser or equal to the median and values on the right higher than or equal to the median.



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/knnball/stat.rb', line 17

def self.median!(data, &cmp_block)
  midx = median_index(data)
  left = 0
  right = data.size-1
  pidx = pivot!(data, midx, 0, data.size-1, &cmp_block)
  while pidx != midx do
    if(pidx < midx)
      left = pidx + 1
    else
      right = pidx - 1
    end
    pidx = pivot!(data, midx, left, right, &cmp_block)
  end
  return data[midx]
end

.median_index(data) ⇒ Object

Retrieve the median index of an array. array.count == 0 -> 0 array.count == 1 -> 0 array.count == 2 -> 1 array.count == 3 -> 1



61
62
63
 
# File 'lib/knnball/stat.rb', line 61

def self.median_index(data)
  (data.size % 2 == 0) ? (data.size / 2) : (data.size - 1) / 2
end

.pivot!(data, pivot, left = 0, right = data.size-1, &cmp_block) ⇒ Object

Returns the final index of the pivot.

Parameters:

  • data —

    an array of data that will be changed in place

  • pivot —

    index of the pivot value in data

Returns:

  • the final index of the pivot



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/knnball/stat.rb', line 36

def self.pivot!(data, pivot, left = 0, right = data.size-1, &cmp_block)
  value = data[pivot]
  cmp_block = Proc.new {|a, b| a <=> b} if cmp_block.nil?
  
  # push pivot value at the end of data
  data[pivot], data[right] = data[right], data[pivot]
  
  # swap position if current idx <= pivot value
  for i in (left..right-1)
    if(cmp_block.call(data[i], value) < 1)
      data[left], data[i] = data[i], data[left]
      left = left + 1
    end
  end
  
  # push the pivot value just after the last index
  data[left], data[right] = data[right], data[left]
  return left
end