The conclusions are:
- String concatenation is more favored than string formatting.
- Built-in set and dict types are fast.
- Computing is more favored in C than Python. Try to minimize Python code with function inlining, implicit loop and move as much computing to C as possible, not necessarily your own C extension. In fact, set and dict are in C.
- Common wisdoms such as optimizing inner loops, or better flatten (unroll) the loop itself, using local instead global variables to take advantage of cache, are helpful but not by much in Python.
- Measurements are a must.