### 18 releases

0.4.0 | Feb 18, 2020 |
---|---|

0.3.6 | Dec 11, 2019 |

0.3.4 | Nov 10, 2019 |

0.3.2 | May 21, 2019 |

0.3.0 | Nov 4, 2018 |

#**906** in Algorithms

**96** downloads per month

**MIT**license

145KB

3K
SLoC

# SdSet

Set theory applied on sorted and deduplicated slices. Much performance! Such Wow!

API Documentation can be found on docs.rs.

stands for `sdset`

which is a little bit too long.`sorted-deduplicated-slices-set`

## Performances

Note about the tests, which are done on ranges of integer, if it ends with:

, the first slice contains`two_slices_big`

and the second has`0``..``100``1``..``101`

, the first contains`two_slices_big2`

and the second has`0``..``100``51``..``151`

, the first contains`two_slices_big3`

and the second has`0``..``100``100``..``200`

, the first contains`three_slices_big`

, the second has`0``..``100`

and the third has`1``..``101``2``..``102`

, the first contains`three_slices_big2`

, the second has`0``..``100`

and the third has`34``..``134``67``..``167`

, the first contains`three_slices_big3`

, the second has`0``..``100`

and the third has`100``..``200``200``..``300`

These slices of runs of integer are useful when they overlap, we can see how performances changes when different parts of the slices overlaps.

For more informations on "Why is there no really big slices benchmarks ?", you can see my response on /r/rust.

To run the benchmarks you must enable the

feature.`unstable`

`$`` cargo bench`` --`features unstable

Note that the

set operations does not need many allocations so it starts with a serious advantage. For more information you can see the benchmarks variance.`sdset`

are benchmarks that uses `_btree`*two* or *three*

s which contains runs of integers (see above), the `BTreeSet`

s creations are not taken into account. The set operations are done on these sets and the result is accumulated in a final `BTreeSet`

.`Vec`

are benchmarks that uses `_fnv`*two* or *three*

s which contains runs of integers (see above), it uses a custom `HashSet`

named `Hasher`

that is specialized for little values like integers, the `fnv`

s creations are not taken into account. The set operations are done on these sets and the result is accumulated in a final `HashSet`

.`Vec`

The

benchmarks are available for the union set operation only, it consist of a `_vec`

which is populated with the elements of `Vec`*two* or *three* slices (see above), sorted and deduplicated.

The

and `duo`

measurements are the implementations that are part of this crate, the first one can only do set operations on `multi`**two** sets and the second one can be used for any given number of sets.

### Histograms

Histograms can be generated using the benchmarks by executing the following command:

`$`` export CARGO_BENCH_CMD=``'`cargo bench --features unstable`'`
`$`` ./gen_graphs.sh xxx.bench`

This is much more easier to read statistics and to see how

is more performant on already sorted and deduplicated slices than any other kind of collection.`sdset`

#### Dependencies

~170KB