10

On my first programming courses I was told I should use a set whenever I need to do things like remove duplicates of something. E.g.: to remove all duplicates from a vector, iterate through said vector and add each element to a set, then you're left with unique occurrences. However, I could also do that by adding each elemento to another vector and checking if the element already exists. I assume that depending on the language used there might be a difference in performance. But is there a reason to use a set other than that?

Basically: what kinds of algorithms require a set and shouldn't be done with any other container type?

  • 2
    Can you be more specific about what you mean when you use the term "set?" Are you referring to a C++ set? – Robert Harvey May 12 '17 at 0:04
  • Yes, actually, the "set" definition seems to be quite similar in most languages: a container that accepts only unique elements. – Floella May 12 '17 at 10:52
  • 6
    "adding each element to another vector and checking if the element already exists" - this is just implementing a set yourself. So you are asking why use a built-in feature when you can write one yourself by hand? – JacquesB May 12 '17 at 12:53
8

You are asking about sets specifically but I think your question is about a larger concept: abstraction. You are absolutely correct that you can use a Vector to do this (if you are using Java, use ArrayList instead.) But why stop there? What do you need the Vector for? You can do this all with arrays.

When ever you need to add an item to the array, you can simply loop over every element and if it's not there, you add it at the end. But, actually, you need to first check whether there's room in the array. If there isn't you'll need to create a new array that is larger and copy all the existing elements from the old array to the new array and then you can add the new element. Of course, you also need to update every reference to the old array to point to the new one. Got all that done? Great! Now what were we trying to accomplish again?

Or, instead you could use a Set instance and just call add(). The reason that sets exist is that they are an abstraction that is useful for lots of common problems. For example, let's say you want to track items and react when a new one is added. You call add() on a set and it returns true or false based on whether the set was modified. You could write that all by hand using primitives but why?

There might actually be a case where you have a List and you want to remove duplicates. The algorithm you propose is pretty much basically the slowest way you could do that. There are a couple of common quicker ways: bucketing them or sorting them. Or, you could add them to a set that implements one of those algorithms.

Early on in your career/education the focus is on building these algorithms and understanding them and it's important to do that. But that's not what professional developers do on a normal basis. They use these approaches to build much more interesting things and using pre-built and reliable implementations saves boatloads of time.

23

I assume that depending on the language used there might be a difference in performance. But is there a reason to use a set other than that?

