Contribute Media
A thank you to everyone who makes this possible: Read More

Mastering Team Play: Four powerful examples of composing Python tools (#184)

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.

  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.

Details

Improve this page