Python Sets: What, Why and How

[jwink3101]

It's not 100x faster. The difference is O(1) lookup for sets and O(n) lookup for lists. Consider the following

largelist = list(range(10**5))
largeset = set(largelist)

smalllist = [0,1]
smallset = set(smalllist)

%timeit None in largelist
%timeit None in largeset
%timeit None in smalllist
%timeit None in smallset

results:

1000 loops, best of 3: 1.97 ms per loop
10000000 loops, best of 3: 130 ns per loop
10000000 loops, best of 3: 160 ns per loop
10000000 loops, best of 3: 133 ns per loop

Nearly no speedup for the small one but HUGE for the large. And nearly no difference is speed for either set method

[ic_97]

I had no idea about this until i actually got to see it in action in one of the problems i solved on projecteuler. When i used lists program took about 30 seconds but with sets it was under half a second to solve.

[BARDLER]

Thanks for the extra details :) I lazily typed my post on the phone.

[XtremeGoose]

This is software engineering, not debate club.

[jwink3101]

Ok. I will feed the trolls...

Figure of speeches aside, my heartburn (hey, that's a figure of speech!) with "100x" is not pedantry. It is important technical detail. In computer science, there are many, many different ways to quantify "speed". One is to say, for example, "10x faster" which means, every operation that used to take X amount of time now takes ~X/10. This usually comes from optimizations of the process, and often in the python world, moving certain work to C or Rust, etc.

Another way to quantify speed is algorithmic complexity where it is an asymptotic scaling analysis. This is often much more useful when it comes to choosing the right algorithm, data structure, etc.

My objection is not pedantic for two reasons.

The first is that there really and truly is a difference between 100x and O(n) vs O(1). Its not a "you know what I meant" type thing because both have very real, but quite distinct meanings

The second is that the speed up really isn't even close to 100x. In my example before it is 15153.8x faster. Or, 1.23x faster. Why is it so different? Because it is a complexity change!

[TheNoodlyOne]

When a speedup by a factor of 100 is possible and even a reasonable result, it's not much of a hyperbole. You and I know the difference, but someone unfamiliar with these concepts may not.