Oh yes, (but it's not performance.)

Use a set when you can use one because not using it means you have to write extra code. Using a set makes what your doing easy to read. All that testing for uniqueness logic is hidden off somewhere else where you don't have to think about it. It's in a place that's already tested and you can trust that it works.

Write your own code to do that and you have to worry about it. Bleh. Who wants to do that?

Basically: what kinds of algorithms require a set and shouldn't be done with any other container type?

There is no algorithm that "shouldn't be done with any other container type". There are simply algorithms that can take advantage of sets. It's nice when you don't have to write extra code.

Now there is nothing particularly special about set in this regard. You should always use the collection that best fits your needs. In java I've found this picture to be helpful in making that decision. You'll notice that it has three different kinds of sets.

enter image description here

And as @germi rightly points out, if you use the right collection for the job your code becomes easier for others to read.

  • 6
    You kind of mentioned it already, but using a set also makes it easier for other people to reason about the code; they don't have to look at how it's populated to know that it only contains unique items. – germi May 12 '17 at 13:11
14

However, I could also do that by adding each elemento to another vector and checking if the element already exists.

If you do that, then you are implementing the semantics of a set on top of the vector datastructure. You're writing extra code (which could contain errors), and the result will be extremely slow if you have a lot of entries.

Why would you want to do that over using an existing, tested, efficient set implementation?

6

Software entities that represent real-world entities often are logically sets. For example, consider a Car. Cars have unique identifiers and group of cars forms a set. The set notion serves as a constraint on the collection of Cars that a program may know about and constraining data values is very valuable.

Also, sets have a very well defined algebra. If you have a set of Cars owned by George and a set owned by Alice, then the union is clearly the set owned by both George and Alice even if George and Alice both own the same car. So the algorithms that should use sets are those where the logic of the entities involved exhibit set characteristics. That turns out to be quite common.

How sets are implemented and how the uniqueness constraint is guaranteed is another matter. One hopes to be able to find an appropriate implementation for the set logic that eliminates duplicates given that sets are so fundamental to logic, but even if you do the implementation yourself, the uniqueness guarantee is intrinsic to the insertion of an item in a set and you should not have to be "checking if the element already exists".

  • "Checking if it already exists" is often essential for deduplication. Often objects are created from data. And you want only one object for identical data, to be reused by anyone creating an object from the same data. So you create a new object, check if it is in the set, if it's there you take the object from the set, otherwise you insert your object. If you just inserted the object, you would still have lots of identical objects. – gnasher729 May 12 '17 at 12:37
  • 1
    @gnasher729 the responsibility of the implementer of Set includes checking for existence, but a user of Set can for 1..100: set.insert(10) and still know that there is only one 10 in set – Caleth May 12 '17 at 13:05
  • The user can create one hundred different objects in ten groups of equal objects. After inserting there are ten objects in the set, but 100 objects still floating around. Deduplicating means there are ten objects in the set, and everyone uses those ten objects. Obviously you don't just need a test - you need a function that given an object, returns the matching object in the set. – gnasher729 May 12 '17 at 13:50
4

Apart from the performance characteristics (which are very significant, and shouldn't be so easily dismissed), Sets are very important as an abstract collection.

Could you emulate Set behavior (ignoring performance) with an Array? Yes, absolutely! Every time you insert, you can check if the element is already in the array, and then only add the element if it wasn't already found. But that's something you consciously have to be aware of, and remember every time you insert into your Array-Psuedo-Set. Oh what's that, you inserted once directly, without first checking for duplicates? Welp, your array has broken its invariant (that all elements are unique, and equivalently, that no duplicates exist).

So what would you do to get around that? You would create a new data type, call it (say, PsuedoSet), which wraps an internal Array, and exposes an insert operation publicly, which will enforce the uniqueness of elements. Since the wrapped array is only accessible through this public insert API, you guarantee that duplicates can never come about. Now add some hashing to improve performance of the contains checks, and sooner or later you'll realize that you implemented a full-out Set.

I would also respond with a statement and follow up question:

On my first programming courses I was told I should use an Array whenever I need to do things like store multiple ordered elements of something. E.g.: to store a collection of names of coworkers. However, I could also do that by allocating raw memory, and setting the value of the memory address given by the start pointer + some offset.

Could you use a raw pointer and fixed offsets to mimic an Array? Yes, absolutely! Every time you insert, you can check if the offset doesn't wander off the end of the allocated memory you're working with. But that's something you consciously have to be aware of, and remember every time you insert into your Pseudo-Array. Oh what's that, you inserted once directly, without first checking the offset? Welp, there's a Segmentation fault with your name on it!

So what would you do to get around that? You would create a new data type, call it (say, PsuedoArray), which wraps a pointer and a size, and exposes an insert operation publicly, which will enforce that the offset doesn't exceed the size. Since the wrapped data is only accessible through this public insert API, you guarantee that no buffer overflows can occur. Now add some other convenience functions (Array resizing, element deletion, etc.), and sooner or later you'll realize that you implemented a full-out Array.

3

There are all kinds of set based algorithms, particularly where you need to perform intersections and unions of sets and have the result be a set.

Set based algorithms are used heavily in various path finding algorithms, etc.

For a primer on set theory check out this link: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

If you need set semantics, use a set. It's going to avoid bugs due to spurious duplicates because you forgot to prune the vector/list at some stage, and it's going to be faster than you can do by constantly pruning your vector/list.

1

I actually find standard set containers to be mostly useless myself and prefer to just use arrays but I do it in a different way.

To compute set intersections, I iterate through the first array and mark elements with a single bit. Then I iterate through the second array and look for marked elements. Voila, set intersection in linear time with far less work and memory than a hash table, e.g. Unions and differences are equally simple to apply using this method. It does help that my codebase revolves around indexing elements rather than duplicating them (I duplicate indices to elements, not the data of the elements themselves) and rarely needs anything to be sorted, but I haven't used a set data structure in years as a result.

I also have some evil bit-fiddling C code I use even when the elements offer no data field for such purposes. It involves using the memory of the elements themselves by setting the most significant bit (which I never use) for the purpose of marking traversed elements. That's pretty gross, don't do that unless you're really working at near-assembly level, but just wanted to mention how it can be applicable even in cases when elements don't provide some field specific for traversal if you can guarantee that certain bits will never be used. It can compute a set intersection between 200 million elements (bout 2.4 gigs of data) in less than a second on my dinky i7. Try doing a set intersection between two std::set instances containing a hundred million elements each in the same time; doesn't even come close.

That aside...

However, I could also do that by adding each elemento to another vector and checking if the element already exists.

That checking to see if an element already exists in the new vector is generally going to be a linear time operation, which will make the set intersection itself a quadratic operation (explosive amount of work the bigger the input size). I recommend the technique above if you just want to use plain old vectors or arrays and do it in a way that scales wonderfully.

Basically: what kinds of algorithms require a set and shouldn't be done with any other container type?

None if you ask my biased opinion if you're talking about it at the container level (as in a data structure specifically implemented to provide set operations efficiently), but there are plenty that require set logic at the conceptual level. For example, let's say you want to find the creatures in a game world which are capable of both flying and swimming, and you have flying creatures in one set (whether or not you actually use a set container) and ones that can swim in another. In that case, you want a set intersection. If you want creatures that can either fly or are magical, then you use a set union. Of course you don't actually need a set container to implement this, and the most optimal implementation generally doesn't need or want a container specifically designed to be a set.

Going Off Tangent

All right, I got some nice questions from JimmyJames regarding this set intersection approach. It's kinda veering off subject but oh well, I'm interested in seeing more people use this basic intrusive approach to set intersection so that they're not building whole auxiliary structures like balanced binary trees and hash tables just for the purpose of set operations. As mentioned the fundamental requirement is that the lists shallow copy elements so that they are indexing or pointing to a shared element that can be "marked" as traversed by the pass through the first unsorted list or array or whatever to then pick up on the second pass through the second list.

However, this can be accomplished practically even in a multithreading context without touching the elements provided that:

  1. The two aggregates contain indices to the elements.
  2. The range of indices is not too large (say [0, 2^26), not billions or more) and are reasonably densely occupied.

This allows us to use a parallel array (just one bit per element) for the purpose of set operations. Diagram:

enter image description here

Thread synchronization only needs to be there when acquiring a parallel bit array from the pool and releasing it back to the pool (done implicitly when going out of scope). The actual two loops to perform the set operation need not involve any thread syncs. We don't even need to use a parallel bit pool if the thread can just allocate and free the bits locally, but the bit pool can be handy to generalize the pattern in codebases that fit this kind of data representation where central elements are often referenced by index so that each thread doesn't have to bother with efficient memory management. Prime examples for my area are entity-component systems and indexed mesh representations. Both frequently need set intersections and tend to refer to everything stored centrally (components and entities in ECS and vertices, edges, and polygons in indexed meshes) by index.

If the indices are not densely occupied and sparsely scattered, then this is still applicable with a reasonable sparse implementation of the parallel bit/boolean array, like one which only stores memory in 512-bit chunks (64 bytes per unrolled node representing 512 contiguous indices) and skips allocating completely vacant contiguous blocks. Chances are you are already using something like this if your central data structures are sparsely occupied by the elements themselves.

enter image description here

... similar idea for a sparse bitset to serve as a parallel bit array. These structures also lend themselves towards immutability since it's easy to shallow copy chunky blocks which don't need to be deep copied to create a new immutable copy.

Again set intersections between hundreds of millions of elements can be done in under a second using this approach on a very average machine, and that's within a single thread.

It can also be done in under half the time if the client doesn't need a list of elements for the resulting intersection, like if they only want to apply some logic to the elements found in both lists, at which point they can just pass a function pointer or functor or delegate or whatever to be called back to process ranges of elements that intersect. Something to this effect:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... or something to this effect. The most expensive part of the pseudocode in the first diagram is intersection.append(index) in the second loop, and that applies even for std::vector reserved to the size of the smaller list in advance.

What If I Deep Copy Everything?

Well, stop that! If you need to do set intersections, it implies that you are duplicating data to intersect against. Chances are that even your tiniest objects aren't smaller than a 32-bit index. It is very possible to reduce the addressing range of your elements to 2^32 (2^32 elements, not 2^32 bytes) unless you actually need more than ~4.3 billion elements instantiated, at which point a totally different solution is needed (and that definitely isn't using set containers in memory).

Key Matches

How about cases where we need to do set operations where the elements aren't identical but could have matching keys? In that case, same idea as above. We just need to map each unique key to an index. If the key is a string, for example, then interned strings can do just that. In those cases a nice data structure like a trie or a hash table is called for to map string keys to 32-bit indices, but we don't need such structures in order to do the set operations on the resulting 32-bit indices.

A whole lot of very cheap and straightforward algorithmic solutions and data structures open up like these when we can work with indices to elements in a very reasonable range, not the full addressing range of the machine, and so it's often more than worth it to be able to obtain a unique index for each unique key.

I Love Indices!

I love indices just as much as pizza and beer. When I was in my 20s, I got really into C++ and started designing all kinds of fully standard-compliant data structures (including the tricks involved to disambiguate a fill ctor from a range ctor at compile-time). In retrospect that was a large waste of time.

If you revolve your database around storing elements centrally in arrays and indexing them rather than storing them in a way that's fragmented and potentially across the entire addressable range of the machine, then you can end up exploring a world of algorithmic and data structure possibilities by just designing containers and algorithms that revolve around plain old int or int32_t. And I found the end result to be so much more efficient and easy to maintain where I wasn't constantly transferring elements from one data structure to another to another to another.

Some example use cases when you can just assume that any unique value of T has a unique index and will have instances residing in a central array:

Multithreaded radix sorts which work well with unsigned integers for indices. I actually have a multithreaded radix sort which takes about 1/10th of the time to sort a hundred million elements as Intel's own parallel sort, and Intel's is already 4 times faster than std::sort for such large inputs. Of course Intel's is much more flexible since it's a comparison-based sort and can sort things lexicographically, so it's comparing apples to oranges. But here I often only need oranges, like I might do a radix sort pass just to achieve cache-friendly memory access patterns or filter out duplicates quickly.

Ability to build linked structures like linked lists, trees, graphs, separate chaining hash tables, etc. without heap allocations per node. We can just allocate the nodes in bulk, parallel to the elements, and link them together with indices. The nodes themselves just become a 32-bit index to the next node and stored in a big array, like so:

enter image description here

Friendly for parallel processing. Often linked structures aren't so friendly for parallel processing, since it's awkward at the very least to try to achieve parallelism in tree or linked list traversal as opposed to, say, just doing a parallel for loop through an array. With the index/central array representation, we can always go to that central array and process everything in chunky parallel loops. We always have that central array of all elements we can process this way, even if we only want to process some (at which point you might process the elements indexed by a radix-sorted list for cache-friendly access through the central array).

Can associate data to each element on the fly in constant-time. As with the case of the parallel array of bits above, we can easily and extremely cheaply associate parallel data to elements for, say, temporary processing. This has use cases beyond temporary data. For example, a mesh system might want to allow users to attach as many UV maps to a mesh as they want. In such a case, we can't just hard-code how many UV maps there will be in every single vertex and face using an AoS approach. We need to be able to associate such data on the fly, and parallel arrays are handy there and so much cheaper than any kind o sophisticated associative container, even hash tables.

Of course parallel arrays are frowned upon due to their error-prone nature of keeping parallel arrays in sync with each other. Whenever we remove an element at index 7 from the "root" array, for example, we likewise have to do the same thing for the "children". However, it's easy enough in most languages to generalize this concept to a general-purpose container so that the tricky logic to keep parallel arrays in sync with each other only need exist in one place throughout the entire codebase, and such a parallel array container can use the sparse array implementation above to avoid wasting lots of memory for contiguous vacant spaces in the array to be reclaimed upon subsequent insertions.

More Elaboration: Sparse Bitset Tree

All right, I got a request to elaborate some more which I think was sarcastic, but I'm gonna do so anyway cause it's so much fun! If people want to take this idea to whole new levels, then it is possible to perform set intersections without even linearly looping through N+M elements. This is my ultimate data structure which I've been using for ages and basically models set<int>:

enter image description here

The reason it can perform set intersections without even inspecting each element in both lists is because a single set bit at the root of the hierarchy can indicate that, say, a million contiguous elements are occupied in the set. By just inspecting one bit, we can know that N indices in the range, [first,first+N) are in the set, where N could be a very large number.

I actually use this as a loop optimizer when traversing occupied indices, because let's say there are 8 million indices occupied in the set. Well, normally we would have to access 8 million integers in memory in that case. With this one, it can potentially just inspect a few bits and come up with index ranges of occupied indices to loop through. Further, the ranges of indices it comes up with are in sorted order which makes for very cache-friendly sequential access as opposed to, say, iterating through an unsorted array of indices used to access the original element data. Of course this technique fares worse for extremely sparse cases, with the worst-case scenario being like every single index being an even number (or every one being odd), in which case there are no contiguous regions whatsoever. But in my use cases at least, that practically never happens.

  • 2
    "To compute set intersections, I iterate through the first array and mark elements with a single bit. Then I iterate through the second array and look for marked elements." You mark them where, on the second array? – JimmyJames Dec 8 '17 at 20:02
  • 1
    Oh I see, you are 'interning' the data a single object representing each value. It's an interesting technique for a subset of use cases for sets. I see no reason why not to implement this approach as an operation on your own set class. – JimmyJames Dec 8 '17 at 20:11
  • 2
    "It's an intrusive solution that violates encapsulation in some cases..." Once I figured out what you meant, that occurred to me but then I think it needn't. If you had a class that managed this behavior, the index objects could be independent from all the element data and be shared across all instances of your collection type. i.e. there would be one master set of data and then each instance would point back to the master set. Multi-threading would need more complexity but I think if would be manageable. – JimmyJames Dec 8 '17 at 20:32
  • 1
    It seems like this would be potentially useful in a database solution but I don't know whether there are any implemented in this way. Thanks for putting this out here. You got my mind working. – JimmyJames Dec 8 '17 at 22:12
  • 1
    Could you elaborate a little more? ;) I'll check it out when I have a some (a lot) of time. – JimmyJames Dec 11 '17 at 16:02
-1

To check whether a set containing n elements contains another element X takes typically constant time. To check whether an array containing n elements contains another element X takes typically O (n) time. That's bad, but if you want to remove the duplicates from n items, suddenly it takes O (n) in time instead of O (n^2); 100,000 items will bring your computer to its knees.

And you are asking for more reasons? "Apart from the shooting, did you enjoy the evening, Mrs. Lincoln?"

  • 2
    I think you might want to read that over again. Taking O(n) time instead of O(n²) time is generally considered a good thing. – JimmyJames May 12 '17 at 13:23
  • Maybe you stood on your head while reading this? OP asked "why not just take an array". – gnasher729 May 12 '17 at 13:48
  • 2
    Why is going from O(n²) to O(n) going to bring a 'computer to it's knees'? I must have missed that in my class. – JimmyJames May 12 '17 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.