Luciano Ramalho - Set Practice: learning from Python's set types - PyCon 2019

"Speaker: Luciano Ramalho

Key takeaways:

1. Set operations enable simpler and faster solutions for many tasks;
1. Python's set classes are lessons in elegant, idiomatic API design;
1. A set class is a suitable context for implementing operator overloading.

Boolean logic and set theory are closely related. In practice, we will see cases where set operations provide simple and fast declarative solutions to programming problems that otherwise require complicated and slow procedural coding.

Python's set built-ins and ABCs provide a rich and well designed API. We will consider their interfaces, and how they can inspire the creation of Pythonic APIs for your own classes.

Finally, we will discuss operator overloading — a technique that is not suitable everywhere, but certainly makes sense with sets. Taking a few operators as examples, we will study their implementation in a new `UintSet` class for integer elements. `UintSet` fully implements the `MutableSet` interface over a totally different internal representation based on a bit array instead of a hash table. Membership tests run in _O(1)_ time like the built-in sets (however, `UintSet` is currently pure Python, so YMMV). Using bit arrays allow core set operations like intersection and union to be implemented with fast bitwise operators, and provides compact storage for dense sets of integers.

Slides are at neither link in the description

[CristianCiupitu]

Since this is based on a bit array, I'd like to point out the "Bit Twiddling Hacks" page [1]. It's for the C programming language, but some techniques might also work for Python. I tried Kernighan's bit counting method [2] and it was a tiny bit faster than Luciano's naive `count_ones` function [3]; at least that's what I got on Python 3.7.