Class: Zipfian

Inherits:
Object
  • Object
show all
Defined in:
lib/zipfian.rb,
lib/zipfian/version.rb

Constant Summary collapse

VERSION = 
"0.0.2"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n, s) ⇒ Zipfian

Returns a new instance of Zipfian.



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/zipfian.rb', line 6

def initialize n, s
  unless n > 0 && n.is_a?(Integer)
    raise ArgumentError.new("Number of elements must be a positive integer")
  end
  unless s > 0
    raise ArgumentError.new("Exponent must be a positive number")
  end

  @n   = n
  @s   = s
  sums = [0]
  @h   = (1..@n).inject(0) { |sum, i| sums[i] = sum + 1.0 / (i ** @s) }
  @cdf = (0..@n).map { |i| sums[i] / @h }

  class << @cdf
    def binary_search_index v
      l = 0
      r = self.length - 2

      while (c = (l + r) / 2) && l < r
        if v < self[c]
          r = c - 1
        elsif v > self[c]
          l = c + 1
        else
          return c
        end
      end

      v < self[c] ? c : c + 1
    end
  end
end

Instance Attribute Details

#n ⇒ Object (readonly)

Returns the value of attribute n.



4
5
6
 
# File 'lib/zipfian.rb', line 4

def n
  @n
end

#s ⇒ Object (readonly)

Returns the value of attribute s.



4
5
6
 
# File 'lib/zipfian.rb', line 4

def s
  @s
end

Instance Method Details

#cdf(k) ⇒ Object 



52
53
54
55
 
# File 'lib/zipfian.rb', line 52

def cdf k
  check_rank k
  @cdf[k]
end

#inspect ⇒ Object 



40
41
42
43
44
45
 
# File 'lib/zipfian.rb', line 40

def inspect
  {
    :N => @n,
    :s => @s
  }.inspect
end

#pmf(k) ⇒ Object 



47
48
49
50
 
# File 'lib/zipfian.rb', line 47

def pmf k
  check_rank k
  1.0 / ((k ** @s) * @h)
end

#sample ⇒ Object 



57
58
59
 
# File 'lib/zipfian.rb', line 57

def sample
  @cdf.binary_search_index rand
end