Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
I need to do a lot of calculations involving sets. There are relatively few values in the "universe" of candidates that could appear in any of the sets, but potentially very many such sets (they mi...
#1: Initial revision
by
Karl Knechtel
·
2023-09-14T03:46:15Z (8 months ago)
Optimized representation for sets?
I need to do a lot of calculations involving sets. There are relatively few values in the "universe" of candidates that could appear in any of the sets, but potentially very many such sets (they might not initially be distinct, either). My language has a built-in (or standard library) representation for sets, but it's designed to be general-purpose - a set could contain any object (or at least any hashable object, for hash-based set representations). This makes it very inefficient: it takes a lot of space to store an internal structure (tree or hash table) along with individual objects (or at least pointers thereto), and a simple element membership test needs to either traverse a tree or check a hash table and then also compare an object for equality. To say nothing of basic union and intersection operations. I don't need this flexibility and do need more efficiency. Is there a simple way to optimize this, taking advantage of the fact that the universe of values I need in my sets is fixed (and small)?