Sets: Is It In There?

Lesson 5 of 10 · 7 min · Free, no account needed

What you will learn

A set holds each item once, in no particular order. It's a hash table with keys and no values.
x in s is one jump into a locker, not a scan: the same speed for 10 items or 100 million.
Pour a list into a set and the repeats vanish: len(set(names)) counts the different names.
Sets combine: a & b is what both have, a | b is everything, a - b is only in a.

Is "shadow_wolf" taken?
A game has 100 million usernames. Checking them one by one: how long does one answer take?
List or set: grow the number of names.
The set stores names in hash lockers, like last lesson. Slide all the way up.
A list has no idea where a name is, so a missing name means checking all of them. A set hashes the name, opens one locker and looks only there.
Pour a guest list into a set.
Some names were typed twice. Watch the length.
That's a set.
A set holds each item at most once, in no particular order. Inside it's a hash table with keys and no values.
s = set() makes one, s.add(x) puts x in, x in s asks the question in one jump, len(s) counts the items.
set(names) turns a list into a set, so len(set(names)) counts the different names.
Who follows whom?
Sort every name by whose list it is in. This is a Venn diagram from math, done with sets.
Make your own set of games.
Pick five. You'll compare it with your friends next.
Who has the most games in common with you?
Tap each friend to see mine & theirs. Keep the best match selected, then Check.
The intersection a & b keeps only items in both sets. For each game in your set, the computer asks "in theirs?", one jump each, so comparing is fast even for huge sets.
Be the bouncer.
Guests arrive. Already inside, or let them in? Fast and no mistakes.
One more job for a set: remembering where you've been.
A robot explores a maze. Run it without a set, then with one.

Lessons are interactive and need JavaScript. Turn it on to play them.