IntSet (int_set v1.5.0) View Source
Efficiently store and index a set of non-negative integers.
A set can be constructed using IntSet.new/0:
iex> IntSet.new
#IntSet<[]>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)
trueSets also implement Collectable, so it can collect values in any context
that a list can:
iex> Enum.into([1, 2, 3], IntSet.new())
#IntSet<[1, 2, 3]>The inspect/1 implementation for IntSet sorts the members, which makes
it way easier to write doctests:
iex> IntSet.new([3, 1, 2])
#IntSet<[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>>
iex> IntSet.new(<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1>>)
#IntSet<[5]>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
With the use of IntSet.bitstring/2, and IntSet.new/1,
you can serialize this collection very efficiently.
Remember to pass the byte_align: true option into IntSet.bitstring/2 when you do this;
most encoding schemes like byte-aligned data.
iex> IntSet.new([4, 8, 15, 16, 23, 42]) |> IntSet.bitstring(byte_align: true) |> Base.encode16()
"088181000020"
iex> Base.decode16!("088181000020") |> IntSet.new()
#IntSet<[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
Specs
t()
Link to this section Functions
Get a bitstring representing the members of a set.
Examples
iex> IntSet.new(0) |> IntSet.bitstring()
<<1::1>>
iex> IntSet.new(5) |> IntSet.bitstring()
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1>>
iex> IntSet.new() |> IntSet.bitstring()
<<>>You can also provide a :byte_align option,
which will pad the end of the binary with zeroes until you're at a nice round n-byte size.
By default this options is false.
iex> IntSet.new(5) |> IntSet.bitstring(byte_align: true)
<<0::1, 0::1, 0::1, 0::1, 0::1, 1::1, 0::1, 0::1>>Specs
delete(t(), non_neg_integer()) :: t()
Remove a number from the int set.
Examples
iex> set = IntSet.new(5)
#IntSet<[5]>
iex> IntSet.delete(set, 5)
#IntSet<[]>Specs
Returns a set that is int_set1 without the members of int_set2.
Examples
iex> IntSet.difference(IntSet.new([1, 2]), IntSet.new([2, 3, 4]))
#IntSet<[1]>Specs
Checks if int_set and int_set2 have no members in common.
Examples
iex> IntSet.disjoint?(IntSet.new([1, 2]), IntSet.new([3, 4]))
true
iex> IntSet.disjoint?(IntSet.new([1, 2]), IntSet.new([2, 3]))
falseSpecs
Checks if two sets are equal
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]))
falseSpecs
Find all elements that are in both int_set1 and int_set2.
Examples
iex> IntSet.intersection(IntSet.new([1, 2]), IntSet.new([2, 3, 4]))
#IntSet<[2]>
iex> IntSet.intersection(IntSet.new([1, 2]), IntSet.new([3, 4]))
#IntSet<[]>Specs
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
iex> IntSet.new(0) |> IntSet.inverse(1)
#IntSet<[]>
iex> IntSet.new(0) |> IntSet.inverse(8)
#IntSet<[1, 2, 3, 4, 5, 6, 7]>
iex> IntSet.new() |> IntSet.inverse(3)
#IntSet<[0, 1, 2]>
iex> IntSet.new() |> IntSet.inverse(9)
#IntSet<[0, 1, 2, 3, 4, 5, 6, 7, 8]>Specs
new() :: t()
Create an empty int set.
Examples
iex> IntSet.new
#IntSet<[]>Specs
new(non_neg_integer() | Enum.t() | bitstring()) :: t()
Create an int set with some starting value.
Examples
You can create a set with a single starting value.
iex> IntSet.new(0)
#IntSet<[0]>You can also provide an enumerable of integers to start with.
iex> IntSet.new([1, 2, 3])
#IntSet<[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<[0]>
iex> IntSet.new(<<0b1000_1000>>)
#IntSet<[0, 4]>
iex> IntSet.new(<<0 :: 1>>)
#IntSet<[]>Specs
put(t(), non_neg_integer()) :: t()
Add a value to the int set.
Examples
iex> set = IntSet.new()
#IntSet<[]>
iex> IntSet.put(set, 0)
#IntSet<[0]>Specs
Create a new set that contains all of the elements of both x and y.
Examples
iex> a = IntSet.new(7)
iex> b = IntSet.new(4)
iex> IntSet.union(a, b)
#IntSet<[4, 7]>