Efficient Memory Deduplication

memory_dedup.rb

# A memory efficient deduplication class used in cases where a
# duplicate object can only occur within n objects of each other.
class MemoryDedup

  # Returns a new deduper.
  #
  # == Options
  # * <tt>:size</tt> - the number of objects to store in the cache
  def initialize(options = {})
    @size = options{:size} || 1000
    @current = {}
    @next = {}
  end

  # Returns true if the object has been seen in the past :size unique
  # objects, false otherwise.
  def exists?(obj)
    if (2 * @current.size) > @size
      @current = @next
      @next = {}
    end
    @next[obj] = true
    if @current.has_key?(obj)
      return true
    else
      @current[obj] = true
      return false
    end
  end

end