[Zope-dev] zc.dict.OrderedDict efficiency

Thomas Lotze thomas at thomas-lotze.de
Thu Sep 18 15:52:41 EDT 2008


The documentation of OrderedDict from zc.dict 1.2.1 states that the
current implementation is inefficient for large collections because it
uses a PersistentList to store the order. It also says that a BList which
would be preferrable is not used as it is not yet released.

- What's the state of those BLists? Are they just around the corner or
  would it be worthwhile to consider some interim solution to the
  efficiency issue?

- If the latter, what about storing the order by
  * introducing internal integer keys incremented for each newly added
    item and
  * mapping from integers to keys and values in one BTree and from keys to
    integers and values in a second (or using more BTrees to avoid storing
    those pairs)?
  This introduces somewhat more overhead in general but prevents the bad
  behaviour for large collections. Would that be an acceptable trade-off?

-- 
Thomas





More information about the Zope-Dev mailing list