1
00:00:05,280 --> 00:00:09,760
In this video, we'll see why using in with 
a set is faster than when you use a list. 

2
00:00:09,760 --> 00:00:14,320
The reason is because sets use hash 
codes – just like keys in a dictionary. 

3
00:00:14,320 --> 00:00:18,560
We saw how dictionary keys are stored using 
their hash codes, when we created our simple 

4
00:00:18,560 --> 00:00:22,400
dictionary implementation.
Review the Hash tables video, 

5
00:00:22,400 --> 00:00:27,353
if you want to remind yourself about 
how we used hash codes to store keys. 

6
00:00:27,840 --> 00:00:32,000
When we check if something is in a list, 
Python has to check each item in the list, 

7
00:00:32,000 --> 00:00:35,840
until it finds the one we want.
If we're checking for the string '1', 

8
00:00:35,840 --> 00:00:39,280
Python starts by comparing 
the 1st item in the list. 

9
00:00:39,280 --> 00:00:42,720
'4' doesn't equal '1' so it 
moves on to check the next value. 

10
00:00:42,720 --> 00:00:47,062
'5' also doesn't equal '1', and 
Python has to continue searching. 

11
00:00:47,062 --> 00:00:52,062
It has to perform 4 comparisons, before 
it knows that '1' is in the list. 

12
00:00:53,120 --> 00:00:55,680
Of course, if we're checking for the string '4', 

13
00:00:55,680 --> 00:00:59,600
it will find it on the first go.
But if we're testing for '7', 

14
00:00:59,600 --> 00:01:04,560
the entire list would have to be checked, before 
Python could tell us that it isn't in the list. 

15
00:01:04,560 --> 00:01:08,000
That's called a linear search. 
You start at the beginning, 

16
00:01:08,000 --> 00:01:13,182
and check each item until you either find the 
one you want, or reach the end of the list. 

17
00:01:14,240 --> 00:01:17,222
Note that this is the case 
even with a sorted list. 

18
00:01:17,280 --> 00:01:21,520
Python has no way to tell if a list is 
sorted, and has to perform a linear search, 

19
00:01:21,520 --> 00:01:27,200
when checking if something is in a list.
When checking for membership of a set, 

20
00:01:27,200 --> 00:01:30,640
Python uses the hash code to find 
out where the item should be. 

21
00:01:30,640 --> 00:01:34,486
If it's there, then the item is 
`in` the set, otherwise it's not. 

22
00:01:34,560 --> 00:01:39,178
Hash codes are used in the same 
way as we saw for dictionary keys. 

23
00:01:39,178 --> 00:01:43,520
A hash code lets us go directly 
to the item in the hash table. 

24
00:01:43,520 --> 00:01:47,520
There's a small overhead while the hash 
code is calculated, but once that's done, 

25
00:01:47,520 --> 00:01:52,000
access is very fast.
You can check if a value 

26
00:01:52,000 --> 00:01:56,800
is in a set of one billion items, just 
as quickly as in a set of five items. 

27
00:01:56,800 --> 00:02:02,204
The size of the set has no effect on the 
time taken, to check if something's in it. 

28
00:02:02,720 --> 00:02:05,840
So that's the advantage of 
using a set, rather than a list, 

29
00:02:05,840 --> 00:02:09,520
when testing for membership.
If you're working with large data, 

30
00:02:09,520 --> 00:02:14,860
checking for membership will be a lot 
faster with a set, compared to a list. 

31
00:02:15,520 --> 00:02:17,760
Does that mean you should replace sets with lists, 

32
00:02:17,760 --> 00:02:20,640
whenever you're testing if 
something is in the list? 

33
00:02:20,640 --> 00:02:25,280
I've just explained why checking an item in a 
set is a lot faster than checking it in a list. 

34
00:02:25,280 --> 00:02:28,560
So you might be tempted to 
convert all your lists to sets. 

35
00:02:28,560 --> 00:02:32,240
But that's not what I'm suggesting.
Things are rarely that simple, 

36
00:02:32,240 --> 00:02:36,498
and there aren't rules that you can apply 
everywhere. Programming isn't like that. 

37
00:02:36,640 --> 00:02:41,941
Understand how things work, rather 
than trying to remember a set of rules. 

38
00:02:42,480 --> 00:02:45,360
If we could produce a set of rules 
to tell you how to write code, 

39
00:02:45,360 --> 00:02:48,400
then we could get computers 
to write the code for us. 

40
00:02:48,400 --> 00:02:52,643
Computers are very good at 
following rules, after all. 

41
00:02:53,360 --> 00:02:57,360
Treat each case individually.
Understand what's happening in the code, 

42
00:02:57,360 --> 00:03:00,720
and understand the implications 
of any decisions you make. 

43
00:03:00,720 --> 00:03:05,512
That's not as hard as it sounds, once you've got 
used to the various objects that are available. 

44
00:03:05,600 --> 00:03:08,640
But students are often still unsure 
of which object they should use, 

45
00:03:08,640 --> 00:03:11,920
so I'm going to digress slightly 
and give you some pointers. 

46
00:03:11,920 --> 00:03:15,440
I'll use the summarychallenge code we've 
just been looking at, and discuss a couple 

47
00:03:15,440 --> 00:03:19,843
of things that might cause you to worry 
whether you're using the right object. 

48
00:03:20,560 --> 00:03:26,037
Our original code checked for the choice 
being in a string. That's the string "12345". 

49
00:03:26,400 --> 00:03:30,525
That had a bug, as we saw – so a 
string isn't really suitable here. 

