Support for Intersection of multiple Sets at the same time
Nobody has claimed this yet.
- Dominant language
- Markdown
- Stars
- 6.6k
- Forks
- 1.7k
- Avg merge
- 16h 14m
- Merged PRs (30d)
- 1
Description
Currently the method intersection of HashSet and BTreeSet only support an intersection between two sets. If you want to intersect multiple sets, for example 3, you'll need to calculate the intersection between the first two, collect them into another set and calculate the intersection between that immediate result and the third set. This is very intense on computation, memory usage and lines of code.
I'd like to suggest the following:
- Change the current implementations of the
Intersectionstructs to contain a list of other sets to intersect with instead of a reference to a single other set. This applies tostd::collections::btree_set::Intersectionas well asstd::collections::hash_set::Intersection. - Implement
intersect_many(orintersect_multiple) onHashSetandBTreeSetwhich take a list of other sets to all intersect with the current one. - Add
intersectandintersect_many(orintersect_multiple) to theIntersectionstructs as well. Those can only be called if theIntersectionhasn't been iterated over yet. Otherwise, they'll panic.
If (3.) is implemented, the "list of sets to intersect with" will need to be a Vec in order to be growable after creation. For performance reasons, the third suggestion could be dropped and the "list" can instead be a reference to the provided slice.
The current implementation of {Hash,BTree}Set::intersection would need to be changed to pass &[other] instead of other.
While this request should be relatively easy to implement for HashSet (self.others.iter().all(|set| set.contains(elt)), implementing it for BTreeSet could result in a lot more code.
Unresolved Questions:
- Naming:
intersect_manyvsintersect_multiplevs ??? - Don't implement the third suggestion (functions on the
Intersectionstruct) in favor of using an allocation free slice-reference instead of aVec?
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the HashSet and BTreeSet intersection APIs and their Intersection structs described in the issue. Review the unresolved naming and allocation questions before proposing an RFC direction; done means the API design is agreed and the requested multi-set behavior is specified clearly enough for implementation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- api
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100