[Checkins] SVN: zc.dict/trunk/ Merged the tlotze-blist feature branch: store the order of an OrderedDict in
Thomas Lotze
tl at gocept.com
Mon Mar 16 14:33:21 EDT 2009
Log message for revision 98150:
Merged the tlotze-blist feature branch: store the order of an OrderedDict in
a bucket-based list instead of a plain PersistentList for better performance.
Changed:
_U zc.dict/trunk/
U zc.dict/trunk/CHANGES.txt
U zc.dict/trunk/buildout.cfg
U zc.dict/trunk/setup.py
U zc.dict/trunk/src/zc/dict/dict.py
A zc.dict/trunk/src/zc/dict/generations/
U zc.dict/trunk/src/zc/dict/ordered.txt
U zc.dict/trunk/src/zc/dict/tests.py
-=-
Property changes on: zc.dict/trunk
___________________________________________________________________
Modified: svn:ignore
- bin
build
develop-eggs
dist
eggs
.installed.cfg
parts
zc.dict.egg-info
+ bin
build
develop-eggs
dist
eggs
.installed.cfg
parts
Modified: zc.dict/trunk/CHANGES.txt
===================================================================
--- zc.dict/trunk/CHANGES.txt 2009-03-16 18:16:57 UTC (rev 98149)
+++ zc.dict/trunk/CHANGES.txt 2009-03-16 18:33:21 UTC (rev 98150)
@@ -1,3 +1,12 @@
+1.3 (unreleased)
+----------------
+
+* Changed the implementation of OrderedDict to store the order in buckets
+ using zc.blist. At present, this improves performance only for those
+ operations that add or remove single items of an OrderedDict. Reordering the
+ existing items still results in the order being rewritten as a whole. A
+ better, more granular reordering API is planned for a future release.
+
1.2.1 (2007-3-5)
----------------
Modified: zc.dict/trunk/buildout.cfg
===================================================================
--- zc.dict/trunk/buildout.cfg 2009-03-16 18:16:57 UTC (rev 98149)
+++ zc.dict/trunk/buildout.cfg 2009-03-16 18:33:21 UTC (rev 98150)
@@ -1,13 +1,17 @@
[buildout]
develop = .
-parts = test py
+parts = test test-generations py
-find-links = http://download.zope.org/distribution/
-
[test]
recipe = zc.recipe.testrunner
eggs = zc.dict
+defaults = ["-v", "-c"]
+[test-generations]
+recipe = zc.recipe.testrunner
+eggs = zc.dict [generations]
+defaults = ["-v", "-c", "--suite-name=test_suite_generations"]
+
[py]
recipe = zc.recipe.egg
eggs = zc.dict
Modified: zc.dict/trunk/setup.py
===================================================================
--- zc.dict/trunk/setup.py 2009-03-16 18:16:57 UTC (rev 98149)
+++ zc.dict/trunk/setup.py 2009-03-16 18:33:21 UTC (rev 98150)
@@ -5,7 +5,7 @@
open("src/zc/dict/ordered.txt").read())
setup(
name="zc.dict",
- version="1.2.1",
+ version="1.3dev",
license="ZPL 2.1",
author="Zope Corporation",
author_email="zope3-dev at zope.org",
@@ -14,7 +14,8 @@
packages=["zc", "zc.dict"],
package_dir={"": "src"},
include_package_data=True,
- install_requires=["setuptools", "zope.interface", "ZODB3"],
+ install_requires=["setuptools", "zope.interface", "ZODB3", "zc.blist"],
+ extras_require={"generations": ["zope.app.generations"]},
tests_require=["zope.testing"],
description=open('README.txt').read(),
long_description=long_description,
Modified: zc.dict/trunk/src/zc/dict/dict.py
===================================================================
--- zc.dict/trunk/src/zc/dict/dict.py 2009-03-16 18:16:57 UTC (rev 98149)
+++ zc.dict/trunk/src/zc/dict/dict.py 2009-03-16 18:33:21 UTC (rev 98150)
@@ -20,7 +20,7 @@
import BTrees
import BTrees.Length
import persistent
-import persistent.list
+import zc.blist
class Dict(persistent.Persistent):
@@ -126,12 +126,11 @@
raise KeyError, 'container is empty'
return (key, self.pop(key))
+
class OrderedDict(Dict):
- """A Ordered BTree-based dict-like persistent object that can be safely
+ """An ordered BTree-based dict-like persistent object that can be safely
inherited from.
-
- This class does not have as good behavior with large numbers of members
- as the Dict class because the _order object is not in buckets.
+
"""
# what do we get from the superclass:
@@ -139,11 +138,11 @@
# get, __delitem__
def __init__(self, *args, **kwargs):
- self._order = persistent.list.PersistentList()
+ self._order = zc.blist.BList()
super(OrderedDict, self).__init__(*args, **kwargs)
def keys(self):
- return self._order[:]
+ return list(self._order)
def __iter__(self):
return iter(self._order)
@@ -155,29 +154,26 @@
return [(key, self._data[key]) for key in self._order]
def __setitem__(self, key, value):
- delta = 1
- if key in self._data:
- delta = 0
- self._data[key] = value
- if delta:
+ if key not in self._data:
self._order.append(key)
- self._len.change(delta)
+ self._len.change(1)
+ self._data[key] = value
def updateOrder(self, order):
- order = persistent.list.PersistentList(order)
+ order = list(order)
if len(order) != len(self._order):
raise ValueError("Incompatible key set.")
order_set = set(order)
-
+
if len(order) != len(order_set):
raise ValueError("Duplicate keys in order.")
if order_set.difference(self._order):
raise ValueError("Incompatible key set.")
- self._order = order
+ self._order[:] = order
def clear(self):
super(OrderedDict, self).clear()
@@ -190,7 +186,7 @@
order = self._order
try:
self._data = OOBTree()
- self._order = persistent.list.PersistentList()
+ self._order = zc.blist.BList()
c = copy.copy(self)
finally:
self._data = data
@@ -219,5 +215,3 @@
self._len.change(-1)
self._order.remove(key)
return res
-
-
Modified: zc.dict/trunk/src/zc/dict/ordered.txt
===================================================================
--- zc.dict/trunk/src/zc/dict/ordered.txt 2009-03-16 18:16:57 UTC (rev 98149)
+++ zc.dict/trunk/src/zc/dict/ordered.txt 2009-03-16 18:33:21 UTC (rev 98150)
@@ -5,12 +5,6 @@
additional feature that it remembers the order in which items were added.
It also provides the API to reorder the items.
-Importantly, the OrderedDict currently uses a PersistentList to store
-the order, which does not have good behavior for large collections,
-because the entire collection of keys must be pickled every time any
-key, or ordering, changes. A BList would be a preferred data structure,
-but that has not yet been released.
-
>>> from zc.dict import OrderedDict
>>> d = OrderedDict()
>>> d
@@ -47,6 +41,11 @@
>>> d._len()
2
+The order of the keys is stored in a BList so buckets are used for it as well:
+
+ >>> d._order
+ <zc.blist.BList object at ...>
+
In order to keep updates efficient for small changes, we unroll them
as a series of setitems.
@@ -172,9 +171,9 @@
However, efficient iterators are available via the iter methods:
>>> iter(d)
- <iterator object at ...>
+ <generator object at ...>
>>> d.iterkeys()
- <iterator object at ...>
+ <generator object at ...>
>>> d.iteritems()
<generator object at ...>
Modified: zc.dict/trunk/src/zc/dict/tests.py
===================================================================
--- zc.dict/trunk/src/zc/dict/tests.py 2009-03-16 18:16:57 UTC (rev 98149)
+++ zc.dict/trunk/src/zc/dict/tests.py 2009-03-16 18:33:21 UTC (rev 98150)
@@ -18,12 +18,25 @@
import unittest
from zope.testing import doctest
+
+optionflags = (doctest.INTERPRET_FOOTNOTES |
+ doctest.REPORT_NDIFF |
+ doctest.ELLIPSIS)
+
+
def test_suite():
return unittest.TestSuite([
doctest.DocFileSuite('dict.txt', 'ordered.txt',
- optionflags=doctest.INTERPRET_FOOTNOTES
- |doctest.REPORT_NDIFF|doctest.ELLIPSIS),
+ optionflags=optionflags),
])
+
+def test_suite_generations():
+ suite = test_suite()
+ suite.addTest(doctest.DocFileSuite('generations/evolve1.txt',
+ optionflags=optionflags))
+ return suite
+
+
if __name__ == '__main__':
unittest.main(defaultTest='test_suite')
More information about the Checkins
mailing list