Class: Zipfian

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

Constant Summary collapse

VERSION = 
"0.0.3"
@@global_mutex = 
Mutex.new
@@mutexes = 
{}
@@h = 
{}
@@cdf = 
{}

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n, s, cache = false) ⇒ Zipfian

Returns a new instance of Zipfian.



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
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/zipfian.rb', line 11

def initialize n, s, cache = false
  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]

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

  key = [n, s]
  mutex = nil
  if cache
    @@global_mutex.synchronize do
      mutex = @@mutexes[key] ||= Mutex.new
    end
    mutex.synchronize do
      @h   = @@h[key]   ||= compute_h.call
      @cdf = @@cdf[key] ||= compute_cdf.call
    end
  else
    @@global_mutex.synchronize do
      # Do not create mutex
      mutex = @@mutexes[key]
    end
    if mutex
      mutex.synchronize do
        @h   = @@h[key]   || compute_h.call
        @cdf = @@cdf[key] || compute_cdf.call
      end
    else
      @h   = compute_h.call
      @cdf = compute_cdf.call
    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

Class Method Details

.cached ⇒ Object 



74
75
76
77
78
79
80
81
82
 
# File 'lib/zipfian.rb', line 74

def self.cached
  ret = []
  @@global_mutex.synchronize do
    @@mutexes.keys.each do |key|
      ret << { :n => key.first, :s => key.last }
    end
  end
  ret
end

Instance Method Details

#cdf(k) ⇒ Object 



65
66
67
68
 
# File 'lib/zipfian.rb', line 65

def cdf k
  check_rank k
  @cdf[k]
end

#inspect ⇒ Object 



53
54
55
56
57
58
 
# File 'lib/zipfian.rb', line 53

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

#pmf(k) ⇒ Object 



60
61
62
63
 
# File 'lib/zipfian.rb', line 60

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

#sample ⇒ Object 



70
71
72
 
# File 'lib/zipfian.rb', line 70

def sample
  binary_search_index @cdf, rand
end