50
00:03:30,640 --> 00:03:34,823
We need to use a list, a tuple or a set. 

51
00:03:35,200 --> 00:03:40,072
To fix the bug, we used a list. 
A tuple would also have worked. 

52
00:03:40,072 --> 00:03:44,080
That fixed the bug, and is an 
acceptable solution to the problem. 

53
00:03:44,080 --> 00:03:47,280
Even though checking for membership 
of a list or a tuple is quite slow, 

54
00:03:47,280 --> 00:03:50,127
we need to keep things in perspective. 

55
00:03:51,120 --> 00:03:55,920
We've only got 5 items in the list.
A set would be faster, but the difference is a 

56
00:03:55,920 --> 00:04:02,160
few microseconds. That's millionths of a second.
Of course, we had to test that statement before 

57
00:04:02,160 --> 00:04:10,346
recording this video. On an Intel Core i7 2.2 
GHz Quad-Core CPU, we got the following timings. 

58
00:04:11,120 --> 00:04:15,760
We used a list and a set with one million items, 
and tested checking for an item that was in the 

59
00:04:15,760 --> 00:04:19,360
data, and an item that wasn't.
The performance using a set 

60
00:04:19,360 --> 00:04:25,040
was better than using a list, as we'd expect.
Not surprisingly, using a list was a lot slower 

61
00:04:25,040 --> 00:04:30,320
when the value wasn't present. In that case, the 
entire list has to be scanned before Python can 

62
00:04:30,320 --> 00:04:34,640
know that the value doesn't exist.
Even then, in the worst case, 

63
00:04:34,640 --> 00:04:39,203
the test for membership of a list 
only took one hundredth of a second. 

64
00:04:39,840 --> 00:04:44,640
Our summarychallenge program spends most of its 
time waiting for the user to type their choice. 

65
00:04:44,640 --> 00:04:48,160
It makes very little sense to worry about 
optimising the code to save a few hundredths 

66
00:04:48,160 --> 00:04:50,960
of a second, or less.
Would you notice a 

67
00:04:50,960 --> 00:04:55,280
delay of a few milliseconds when typing?
But if we were testing membership inside 

68
00:04:55,280 --> 00:05:01,322
a tight loop, where performance was important, 
there is a performance improvement we can make. 

69
00:05:02,080 --> 00:05:06,800
Using a set, rather than a list, 
is a good start – as we've seen. 

70
00:05:06,800 --> 00:05:12,800
But how we create that set is also important.
In this example, we call the set function. We 

71
00:05:12,800 --> 00:05:17,920
pass a sequence containing the characters we 
need, and Python will create a set for us. 

72
00:05:17,920 --> 00:05:21,600
That means the set has to be 
created, each time round the loop. 

73
00:05:21,600 --> 00:05:26,529
That's quite expensive in terms 
of CPU time, and can be improved. 

74
00:05:27,356 --> 00:05:32,160
Using a set literal, instead of 
the set function, is much faster. 

75
00:05:32,160 --> 00:05:37,206
After this simple change, the code performed 
twice as fast as using the set function. 

76
00:05:37,280 --> 00:05:40,880
That's definitely worth knowing, when 
you find that performance is an issue, 

77
00:05:40,880 --> 00:05:44,320
and you want to speed things up.
The disadvantage is that it takes 

78
00:05:44,320 --> 00:05:48,400
a bit longer to type . That's not a 
huge problem, but does explain why 

79
00:05:48,400 --> 00:05:54,370
you'll sometimes see a string being passed 
to the set function, in cases like this. 

80
00:05:54,800 --> 00:05:58,880
You might also decide to create 
the set once, outside the loop. 

81
00:05:58,880 --> 00:06:03,460
Inside the loop, the valid_choices 
variable is used in the condition. 

82
00:06:03,520 --> 00:06:09,210
We found very little performance difference 
between this code, and the code in the last slide. 

83
00:06:10,080 --> 00:06:14,320
Once you start thinking in terms of what 
Python has to do, when executing your code, 

84
00:06:14,320 --> 00:06:19,920
it gets easier to write more efficient code.
But as I've said, keep it in perspective. 

85
00:06:19,920 --> 00:06:24,800
Optimising code that's mainly spent waiting for 
user input, isn't usually worth the extra typing, 

86
00:06:24,800 --> 00:06:29,680
or the risk of making your code less readable.
If your loop is doing a lot of computation, 

87
00:06:29,680 --> 00:06:34,484
and has to run quickly, then 
it is worth optimising it. 

88
00:06:34,640 --> 00:06:38,080
A tight loop is one that iterates 
many times, and has a significant 

89
00:06:38,080 --> 00:06:42,640
impact on the total execution time.
You'll find other definitions on line, 

90
00:06:42,640 --> 00:06:45,920
but that's the one we use.
All definitions will talk about 

91
00:06:45,920 --> 00:06:51,040
the loop iterating many times – hundreds, 
thousands or maybe millions of times. 

92
00:06:51,040 --> 00:06:56,012
Those are the kinds of loops that can benefit 
from more efficient ways of writing the code. 

93
00:06:56,800 --> 00:07:01,040
That's the end of this little digression. We've 
looked at why you might want to use a set, 

94
00:07:01,040 --> 00:07:06,480
when you need to test for membership. And we've 
seen how a set is faster than a list or tuple. 

95
00:07:06,480 --> 00:07:11,120
In the remaining videos in this section, we'll 
look at the other things we can do with sets. 

96
00:07:11,120 --> 00:07:14,800
See you in the next video.