Skip to main content

Ordered Dictionary.

Project description

odict

Dictionary in which the insertion order of items is preserved (using an internal double linked list). In this implementation replacing an existing item keeps it at its original position.

Internal representation: values of the dict.

[pred_key, val, succ_key]

The sequence of elements uses as a double linked list. The links are dict keys. self.lh and self.lt are the keys of first and last element inserted in the odict.

Motivation

When this package was created, collections.OrderedDict not existed yet.

Another problem is that dict cannot always be inherited from in conjunction with other base classes. This may result in instance lay-out conflicts or other errors. So odict is written in a way that let you alter the dictionary base implementation easily.

Performance (Python 3.4)

When running the benchmark script, you get results similar to the one below on recent common hardware.

Adding and deleting builtin dict objects

Add 1000

0.63800ms

Delete 1000

0.36900ms

Add 10000

5.74600ms

Delete 10000

3.97000ms

Add 100000

69.40600ms

Delete 100000

47.30000ms

Add 1000000

807.09100ms

Delete 1000000

495.33400ms

Adding and deleting collection.OrderedDict objects

Add 1000

8.15200ms

Delete 1000

0.50800ms

Add 10000

91.45800ms

Delete 10000

7.10200ms

Add 100000

982.35500ms

Delete 100000

71.02300ms

Add 1000000

10222.78300ms

Delete 1000000

715.35100ms

Adding and deleting odict objects provided by this package

Add 1000

46.75600ms

Delete 1000

0.35700ms

Add 10000

23.97900ms

Delete 10000

4.79100ms

Add 100000

276.15900ms

Delete 100000

49.02700ms

Add 1000000

3244.68600ms

Delete 1000000

539.16500ms

Relation dict : odict

creating 1000 objects

1:73.285

deleting 1000 objects

1: 0.967

creating 10000 objects

1: 4.173

deleting 10000 objects

1: 1.207

creating 100000 objects

1: 3.979

deleting 100000 objects

1: 1.037

creating 1000000 objects

1: 4.020

deleting 1000000 objects

1: 1.088

Relation OrderedDict : odict

creating 1000 objects

1: 5.736

deleting 1000 objects

1: 0.703

creating 10000 objects

1: 0.262

deleting 10000 objects

1: 0.675

creating 100000 objects

1: 0.281

deleting 100000 objects

1: 0.690

creating 1000000 objects

1: 0.317

deleting 1000000 objects

1: 0.754

Usage

Import and create ordered dictionary.

from odict import odict
od = odict()

type conversion to ordinary dict. This will fail.

>>> dict(odict([(1, 1)]))
{1: [nil, 1, nil]}

The reason for this is here -> http://bugs.python.org/issue1615701

The __init__ function of dict checks wether arg is subclass of dict, and ignores overwritten __getitem__ & co if so.

This was fixed and later reverted due to behavioural problems with pickle.

Use one of the following ways for type conversion.

>>> dict(odict([(1, 1)]).items())
{1: 1}

>>> odict([(1, 1)]).as_dict()
{1: 1}

It is possible to use abstract mixin class _odict to hook another dict base implementation. This is useful i.e. when persisting to ZODB. Inheriting from dict and Persistent at the same time fails.

from persistent.dict import PersistentDict
class podict(_odict, PersistentDict):

    def _dict_impl(self):
        return PersistentDict

Misc

In a C reimplementation of this data structure, things could be simplified (and speed up) a lot if given a value you can at the same time find its key. With that, you can use normal C pointers.

TestCoverage

https://travis-ci.org/bluedynamics/odict.svg?branch=master

Summary of the test coverage report:

Name                    Stmts   Miss  Cover
-------------------------------------------
src/odict/__init__.py       1      0   100%
src/odict/pyodict.py      237      0   100%
src/odict/tests.py        198      0   100%
-------------------------------------------
TOTAL                     436      0   100%

Python Versions

  • Python 2.6+, 3.2+, pypy

  • May work with other versions (untested)

Contributors

  • bearophile (Original Author)

  • Robert Niederreiter (Author)

  • Georg Bernhard

  • Florian Friesdorf

  • Jens Klein

under the Python Software Foundation License.

