module Quartiles

Buckets provides utility computation methods for computation of quartile statistics

Constants

EFF_BUCKETS

Public Class Methods

quartile_points(buckets) click to toggle source
# File lib/tlsh/quartiles.rb, line 6
def quartile_points(buckets)
  spl = spr = 0
  q1 = 0

  p1 = EFF_BUCKETS / 4 - 1
  p2 = EFF_BUCKETS / 2 - 1
  p_end = EFF_BUCKETS - 1

  buckets_cpy = buckets.dup[0..EFF_BUCKETS]

  cut_left = []
  cut_right = []

  l = 0
  r = p_end
  loop do
    ret = partition(buckets_cpy, l, r)
    if ret > p2
      r = ret - 1
      cut_right[spr] = ret
      spr += 1
    elsif ret < p2
      l = ret + 1
      cut_left[spl] = ret
      spl += 1
    else
      q1 = buckets_cpy[p2]
      break
    end
  end

  cut_left[spl] = p2 - 1
  cut_right[spr] = p2 + 1

  q2 = get_q2(buckets_cpy, cut_left, spl, p1)
  q3 = get_q3(buckets_cpy, cut_right, spr, p_end)

  [q1, q2, q3]
end

Private Class Methods

get_q2(buckets, cut_left, spl, p1) click to toggle source
# File lib/tlsh/quartiles.rb, line 83
def get_q2(buckets, cut_left, spl, p1)
  i = l = 0
  while i <= spl
    r = cut_left[i]

    if r > p1
      loop do
        ret = partition(buckets, l, r)
        if ret > p1
          r = ret - 1
        elsif ret < p1
          l = ret + 1
        else
          return buckets[p1]
        end
      end
    end

    i += 1
  end
end
get_q3(buckets, cut_right, spr, p_end) click to toggle source
# File lib/tlsh/quartiles.rb, line 105
def get_q3(buckets, cut_right, spr, p_end)
  p3 = EFF_BUCKETS - EFF_BUCKETS / 4 - 1
  q3 = 0

  i = 0
  r = p_end
  while i <= spr
    l = cut_right[i]
    if l < p3
      loop do
        ret = partition(buckets, l, r)
        if ret > p3
          r = ret - 1
        elsif ret < p3
          l = ret + 1
        else
          q3 = buckets[p3]
          break
        end
      end
      break
    elsif l > p3
      r = l
    else
      q3 = buckets[p3]
    end

    i += 1
  end
  q3
end
partition(buffer, left, right) click to toggle source
# File lib/tlsh/quartiles.rb, line 48
def partition(buffer, left, right)
  return left if left == right

  if left + 1 == right
    if buffer[left] > buffer[right]
      buffer[right], buffer[left] = buffer[left], buffer[right]
    end
    return left
  end

  ret = left

  partition_buffer(buffer, ret, left, right)
end
partition_buffer(buffer, ret, left, right) click to toggle source
# File lib/tlsh/quartiles.rb, line 63
def partition_buffer(buffer, ret, left, right)
  pivot = (left + right) >> 1
  value = buffer[pivot]

  buffer[pivot] = buffer[right]
  buffer[right] = value

  (left..right).each do |i|
    if buffer[i] < value
      buffer[i], buffer[ret] = buffer[ret], buffer[i]
      ret += 1
    end

    buffer[right] = buffer[ret]
    buffer[ret] = value
  end

  ret
end