Description
Mastering Team Play: Four powerful examples of composing Python tools
Presented by Raymond Hettinger
Starts with a quick review of the performance characteristics of major individual tools in Python: bisect, heapq, lists, deques, sets, frozensets, class structures, sorts, and weakreferences. Show how these tools can be powerfully combined to create elegant solutions to four hard problems.
- Random sampling: when one data structure isn't enough. Discuss how the nature of the problem dictates when to use one of two alternate data structures.
- Ordered dictionaries: with the right compostion of dictionaries, linked lists, and weak references, a dictionary can remember its insertion order without any impact on its big-Oh running times.
- NFA to DFA conversion. The classic, but difficult, algorithm for lexical analysis becomes simple when composing Python's dicts and frozensets.
- Running median: the obvious approaches are horribly slow. The problem centers around how to efficiently maintain sorted data while advancing a large sliding window one value at a time. A list of deques provides a dramatic and scalable improvement in running time.