Mastering Team Play: Four powerful examples of composing Python tools (#184)
Raymond Hettinger
45min ◊◊ Intermediate
Saturday 01:20pm, Centennial II
categories:
invited
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.
1. 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.
2. 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.
3. NFA to DFA conversion. The classic, but difficult, algorithm for lexical analysis becomes simple when composing Python's dicts and frozensets.
4. 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.
1. 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.
2. 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.
3. NFA to DFA conversion. The classic, but difficult, algorithm for lexical analysis becomes simple when composing Python's dicts and frozensets.
4. 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.
Files:
| file | size | uploaded | comment |
|---|---|---|---|
| TeamPlay.ppt | 1.7 MB | Sun, Feb. 21st, 5:08 p.m. | Slides |
| TeamPlay_.ppt | 1.7 MB | Sun, Feb. 21st, 5:12 p.m. | Origional Slides |
video:
# Permalink
.