blob: fe5a1203269979d9fb1128c51ca8e8b45024c52b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
immutables
==========
.. image:: https://travis-ci.org/MagicStack/immutables.svg?branch=master
:target: https://travis-ci.org/MagicStack/immutables
.. image:: https://ci.appveyor.com/api/projects/status/tgbc6tq56u63qqhf?svg=true
:target: https://ci.appveyor.com/project/MagicStack/immutables
.. image:: https://img.shields.io/pypi/v/immutables.svg
:target: https://pypi.python.org/pypi/immutables
An immutable mapping type for Python.
The underlying datastructure is a Hash Array Mapped Trie (HAMT)
used in Clojure, Scala, Haskell, and other functional languages.
This implementation is used in CPython 3.7 in the ``contextvars``
module (see PEP 550 and PEP 567 for more details).
Immutable mappings based on HAMT have O(log N) performance for both
``set()`` and ``get()`` operations, which is essentially O(1) for
relatively small mappings.
Below is a visualization of a simple get/set benchmark comparing
HAMT to an immutable mapping implemented with a Python dict
copy-on-write approach (the benchmark code is available
`here <https://gist.github.com/1st1/292e3f0bbe43bd65ff3256f80aa2637d>`_):
.. image:: bench.png
Installation
------------
``immutables`` requires Python 3.5+ and is available on PyPI::
$ pip install immutables
immutables.Map
--------------
The ``Map`` object implements ``collections.abc.Mapping`` ABC
so working with it is very similar to working with Python dicts.
The only exception are its ``Map.set()`` and ``Map.delete()`` methods
which return a new instance of ``Map``:
.. code-block:: python
m1 = Map() # an empty Map
m2 = m1.set('key1', 'val1') # m2 has a 'key1' key, m1 is still empty
m3 = m2.set('key2', 'val2')
m3 = m3.delete('key1') # m3 has only a 'key2' key
Further development
-------------------
* An immutable version of Python ``set`` type with efficient
``add()`` and ``discard()`` operations.
* Add support for efficient ``Map.update()`` operation, allow to
pass a set of key/values to ``Map()``, and add support for
pickling.
License
-------
Apache 2.0
|
