Metadata-Version: 2.2 Name: orderly-set Version: 5.3.0 Summary: Orderly set Home-page: https://github.com/seperman/orderly-set Download-URL: https://github.com/seperman/orderly-set/tarball/master Author: Seperman Author-email: sep@zepworks.com License: MIT Classifier: Intended Audience :: Developers Classifier: Operating System :: OS Independent Classifier: Topic :: Software Development Classifier: Programming Language :: Python :: 3.8 Classifier: Programming Language :: Python :: 3.9 Classifier: Programming Language :: Python :: 3.10 Classifier: Programming Language :: Python :: 3.11 Classifier: Programming Language :: Python :: 3.12 Classifier: Programming Language :: Python :: Implementation :: PyPy Classifier: Development Status :: 5 - Production/Stable Classifier: License :: OSI Approved :: MIT License Requires-Python: >=3.8 Description-Content-Type: text/markdown License-File: AUTHORS.md Dynamic: author Dynamic: author-email Dynamic: classifier Dynamic: description Dynamic: description-content-type Dynamic: download-url Dynamic: home-page Dynamic: license Dynamic: requires-python Dynamic: summary # Orderly Set 5.3.0 Orderly Set is a package containing multiple implementations of Ordered Set. ## OrderlySet This implementation keeps the order in all set operations except set difference operations. As a result, it can do set difference operations much faster than other implementations. Still 2X slower than of Python's built-in set. ## StableSet A StableSet is a mutable set that remembers its insertion order. Featuring: Fast O(1) insertion, deletion, iteration and membership testing. But slow O(N) Index Lookup. ## StableSetEq Same as StableSet but the order of items doesn't matter for equality comparisons. ## OrderedSet An OrderedSet is a mutable data structure that is a hybrid of a list and a set. It remembers its insertion order so that every entry has an index that can be looked up. Featuring: O(1) Index lookup, insertion, iteration and membership testing. But slow O(N) Deletion. ## SortedSet SortedSet is basically set but when printed, turned into string, or iterated over, returns the items in alphabetical order. # Installation `pip install orderly-set` # Usage examples An OrderedSet is created and used like a set: >>> from orderly_set import OrderedSet >>> letters = OrderedSet('abracadabra') >>> letters OrderedSet(['a', 'b', 'r', 'c', 'd']) >>> 'r' in letters True It is efficient to find the index of an entry in an OrderedSet, or find an entry by its index. To help with this use case, the `.add()` method returns the index of the added item, whether it was already in the set or not. >>> letters.index('r') 2 >>> letters[2] 'r' >>> letters.add('r') 2 >>> letters.add('x') 5 OrderedSets implement the union (`|`), intersection (`&`), and difference (`-`) operators like sets do. >>> letters |= OrderedSet('shazam') >>> letters OrderedSet(['a', 'b', 'r', 'c', 'd', 'x', 's', 'h', 'z', 'm']) >>> letters & set('aeiou') OrderedSet(['a']) >>> letters -= 'abcd' >>> letters OrderedSet(['r', 'x', 's', 'h', 'z', 'm']) The `__getitem__()` and `index()` methods have been extended to accept any iterable except a string, returning a list, to perform NumPy-like "fancy indexing". >>> letters = OrderedSet('abracadabra') >>> letters[[0, 2, 3]] ['a', 'r', 'c'] >>> letters.index(['a', 'r', 'c']) [0, 2, 3] OrderedSet implements `__getstate__` and `__setstate__` so it can be pickled, and implements the abstract base classes `collections.MutableSet` and `collections.Sequence`. OrderedSet can be used as a generic collection type, similar to the collections in the `typing` module like List, Dict, and Set. For example, you can annotate a variable as having the type `OrderedSet[str]` or `OrderedSet[Tuple[int, str]]`. # Authors Please check the [Authors](AUTHORS.md) file. # Comparisons ``` -- initialize a set -- Using Python dict time: 4.13 set time: 2.98 ordered_set.OrderedSet time: 15.77 orderly_set.OrderedSet time: 15.25 StableSet time: 4.78 OrderlySet time: 4.38 SortedSet time: 3.09 -- update a set -- Using Python dict: 6.77 set time: 2.46 ordered_set.OrderedSet time: 10.17 orderly_set.OrderedSet time: 10.06 StableSet time: 7.16 OrderlySet time: 6.77 SortedSet time: 2.46 -- update a set and get item -- ordered_set.OrderedSet time: 29.98 orderly_set.OrderedSet time: 29.57 StableSet time: 14.31 OrderlySet time: 14.23 SortedSet time: 9.03 -- set symmetric difference (xor) -- set time: 5.368663903005654 ordered_set.OrderedSet time: 39.25 orderly_set.OrderedSet time: 80.31 StableSet time: 42.81 OrderlySet time: 11.44 SortedSet time: 3.87 -- set difference (-) -- set time: 3.7398674299911363 ordered_set.OrderedSet time: 22.39 orderly_set.OrderedSet time: 38.00 StableSet time: 22.30 OrderlySet time: 8.92 SortedSet time: 3.03 ``` Despite what you see in the benchmarks, in DeepDiff OrderlySet performed better than SortedSet. A StableSet is a mutable set that remembers its insertion order. Featuring: Fast O(1) insertion, deletion, iteration and membership testing. But slow O(N) Index Lookup. An OrderedSet is a mutable data structure that is a hybrid of a list and a set. It remembers its insertion order so that every entry has an index that can be looked up. Featuring: O(1) Index lookup, insertion, iteration and membership testing. But slow O(N) Deletion. Both have similar interfaces but differ in respect of their implementation and performance. The original implementation of OrderedSet was a [recipe posted to ActiveState Recipes][recipe] by Raymond Hettiger, released under the MIT license. [recipe]: https://code.activestate.com/recipes/576694-orderedset/ Hettiger's implementation kept its content in a doubly-linked list referenced by a dict. As a result, looking up an item by its index was an O(N) operation, while deletion was O(1). This version of OrderedSet makes different trade-offs for the sake of efficient lookups. Its content is a standard Python list instead of a doubly-linked list. This provides O(1) lookups by index at the expense of O(N) deletion, as well as slightly faster iteration.