<commit_before>require 'test/unit'
require 'set'
require 'benchmark'

# A classic implementation of the union-find collection. This will only
# work for integer values. See below for an interesting "variation" of
# this collection.
class UnionFind
  def initialize
    @size = 0
    @parents = []
    @sizes = []
  end

  def find(k)
    return k if @parents[k].nil?
    @parents[k] == k ? k : find(@parents[k])
  end

  def union(x, y)
    resize!([x, y].max) if [x, y].max > @size
    set1, set2 = find(x), find(y)
    return if set1 == set2 # same set already

    @sizes[set1] = 1 if @sizes[set1].nil?
    @sizes[set2] = 1 if @sizes[set2].nil?

    if @sizes[set1] > @sizes[set2]
      @sizes[set1] += @sizes[set2]
      @parents[set2] = set1
    else
      @sizes[set2] += @sizes[set1]
      @parents[set1] = set2
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  private
  def resize!(m)
    return if m < @size
    @size = m
  end

  alias same_component? same?
end


# Dict-based implementation of a union-find. This will accept
# any object but won't be memory constrained.
class UnionFindDict
  def initialize
    @parents = {}
    @sizes = {}
    @sizes.default = 1
  end

  # In this case find() will always return the object with the larger
  # component and not a component #id.
  def find(k)
    return k if @parents[k].nil?
    @parents[k] == k ? k : find(@parents[k])
  end

  def union(x, y)
    set1, set2 = find(x), find(y)
    return if set1 == set2 # same set already

    if @sizes[set1] > @sizes[set2]
      @sizes[set1] += @sizes[set2]
      @parents[set2] = set1
    else
      @sizes[set2] += @sizes[set1]
      @parents[set1] = set2
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  alias same_component? same?
end


# Implementation of a probabilistic version of a union-find datastructure.
#
# This collection ensures that if !@same?(x, y) then we are sure that
# x and y belong to different components, however the contrary is not
# guaranteed since there may be collisions in the internal buffer.
#
# This collection however accepts any kind of hashable object such as
# strings and is memory-constrained.
#
# This implementation is optimistical, in the sense that it assumes that there
# won't be collisions among the contained objects. However this won't be
# necessarily true in a real-world application, so a proper tuning of the max
# buffer size is required.
class UnionFindProbabilistic
  # Initializes a new union-find data structure. The max size parameter
  # refers to the internal buffer, and not to the max number of items this
  # collection can hold. Hence proper tuning is required to avoid collisions.
  def initialize(max_size=2048)
    # TODO: I'm fairly sure we can steal some ideas from bloom filters and
    # calculate max_size automatically as a measure of the expected error rate
    @max_size = max_size
    @size = 0
    @parents = []
    @sizes = []
  end

  def find(k)
    _find(k.hash % @max_size)
  end

  def union(x, y)
    _union(x.hash % @max_size, y.hash % @max_size)
  end

  def same?(x, y)
    find(x) == find(y)
  end

  private

  def _find(k)
    return k if @parents[k].nil?
    @parents[k] == k ? k : _find(@parents[k])<commit_msg>Explain what's the purpose of max_buffer_size<commit_after>require 'test/unit'
require 'set'
require 'benchmark'

# A classic implementation of the union-find collection. This will only
# work for integer values. See below for an interesting "variation" of
# this collection.
class UnionFind
  def initialize
    @size = 0
    @parents = []
    @sizes = []
  end

  def find(k)
    return k if @parents[k].nil?
    @parents[k] == k ? k : find(@parents[k])
  end

  def union(x, y)
    resize!([x, y].max) if [x, y].max > @size
    set1, set2 = find(x), find(y)
    return if set1 == set2 # same set already

    @sizes[set1] = 1 if @sizes[set1].nil?
    @sizes[set2] = 1 if @sizes[set2].nil?

    if @sizes[set1] > @sizes[set2]
      @sizes[set1] += @sizes[set2]
      @parents[set2] = set1
    else
      @sizes[set2] += @sizes[set1]
      @parents[set1] = set2
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  private
  def resize!(m)
    return if m < @size
    @size = m
  end

  alias same_component? same?
end


# Dict-based implementation of a union-find. This will accept
# any object but won't be memory constrained.
class UnionFindDict
  def initialize
    @parents = {}
    @sizes = {}
    @sizes.default = 1
  end

  # In this case find() will always return the object with the larger
  # component and not a component #id.
  def find(k)
    return k if @parents[k].nil?
    @parents[k] == k ? k : find(@parents[k])
  end

  def union(x, y)
    set1, set2 = find(x), find(y)
    return if set1 == set2 # same set already

    if @sizes[set1] > @sizes[set2]
      @sizes[set1] += @sizes[set2]
      @parents[set2] = set1
    else
      @sizes[set2] += @sizes[set1]
      @parents[set1] = set2
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  alias same_component? same?
end


# Implementation of a probabilistic version of a union-find datastructure.
#
# This collection ensures that if !@same?(x, y) then we are sure that
# x and y belong to different components, however the contrary is not
# guaranteed since there may be collisions in the internal buffer.
#
# This collection however accepts any kind of hashable object such as
# strings and is memory-constrained.
#
# This implementation is optimistical, in the sense that it assumes that there
# won't be collisions among the contained objects. However this won't be
# necessarily true in a real-world application, so a proper tuning of the max
# buffer size is required.
class UnionFindProbabilistic

  # Initializes a new union-find data structure. The max buffer size
  # refers to the internal buffer, and not to the max number of items this
  # collection can hold. Hence proper tuning is required to avoid collisions.
  #
  # The buffer will start from a small size and will grow automatically to
  # receive new items.
  def initialize(max_buffer_size=2048)
    # TODO: I'm fairly sure we can steal some ideas from bloom filters and
    # calculate max_size automatically as a measure of the expected error rate
    @max_buffer_size = max_buffer_size
    @size = 0
    @parents = []
    @sizes = []
  end

  def find(k)
    _find(k.hash % @max_buffer_size)
  end

  def union(x, y)
    _union(x.hash % @max_buffer_size, y.hash % @max_buffer_size)
  end

  def same?(x, y)
    find(x) == find(y)
  end

  private

  def _find(k)
    return k if @parents[k].nil?
    @parents[k] == k ? k : _find(@parents[k])
{'fraction_non_alphanumeric': 0.10541353383458647, 'fraction_numerical': 0.012330827067669173, 'mean_word_length': 3.057962172056132, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3914173', 'n_tokens_mistral': 2290, 'n_tokens_neox': 2203, 'n_words': 820}