Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Fast implementation of finite and complement sets in Ruby
Ruby
tree: 168f61a0d5

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
benchmark
lib
spec
Gemfile
Gemfile.lock
README.md
Rakefile

README.md

Cantor

Fast implementation of finite and complement sets in Ruby

Constructors

  • Cantor.empty
    Finite set that contains no elements

  • Cantor.build(enum)
    Finite set containing each element in enum, whose domain of discourse is unrestricted

  • Cantor.absolute(enum, universe)
    Finite set containing each element in enum, whose domain of discourse is universe

  • Cantor.universal
    Infinite set containing every value in the universe

  • Cantor.complement(enum)
    Set containing every value except those in enum. Finite when enum is infinite. Infinite when enum is finite

Operations

  • xs.include?(x)
  • xs.exclude?(x)
  • xs.finite?
  • xs.infinite?
  • xs.empty?
  • xs.size
  • xs.replace(ys)
  • ~xs
  • xs.complement
  • xs + xs
  • xs | ys
  • xs.union(ys)
  • xs - ys
  • xs.difference(ys)
  • xs ^ ys
  • xs.symmetric_difference(ys)
  • xs & ys
  • xs.intersection(ys)
  • xs <= ys
  • xs.subset?(ys)
  • xs < ys
  • xs.proper_subset?(ys)
  • xs >= ys
  • xs.superset?(ys)
  • xs > ys
  • xs.proper_superset?(ys)
  • xs.disjoint?(ys)
  • xs == ys

Performance

Sets with a finite domain of discourse are represented using a bit string of 2|U| bits, where |U| is the size of the domain. This provides nearly O(1) constant-time implementation using bitwise operations for all of the above set operations.

The bit string is represented as an Integer, but as the domain grows larger than 0.size * 8 - 2 items, the type is automatically expanded to a Bignum. Bitwise operations on Bignums are O(|U|), which is still be significantly faster than using the default Set library.

Sets with an unrestricted domain of discourse are implemented using a Hash. Unary operations and membership tests are O(1) constant-time. Binary operations on these sets is close to that of the default Set library.

Benchmarks

These benchmarks aren't intended to be useful. While they indicate the worst-case performance for Cantor, they probably don't show the worst case for the standard Set library.

Note "Relative" indicates Cantor sets with an infinite domain of discourse. This includes Cantor.build, Cantor.universal, and Cantor.complement. "Absolute" sets are Cantor sets with a finite domain of discourse, built from Cantor.absolute.

Something went wrong with that request. Please try again.