Class: TopN

Inherits:
Object
  • Object
show all
Defined in:
lib/top_n.rb

Overview

Note:

Note that while the number of keys is restricted, the values are not. This can cause memory issues if many values are added to the same key. If this is the type of data you are tracking, you may need a different solution.

This class tracks the top (or bottom) N values for a set of keys.

As keys and values are added, only the largest (or smallest) keys will be recorded. As larger (or smaller) keys are added, unneeded items are removed.

Keys may be any object that is comparable with < and >. Values may be any object, and are not processed beyond appending them to an internal list.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ TopN

Create a new TopN object. Options available:

Examples:

Create with default options

topn = TopN.new

Create with a maximum size of 10, and track smaller values

topn = TopN.new(maxsize: 10, direction: :bottom)

Parameters:

  • options (Hash) (defaults to: {}) —

    the options used to configure the TopN object.

Options Hash (options):

  • :maxsize (Fixnum) —

    The maximum number of keys to track. Must be a positive Fixnum. Defaults to 100.

  • :direction (Symbol) —

    Configure the direction. If this is :top, the largest keys will be maintained. If :bottom, the smallest keys will be maintained. Any other value throws an exception. Defaults to :top.

Raises:

  • (ArgumentError) —

    if an invalid value is detected for any option.



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/top_n.rb', line 63

def initialize(options = {})
  options = {
    maxsize: 100,
    direction: :top,
  }.merge(options)

  @maxsize = options[:maxsize]
  @direction = options[:direction]
  @data = {}
  @size = 0
  @threshold_key = nil

  unless [:top, :bottom].include?(@direction)
    raise ArgumentError.new("direction must be :top or :bottom")
  end

  unless @maxsize.is_a?Fixnum
    raise ArgumentError.new("maxsize must be a Fixnum")
  end

  if @maxsize <= 0
    raise ArgumentError.new("maxsize must be >= 1")
  end
end

Instance Attribute Details

#data ⇒ Hash (readonly)

The currently tracked data as one blob. This is tied to the current implementation, so its use is not recommended.

Returns:

  • (Hash) —

    the internal data structure containing the keys and values. The keys to the returned Hash are the tracked keys, and the values at those keys is the list of values.



39
40
41
 
# File 'lib/top_n.rb', line 39

def data
  @data
end

#direction ⇒ Symbol (readonly)

The configured direction.

Returns:

  • (Symbol) —

    either :top or :bottom.



24
25
26
 
# File 'lib/top_n.rb', line 24

def direction
  @direction
end

#maxsize ⇒ Fixnum (readonly)

The maxinum number of keys which will be tracked.

Returns:

  • (Fixnum) —

    the configured maximum number of keys to be tracked.



20
21
22
 
# File 'lib/top_n.rb', line 20

def maxsize
  @maxsize
end

#size ⇒ FixNum (readonly)

The current number of keys we are tracking.

Returns:

  • (FixNum) —

    the count, which will be 0 up to :maxsize.



28
29
30
 
# File 'lib/top_n.rb', line 28

def size
  @size
end

#threshold_key ⇒ Object (readonly)

The current value of the minimum (:top) or maximum (:bottom) key.

Returns:

  • (Object) —

    the threshold key.



32
33
34
 
# File 'lib/top_n.rb', line 32

def threshold_key
  @threshold_key
end

Instance Method Details

#add(key, value) ⇒ Array?

Add a key, value pair.

If the key already exists, the value will be appended to the existing list of values at that key.

If an existing (key, value) is permitted, and will result in the list of values at that key having the same value multiple times.

large to be tracked.

Parameters:

  • key (Object) —

    the key, which must be compariable with < and >.

  • value (Object) —

    the value, which is added to the key’s list of values. Adding the same value to a key multiple times results in duplicate values being recorded.

Returns:

  • (Array) —

    if the value was added to the key’s list.

  • (nil) —

    if the value was not added because the key is too small or



106
107
108
109
110
111
112
 
# File 'lib/top_n.rb', line 106

def add(key, value)
  if @direction == :top
    add_top(key, value)
  else
    add_bottom(key, value)
  end
end

#find(key) ⇒ Array<Object>?

Find and return the list of values for a key.

Returns:

  • (Array<Object>) —

    the list of values for ‘key’.

  • (nil) —

    if the key does not exist.



120
121
122
 
# File 'lib/top_n.rb', line 120

def find(key)
  @data[key]
end

#keys ⇒ Array<Object>

Return the list of currently tracked keys.

Returns:

  • (Array<Object>) —

    the list of values for this key. Order is not guaranteed to match the oder which they were added.



129
130
131
 
# File 'lib/top_n.rb', line 129

def keys
  @data.keys
end