Python Data Structures: Sets, Frozensets, and Multisets (Bags)

Key Takeaways

hey there this is Dan and today I want to talk about the set data structure in Python basically we're going to talk about what is a set in a computer science uh sense and uh what can you do with it and how can you implement sets in Python because there's a couple of ways for you to use a set data structure in Python there's uh different kinds of sets there's the regular set there's also multi sets are also called bags and there's a difference between mutable and immutable sets and I just want to give you a quick overview of uh what's available in Python sort of what the general idea is and then just to give you some pointers so you can dive in and learn some more all right so let's start with a really simple example so what I'm going to do here is I'm going to define a very simple set and then we can talk about some of the properties that a set data structure has so what I did here was I created a new set object in Python that holds all of the vowels right just the the characters uh a e i o u we inspect that you can see that python actually prints us this out a little bit differently because the syntax that I used up here is kind of old school there's actually a short hand to creating sets and it looks exactly like this so I could have created the exact same set in uh in the same way so this sort of looks like uh a dictionary but the difference to a dictionary expression is that you don't have the columns so a set doesn't really map keys to values it's it's just a collection of objects that it holds all right so now we've created a set object now what actually makes a set special you know what what do we need it for can we just use a list or can't we just use a dictionary so here's the key distinctions number one a set is an unordered collection of items a list is an ordered collection of items so if I had this list this is pretty much the worst choice of elements here because I it sucks to type it out um so if I had this list it uh actually has an order to it and you've seen this effect where uh the set doesn't retain the order but the list does you can see that here because when I initially created this set you can see here I passed it an ordered list of elements like I actually gave it a list and what python spit out the second time it kind of flipped the order around right because the order in a set is not important so the order doesn't really matter and this is exactly what you're seeing here now with a list the order has meaning the order is important and python retains the order that the objects were added to the list so this is a key distinction sets are unordered lists are ordered now the other distinction is that a set does not allow duplicate elements so uh to give you an example here let's copy and paste this set and I'm just going to create a bunch of duplicates here so I'm going to add the O character twice I'm going to add the U twice and I'm going to add a whole bunch of a a here now when I evaluate this expression we can see here we get the exact same result that we actually got before so python is weeding out all the duplicates when you create a set and that's kind of the whole point right a set does not allow duplicates whereas with a list I can create duplicates all day long right the the list does not care about duplicates at all it just cares about the elements that are contained in it and the Order of those elements so this will work beautifully and with a set it will remove the duplicate elements and just stick to the non-duplicate elements and it's going to ignore the order as well so key distinction here right now let's talk about some of the performance characteristics for these sets so in a proper set implementation you would be able to quickly test for set membership so if I wanted to test for membership in a list for example like this I in list vowels what happens internally is that we search the whole list one by one right so python is going to go all right I'm supposed to look for I in list of vowels all right so let's take list of vowels and let's look at each element in sequence and make sure it's I or not I right so all right we're going to take a look at a well that's not I we're going to take a look at e well that's not I we're going to take a look at I all right that's I I can return true and stop the search so in the worst case our list here if we search for an element it actually has to search the whole list so with the list to test for membership in the worst case it has to search all of the objects in the list in sequence and that can be quite slow so this is an a linear time uh test for membership which is not that great if you have a lot of elements now with a proper set implementation like the built-in set implementation in Python the situation is actually quite different so here when I do the same membership test with a proper set object uh it actually happens much faster I mean in this case you know honestly it doesn't really matter because we only have a small number of elements and in this case the list might actually be faster but but if you imagine we had thousands of elements the set will be much faster because a set is backed by a python dictionary which is a hash table internally it can test for membership much much much quicker so we can actually do this in constant time so once the set has been constructed it is very very easy for us or very fast for the computer to check whether a set contains a specific character so in this case what happens internally is that python doesn't actually search through all of these characters to find the ey or to make sure that I is uh an element in this set but it can do a faster lookup because of the way the set is structured internally so you can basically say hey are you in this in this bucket or are you in this part of the set and if you're in there well then I know to I know I can return true and if not then we're done and I don't have to search the rest of it and it's basically a tradeoff if you're trading some space like a set data structure is going to take up more space than a than a than a flat list or than just a plain list data structure but uh it can provide much quicker membership tests so it's kind of you know it's always about these trade-offs in uh when it comes to these data structures but that's kind of the key distinction so a set is very fast for doing these membership tests it doesn't allow duplicates and it is an unordered collection whereas a list is kind of the opposite in these aspects right it is ordered um it is kind of slow for membership tests because it needs to search the full list and it cares about the order so these are the key distinctions here and this is what makes a set data structure special so we looked at the simple set Expressions here to create a set and um you may remember you may have heard of other kinds of expressions in Python that allow you to create these structures for example list comprehensions and dictionary comprehensions and it turns out there is something very similar when it comes to sets in python as well so there is actually a set comprehension that works very similarly or looks very similar similarly to the dictionary comprehension so basically this is a way to express a simple for Loop in like a oneliner that creates a new set object very quickly and very conveniently for the programmer and I've got a video tutorial that I'm going to link that tells you a little bit more about how these comprehensions work if you haven't seen them before but you know just as a heads up these comprehensions also work with sets which is great now there's one caveat so if you want to create an empty set in Python and you do this you actually get a dictionary so what you need to do to create an empty set is you need to use the set Constructor so if you do this then you're actually creating a proper set object this is just something to keep in mind because otherwise it gets kind of hard to create an empty set object and uh you need those from time to time so now I want to talk about some of the set implementations that are available in the python standard library and you have seen one of them already so that was just the built-in set object um so the set type in Python is built into python it's part of the core language and uh it is mutable as you've seen so it means we can dynamically insert and delete elements from a set and sets are built on the dictionary data typee in Python and they share pretty much share the same performance characteristics so I went a little bit into that and I'm going to put some more links into the description if you want to go deeper and learn a little bit more about this so with the set built in you've kind of seen how to create these sets with the vowels example right and then also you can use the set Constructor or the set function to create new set objects I want to show you some cool features with the built-in sets just really quickly so you can actually create sets from all kinds of of uh sequence objects so in this case I'm passing a string to the set Constructor here and what this will do it will sort of explode this string into its characters and because sets are unordered you know this is doesn't really resemble what I put in but contains all of the characters and what I can do now is I can use a bunch of different operations uh working with sets so for example I can calculate the intersection between the word Al or the name Alice and the letters in it and the uh vowels here in my vowel set so the intersection between those two sets would be a i and e and these kinds of operations are really handy and this is really why you're using sets right uh because they can do these intersection tests in uh in linear time and just like you can do these intersection calculations you can also compute all of the other classical operations you want from a set Set uh for example doing a set Union or doing the set difference or subset operations and these all run in linear time which is great because that's what you would expect from a set implementation now these sets in Python they are Dynamic so you can add new elements to a set so in this case I just updated the vowel set here and you can add any element or any object to a python set as long as it's hash so it needs to follow the hashable uh protocol in Python and you can add it to a set which means that's really flexible so I could also you know uh put in all kinds of other objects numbers and then even generic objects if they support or if they're hashable and if you don't know what hashable is I'm going to put a link to that as well so it's just a definition of kind of the methods an object needs to provide for it to be considered hashable and so that you can add it to a python set all right so that's the set builtin now another built-in set implementation is the Frozen set remember how we created this vowels object previously with the set built in and I was able to add new elements to that set now python also has something called a frozen set which is also a built-in data type and what a frozen set is or does well it's pretty much the same as the regular set but the key difference is that I can't modify it so a frozen set is immutable it's completely static you can't delete elements from it or add elements to it and that's sometimes useful if you have some kind of constant so remember when I added the uh the letter X to that vowel set that didn't really make any sense right it would be much better if the vowels set would have been static so I couldn't make that mistake in my program and this is what you can get with a frozen set so they are really useful now another benefit is that they are hashable themselves so you can use a frozen set as a key inside a dictionary which can sometimes be useful if you want to do um you know some kind of lookup table to map a whole set to some output value so this can be really handy and Frozen sets are great they're helpful every time you need some kind of constant or a hashable object so yeah you should definitely know about them they're built into pythons are part of the language you don't you need to import any module for it and just like the set built in the Frozen set built-in exists all right so one more set data type so the python standard Library includes a pretty interesting class in the collections module so I just imported the collections module and what I'm going to do now is I'm going to create a counter object and the counter class in the python standard Library implements a multi set or also sometimes called a bag this is a set data type that allows items or elements in the set to have more than one occurrence so this is really helpful if you need to keep track not only if an element is part of a set but also how many times it is included in a set so let me give you an example all right so I created a new counter object and I call it inventory so you can imagine this would be the inventory of some character in a game right in some role playing game maybe and right now it's empty now the character kills a monster and the monster drops some Loop right so let's say the monster has one sword and it has uh three pieces of bread now I can add that to my inventory let's take a look at inventory all right so we can see here we picked up the three pieces of bread and the one sword now let's say we uh Venture on and kill another monster and this time it dropped another sword it also dropped an apple now if we pick up that loot if this was a regular set then we wouldn't really know you know how many pieces of bread and how many sorts and how many other things do we have but because this is a multi set it actually keeps track of the number of times each of these these objects occurs uh in the inventory so now I know exactly all right I have two swords right because we added one more sword to our inventory when we picked it up and I've got these three pieces of bread and I've got exactly one apple so the collections counter is considered to be a set data type and um it is Handy if you need anytime you need a multi set or a bag it can be a little bit hard to find in the python standard library because I mean it's not called a multi set or a bag but it's called a counter which in in my mind well I guess the name makes sense but um often I I like if things are named after the the abstract data structure because then I find them a little bit easier to find but python has a slightly different naming scheme here and I mean it it makes sense but it sometime sometimes is a little hard to find things that way all right so I hope that gave you a nice overview on sets how they work in Python if you ever need to implement a set in python or work with a set data structure in Python this is how you can do it you've got the set built in you've got the Frozen set built in and you've got the collections counter class all of them are excellent implementations from a per performance perspective so you don't need to worry about you know unexpected performance hits there this is sort of what you would expect from from a proper set implementation and uh if you would like to see more tutorials just like that then subscribe to my YouTube channel I'm going to put a little bit more info in the description below the video so you can find a tutorial that I wrote that gives you some more background and some more links about this topic and talking about sets in Python all right so thanks for listening and happy python take care