Pycon Notes: Composing Python Tools
by john on Feb.20, 2010, under PyCon
Raymond Hettinger
Deque is like a list. Pronounced “deck” and stands for double ended queue. Can append() and pop() at both ends, can be indexed but not efficiently, no insert. Basically efficient on the ends. In collections.deque().
Timsort uses partially sorted lists to sort in O(n) time.
Random.sample() picks between two algorithms depending on how you are going to use it because 1,000 choose 900 is very different from 1,000,000 choose 10.
OrderedDicts usually have O(n) performance for deletion. By using a doubly linked list to store items in order and a dict for lookup you get O(1) for all operations. New code is in Python 3.
Python has native support for sets of sets. This enables easy translation of English description of problems involving sets to Python code in a few lines. Applicable to translating an NFA to a DFA.
