View Source IntSet (IntSet v2.0.0)
Efficiently store and index a set of non-negative integers.
A set can be constructed using IntSet.new/0
:
iex> IntSet.new()
IntSet.new([])
An IntSet
obeys the same set semantics as MapSet
, and provides
constant-time operations for insertion, deletion, and membership checking.
Use Enum.member?/2
to check for membership.
iex> IntSet.new(3) |> Enum.member?(3)
true
Sets also implement Collectable
, so it can collect values in any context
that a list can:
iex> Enum.into([1, 2, 3], IntSet.new())
IntSet.new([1, 2, 3])
Working with applications that use bitstrings becomes way easier,
because IntSet.new/1
accepts a bitstring,
and IntSet.bitstring/2
can return one.
iex> IntSet.new(5) |> IntSet.bitstring()
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1, 0::1, 0::1>>
iex> IntSet.new(<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1>>)
IntSet.new([5])
performance
Performance
An IntSet
is significantly faster than Elixir's MapSet
at set operations (union, intersection, difference, equality),
but slower at everything else.
The case for memory usage is similar:
better than MapSet
for set operations,
worse for everything else.
Op | MapSet | IntSet | Comparison |
---|---|---|---|
new | 4.8K | 2.46K | 1.95x slower |
member? | 6.78M | 2.93M | 2.31x slower |
put | 4.19M | 1.15M | 3.66x slower |
union | 156.4K | 944.31K | 6.04x faster |
difference | 48.09 | 891.27K | 18.53x faster |
intersection | 14.03K | 905.70K | 64.54x faster |
equal? | 0.26M | 2.41M | 9.25x faster |
There is a benchmark checked into the project repo
at perf/performance_test.exs
.
You can run it with mix run
to see some results for yourself.
serialization
Serialization
With the use of IntSet.bitstring/2
, and IntSet.new/1
,
you can serialize this collection very efficiently.
iex> IntSet.new([4, 8, 15, 16, 23, 42]) |> IntSet.bitstring() |> Base.encode16()
"088181000020"
iex> Base.decode16!("088181000020") |> IntSet.new()
IntSet.new([4, 8, 15, 16, 23, 42])
Link to this section Summary
Functions
Get a bitstring representing the members of a set.
Remove a number from the int set.
Returns a set that is int_set1
without the members of int_set2
.
Checks if int_set
and int_set2
have no members in common.
Checks if two sets are equal
Find all elements that are in both int_set1
and int_set2
.
Returns a set of size n with all members not in the given IntSet.
Create an empty int set.
Create an int set with some starting value.
Add a value to the int set.
Create a new set that contains all of the elements of both x and y.
Link to this section Types
@opaque t()
Link to this section Functions
Get a bitstring representing the members of a set.
examples
Examples
iex> IntSet.new(0) |> IntSet.bitstring()
<<128>>
iex> IntSet.new(5) |> IntSet.bitstring()
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1, 0::1, 0::1>>
iex> IntSet.new() |> IntSet.bitstring()
<<>>
@spec delete(t(), non_neg_integer()) :: t()
Remove a number from the int set.
examples
Examples
iex> set = IntSet.new(5)
IntSet.new([5])
iex> IntSet.delete(set, 5)
IntSet.new([])
Returns a set that is int_set1
without the members of int_set2
.
examples
Examples
iex> IntSet.difference(IntSet.new([1, 2]), IntSet.new([2, 3, 4]))
IntSet.new([1])
Checks if int_set
and int_set2
have no members in common.
examples
Examples
iex> IntSet.disjoint?(IntSet.new([1, 2]), IntSet.new([3, 4]))
true
iex> IntSet.disjoint?(IntSet.new([1, 2]), IntSet.new([2, 3]))
false
Checks if two sets are equal
examples
Examples
iex> IntSet.equal?(IntSet.new([1, 2]), IntSet.new([2, 1, 1]))
true
iex> IntSet.equal?(IntSet.new([1, 2]), IntSet.new([3, 4]))
false
Find all elements that are in both int_set1
and int_set2
.
examples
Examples
iex> IntSet.intersection(IntSet.new([1, 2]), IntSet.new([2, 3, 4]))
IntSet.new([2])
iex> IntSet.intersection(IntSet.new([1, 2]), IntSet.new([3, 4]))
IntSet.new([])
@spec inverse(t(), non_neg_integer()) :: t()
Returns a set of size n with all members not in the given IntSet.
You can visualize this operation as calling IntSet.difference/2
with the first argument being a full IntSet of size n.
examples
Examples
iex> IntSet.new(0) |> IntSet.inverse(1)
IntSet.new([])
iex> IntSet.new(0) |> IntSet.inverse(8)
IntSet.new([1, 2, 3, 4, 5, 6, 7])
iex> IntSet.new() |> IntSet.inverse(3)
IntSet.new([0, 1, 2])
iex> IntSet.new() |> IntSet.inverse(9)
IntSet.new([0, 1, 2, 3, 4, 5, 6, 7, 8])
@spec new() :: t()
Create an empty int set.
examples
Examples
iex> IntSet.new
IntSet.new([])
@spec new(non_neg_integer() | Enum.t() | bitstring()) :: t()
Create an int set with some starting value.
examples
Examples
You can create a set with a single starting value.
iex> IntSet.new(0)
IntSet.new([0])
You can also provide an enumerable of integers to start with.
iex> IntSet.new([1, 2, 3])
IntSet.new([1, 2, 3])
Lastly, you can initialize the set with a bit string. Binary strings are interpreted as little-endian, with the very first bit of the string representing the number zero.
iex> IntSet.new(<<1 :: 1>>)
IntSet.new([0])
iex> IntSet.new(<<0b1000_1000>>)
IntSet.new([0, 4])
iex> IntSet.new(<<0 :: 1>>)
IntSet.new([])
@spec put(t(), non_neg_integer()) :: t()
Add a value to the int set.
examples
Examples
iex> set = IntSet.new()
IntSet.new([])
iex> IntSet.put(set, 0)
IntSet.new([0])
Create a new set that contains all of the elements of both x and y.
examples
Examples
iex> a = IntSet.new(7)
iex> b = IntSet.new(4)
iex> IntSet.union(a, b)
IntSet.new([4, 7])