[Python-checkins] r70014 - peps/trunk/pep-0372.txt

[raymond.hettinger]

Author: raymond.hettinger
Date: Fri Feb 27 06:04:47 2009
New Revision: 70014

Log:
Note performance trade-offs of various design strategies.

Modified:
   peps/trunk/pep-0372.txt

Modified: peps/trunk/pep-0372.txt
==============================================================================
--- peps/trunk/pep-0372.txt	(original)
+++ peps/trunk/pep-0372.txt	Fri Feb 27 06:04:47 2009
@@ -224,6 +224,24 @@
    explicitly craft an order based comparison:
    ``list(od1.items())==list(od2.items())``.
 
+What are the trade-offs of the possible underlying data structures?
+
+   * Keeping a sorted list of keys is very fast for all operations except
+     __delitem__() which becomes an O(n) exercise.  This structure leads to
+     very simple code and little wasted space.
+
+   * Keeping a separate dictionary to record insertion sequence numbers makes
+     the code a little bit more complex.  All of the basic operations are O(1)
+     but the constant factor is increased for __setitem__() and __delitem__()
+     meaning that every use case will have to pay for this speedup (since all
+     buildup go through __setitem__). Also, the first traveral incurs a
+     one-time ``O(n log n)`` sorting cost.  The storage costs are double that
+     for the sorted-list-of-keys approach.
+
+   * A version written in C could use a linked list.  The code would be more
+     complex than the other two approaches but it would conserve space and
+     would keep the same big-oh performance as regular dictionaries.  It is
+     the fastest and most space efficient.
 
 Reference Implementation
 ========================