Changes

1.6.0

  • Compatible with Python 3 and pypy. [rnix]

1.5.2

  • Fix permission problem in 1.5.1 release, some files were only rw by user. [jensens, 2016-11-25]

1.5.1

  • Implement __copy__ and __deepcopy__ in order to work with Python 2.7. [rnix, 2012-10-15]

  • Use try/except instead of in in __contains__. [rnix, 2012-10-15]

1.5.0

  • Implement alter_key. [rnix, 2012-05-18]

1.4.4

  • Remove unused error variable. [rnix, 2011-11-28]

  • Add note on why to check with == and != against _nil. [rnix, 2011-11-28]

1.4.3

  • Get rid of annoying warning about “global” usage in bench.py. [jensens, 2011-09-20]

1.4.2

  • More copy testing. [rnix, 2010-12-18]

  • Add has_key to odict. [rnix, 2010-12-18]

1.4.1

  • Fix release, README.rst was missing, added MANIFEST.in file to include it. [jensens, 2010-11-29]

1.4.0

  • Full test coverage. [chaoflow, rnix, 2010-08-17]

  • Code cleanup and optimizing. [chaoflow, rnix, 2010-08-17]

1.3.2

  • Access dict API providing class via function _dict_impl() and provide odict logic as abstract base class _odict. [rnix, 2010-07-08]

1.3.1

  • Add test for bool evaluation. [rnix, 2010-04-21]

1.3.0

  • Fix access to odict.lt and odict.lh properties. Now it’s possible to overwrite __setattr__ and __getattr__ on odict subclass without hassle. [rnix, 2010-04-06]

  • Add sort function to odict. [rnix, 2010-03-03]

1.2.6

  • Make odict serialize and deserialize properly. [gogo, 2010-01-12]

1.2.5

  • Add as_dict function. Supports type conto ordinary dict. [rnix, 2009-12-19]

  • Add benchmark script. [rnix, 2009-12-19]

1.2.4

  • Do not check for key in self on __delitem__, KeyError is raised properly anyway. Huge Speedup! [rnix, jensens, 2009-12-18]

1.2.3

  • Move tests to seperate file and make egg testable with python setup.py test. [rnix, 2009-12-07]

  • improve lt and lh properties to make odict work with copy.deepcopy. [rnix, 2009-12-07]

1.2.2

  • Use try/except instead of __iter__ in __setitem__ to determine if value was already set. [rnix, 2009-07-17]

1.2.1

  • Add missing __len__ and __contains__ functions. [rnix, 2009-03-17]

1.2.0

  • Eggified [rnix, 2009-03-17]

< 1.2

License

PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2

1. This LICENSE AGREEMENT is between the Python Software Foundation (“PSF”), and the Individual or Organization (“Licensee”) accessing and otherwise using this software (“Python”) in source or binary form and its associated documentation.

2. Subject to the terms and conditions of this License Agreement, PSF hereby grants Licensee a nonexclusive, royalty-free, world-wide license to reproduce, analyze, test, perform and/or display publicly, prepare derivative works, distribute, and otherwise use Python alone or in any derivative version, provided, however, that PSF’s License Agreement and PSF’s notice of copyright, i.e., “Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006 Python Software Foundation; All Rights Reserved” are retained in Python alone or in any derivative version prepared by Licensee.

3. In the event Licensee prepares a derivative work that is based on or incorporates Python or any part thereof, and wants to make the derivative work available to others as provided herein, then Licensee hereby agrees to include in any such work a brief summary of the changes made to Python.

4. PSF is making Python available to Licensee on an “AS IS” basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON WILL NOT INFRINGE ANY THIRD PARTY RIGHTS.

5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON, OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF.

6. This License Agreement will automatically terminate upon a material breach of its terms and conditions.

7. Nothing in this License Agreement shall be deemed to create any relationship of agency, partnership, or joint venture between PSF and Licensee. This License Agreement does not grant permission to use PSF trademarks or trade name in a trademark sense to endorse or promote products or services of Licensee, or any third party.

8. By copying, installing or otherwise using Python, Licensee agrees to be bound by the terms and conditions of this License Agreement.

Project details


Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page