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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
Python Sorted Containers
========================
`Sorted Containers`_ is an Apache2 licensed `sorted collections library`_,
written in pure-Python, and fast as C-extensions.
Python's standard library is great until you need a sorted collections
type. Many will attest that you can get really far without one, but the moment
you **really need** a sorted list, sorted dict, or sorted set, you're faced
with a dozen different implementations, most using C-extensions without great
documentation and benchmarking.
In Python, we can do better. And we can do it in pure-Python!
.. code-block:: python
>>> from sortedcontainers import SortedList
>>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
>>> sl
SortedList(['a', 'b', 'c', 'd', 'e'])
>>> sl *= 10_000_000
>>> sl.count('c')
10000000
>>> sl[-3:]
['e', 'e', 'e']
>>> from sortedcontainers import SortedDict
>>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
>>> sd
SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.popitem(index=-1)
('c', 3)
>>> from sortedcontainers import SortedSet
>>> ss = SortedSet('abracadabra')
>>> ss
SortedSet(['a', 'b', 'c', 'd', 'r'])
>>> ss.bisect_left('c')
2
All of the operations shown above run in faster than linear time. The above
demo also takes nearly a gigabyte of memory to run. When the sorted list is
multiplied by ten million, it stores ten million references to each of "a"
through "e". Each reference requires eight bytes in the sorted
container. That's pretty hard to beat as it's the cost of a pointer to each
object. It's also 66% less overhead than a typical binary tree implementation
(e.g. Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap, etc.) for which
every node must also store two pointers to children nodes.
`Sorted Containers`_ takes all of the work out of Python sorted collections -
making your deployment and use of Python easy. There's no need to install a C
compiler or pre-build and distribute custom extensions. Performance is a
feature and testing has 100% coverage with unit tests and hours of stress.
.. _`Sorted Containers`: http://www.grantjenks.com/docs/sortedcontainers/
.. _`sorted collections library`: http://www.grantjenks.com/docs/sortedcontainers/
Testimonials
------------
**Alex Martelli**, `Fellow of the Python Software Foundation`_
"Good stuff! ... I like the `simple, effective implementation`_ idea of
splitting the sorted containers into smaller "fragments" to avoid the O(N)
insertion costs."
**Jeff Knupp**, `author of Writing Idiomatic Python and Python Trainer`_
"That last part, "fast as C-extensions," was difficult to believe. I would need
some sort of `Performance Comparison`_ to be convinced this is true. The author
includes this in the docs. It is."
**Kevin Samuel**, `Python and Django Trainer`_
I'm quite amazed, not just by the code quality (it's incredibly readable and
has more comment than code, wow), but the actual amount of work you put at
stuff that is *not* code: documentation, benchmarking, implementation
explanations. Even the git log is clean and the unit tests run out of the box
on Python 2 and 3.
**Mark Summerfield**, a short plea for `Python Sorted Collections`_
Python's "batteries included" standard library seems to have a battery
missing. And the argument that "we never had it before" has worn thin. It is
time that Python offered a full range of collection classes out of the box,
including sorted ones.
`Sorted Containers`_ is used in popular open source projects such as:
`Zipline`_, an algorithmic trading library from Quantopian; `Angr`_, a binary
analysis platform from UC Santa Barbara; `Trio`_, an async I/O library; and
`Dask Distributed`_, a distributed computation library supported by Continuum
Analytics.
.. _`Fellow of the Python Software Foundation`: https://en.wikipedia.org/wiki/Alex_Martelli
.. _`simple, effective implementation`: http://www.grantjenks.com/docs/sortedcontainers/implementation.html
.. _`author of Writing Idiomatic Python and Python Trainer`: https://jeffknupp.com/
.. _`Python and Django Trainer`: https://www.elephorm.com/formateur/kevin-samuel
.. _`Python Sorted Collections`: http://www.qtrac.eu/pysorted.html
.. _`Zipline`: https://github.com/quantopian/zipline
.. _`Angr`: https://github.com/angr/angr
.. _`Trio`: https://github.com/python-trio/trio
.. _`Dask Distributed`: https://github.com/dask/distributed
Features
--------
- Pure-Python
- Fully documented
- Benchmark comparison (alternatives, runtimes, load-factors)
- 100% test coverage
- Hours of stress testing
- Performance matters (often faster than C implementations)
- Compatible API (nearly identical to older blist and bintrees modules)
- Feature-rich (e.g. get the five largest keys in a sorted dict: d.keys()[-5:])
- Pragmatic design (e.g. SortedSet is a Python set with a SortedList index)
- Developed on Python 3.7
- Tested on CPython 2.7, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7 and PyPy, PyPy3
.. image:: https://api.travis-ci.org/grantjenks/python-sortedcontainers.svg?branch=master
:target: http://www.grantjenks.com/docs/sortedcontainers/
.. image:: https://ci.appveyor.com/api/projects/status/github/grantjenks/python-sortedcontainers?branch=master&svg=true
:target: http://www.grantjenks.com/docs/sortedcontainers/
Quickstart
----------
Installing `Sorted Containers`_ is simple with `pip
<https://pypi.org/project/pip/>`_::
$ pip install sortedcontainers
You can access documentation in the interpreter with Python's built-in `help`
function. The `help` works on modules, classes and methods in `Sorted
Containers`_.
.. code-block:: python
>>> import sortedcontainers
>>> help(sortedcontainers)
>>> from sortedcontainers import SortedDict
>>> help(SortedDict)
>>> help(SortedDict.popitem)
Documentation
-------------
Complete documentation for `Sorted Containers`_ is available at
http://www.grantjenks.com/docs/sortedcontainers/
User Guide
..........
The user guide provides an introduction to `Sorted Containers`_ and extensive
performance comparisons and analysis.
- `Introduction`_
- `Performance Comparison`_
- `Load Factor Performance Comparison`_
- `Runtime Performance Comparison`_
- `Simulated Workload Performance Comparison`_
- `Performance at Scale`_
.. _`Introduction`: http://www.grantjenks.com/docs/sortedcontainers/introduction.html
.. _`Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance.html
.. _`Load Factor Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance-load.html
.. _`Runtime Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance-runtime.html
.. _`Simulated Workload Performance Comparison`: http://www.grantjenks.com/docs/sortedcontainers/performance-workload.html
.. _`Performance at Scale`: http://www.grantjenks.com/docs/sortedcontainers/performance-scale.html
Community Guide
...............
The community guide provides information on the development of `Sorted
Containers`_ along with support, implementation, and history details.
- `Development and Support`_
- `Implementation Details`_
- `Release History`_
.. _`Development and Support`: http://www.grantjenks.com/docs/sortedcontainers/development.html
.. _`Implementation Details`: http://www.grantjenks.com/docs/sortedcontainers/implementation.html
.. _`Release History`: http://www.grantjenks.com/docs/sortedcontainers/history.html
API Documentation
.................
The API documentation provides information on specific functions, classes, and
modules in the `Sorted Containers`_ package.
- `Sorted List`_
- `Sorted Dict`_
- `Sorted Set`_
.. _`Sorted List`: http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html
.. _`Sorted Dict`: http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html
.. _`Sorted Set`: http://www.grantjenks.com/docs/sortedcontainers/sortedset.html
Talks
-----
- `Python Sorted Collections | PyCon 2016 Talk`_
- `SF Python Holiday Party 2015 Lightning Talk`_
- `DjangoCon 2015 Lightning Talk`_
.. _`Python Sorted Collections | PyCon 2016 Talk`: http://www.grantjenks.com/docs/sortedcontainers/pycon-2016-talk.html
.. _`SF Python Holiday Party 2015 Lightning Talk`: http://www.grantjenks.com/docs/sortedcontainers/sf-python-2015-lightning-talk.html
.. _`DjangoCon 2015 Lightning Talk`: http://www.grantjenks.com/docs/sortedcontainers/djangocon-2015-lightning-talk.html
Resources
---------
- `Sorted Containers Documentation`_
- `Sorted Containers at PyPI`_
- `Sorted Containers at Github`_
- `Sorted Containers Issue Tracker`_
.. _`Sorted Containers Documentation`: http://www.grantjenks.com/docs/sortedcontainers/
.. _`Sorted Containers at PyPI`: https://pypi.org/project/sortedcontainers/
.. _`Sorted Containers at Github`: https://github.com/grantjenks/python-sortedcontainers
.. _`Sorted Containers Issue Tracker`: https://github.com/grantjenks/python-sortedcontainers/issues
Sorted Containers License
-------------------------
Copyright 2014-2019 Grant Jenks
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
|
