A python implementation of Operational Transformation.
Project description
Python-OTType
A python library for Operational Transformation (OT). Basic idea follows the spec at https://github.com/ottypes/docs.
Installation
pip install ottype
OT Operations
Skip
Object type : int
Skip n
characters from the current position is represented as n
assert apply('asdf', [3]) == 'asdf'
Insert
Object type : str
Insert a string s
at the current position is represented as s
assert apply('asdf', ['qwer']) == 'qwerasdf'
assert apply('asdf', [2, 'qwer']) == 'asqwerdf'
Delete
Object type : dict
Delete a string s
at the current position is represented as {'d': s}
assert apply('asdf', [{'d': 'as'}]) == 'df'
assert apply('asdf', [1, {'d': 'sd'}]) == 'af'
Supported Functions
OT = Union[int, str, dict]
check(ots: List[OT], *, check_unoptimized: bool = True) -> bool
Check a list whether it only contains valid OTs. If check_unoptimized
is True
, only normalized list of OTs is accepted.
assert check(['a', 4, 'b'])
assert not check(['a', 'b']) # is not normalized
assert not check([3]) # is not normalized
apply(doc: str, ots: List[OT]) -> str
Apply a list of OTs to a string.
assert apply('abcde', [2, 'qq', {'d': 'c'}, 1, 'w']) == 'abqqdwe'
inverse_apply(doc: str, ots: List[OT]) -> str
Inversely apply a list of OTs to a string.
assert inverse_apply(apply(doc, ots), ots) == doc
normalize(ots: List[OT]) -> List[OT]
Normalize a list of OTs : merge consecutive OTs and trim the last skip operation.
assert normalize([1, 2, 'as', 'df', {'d': 'qw'}, {'d': 'er'}, 3]) \
== [3, 'asdf', {'d': 'qwer'}]
transform(ots1: List[OT], ots2: List[OT]) -> List[OT]
Transform a list of OTs with the property:
assert apply(apply(doc, ots1), transform(ots2, ots1, 'left')) \
== apply(apply(doc, ots2), transform(ots1, ots2, 'right'))
compose(ots1: List[OT], ots2: List[OT]) -> List[OT]
Compose two list of OTs with the property:
assert apply(apply(doc, ots1), ots2) == apply(doc, compose(ots1, ots2))
Benchmark (at Python 3.7)
apply
function
=== baseline ===
Doc Length : 100, OT Length : 5, Performance : 5.80 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 10, Performance : 8.87 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 20, Performance : 16.47 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 50, Performance : 39.13 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 100, Performance : 73.84 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 5, Performance : 4.70 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 10, Performance : 7.46 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 20, Performance : 14.55 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 50, Performance : 50.22 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 100, Performance : 83.51 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 5, Performance : 7.43 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 10, Performance : 13.05 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 20, Performance : 18.66 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 50, Performance : 41.28 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 100, Performance : 97.67 ms/loop ( 1.00x )
=== python ===
Doc Length : 100, OT Length : 5, Performance : 6.77 ms/loop ( 0.86x )
Doc Length : 100, OT Length : 10, Performance : 15.48 ms/loop ( 0.57x )
Doc Length : 100, OT Length : 20, Performance : 27.14 ms/loop ( 0.61x )
Doc Length : 100, OT Length : 50, Performance : 54.14 ms/loop ( 0.72x )
Doc Length : 100, OT Length : 100, Performance : 84.28 ms/loop ( 0.88x )
Doc Length : 1000, OT Length : 5, Performance : 4.23 ms/loop ( 1.11x )
Doc Length : 1000, OT Length : 10, Performance : 8.74 ms/loop ( 0.85x )
Doc Length : 1000, OT Length : 20, Performance : 18.65 ms/loop ( 0.78x )
Doc Length : 1000, OT Length : 50, Performance : 37.61 ms/loop ( 1.34x )
Doc Length : 1000, OT Length : 100, Performance : 82.60 ms/loop ( 1.01x )
Doc Length : 10000, OT Length : 5, Performance : 8.86 ms/loop ( 0.84x )
Doc Length : 10000, OT Length : 10, Performance : 13.19 ms/loop ( 0.99x )
Doc Length : 10000, OT Length : 20, Performance : 20.43 ms/loop ( 0.91x )
Doc Length : 10000, OT Length : 50, Performance : 48.91 ms/loop ( 0.84x )
Doc Length : 10000, OT Length : 100, Performance : 102.81 ms/loop ( 0.95x )
=== cython ===
Doc Length : 100, OT Length : 5, Performance : 0.77 ms/loop ( 7.55x )
Doc Length : 100, OT Length : 10, Performance : 1.36 ms/loop ( 6.53x )
Doc Length : 100, OT Length : 20, Performance : 2.34 ms/loop ( 7.04x )
Doc Length : 100, OT Length : 50, Performance : 4.74 ms/loop ( 8.25x )
Doc Length : 100, OT Length : 100, Performance : 9.73 ms/loop ( 7.59x )
Doc Length : 1000, OT Length : 5, Performance : 0.70 ms/loop ( 6.75x )
Doc Length : 1000, OT Length : 10, Performance : 1.61 ms/loop ( 4.64x )
Doc Length : 1000, OT Length : 20, Performance : 2.47 ms/loop ( 5.88x )
Doc Length : 1000, OT Length : 50, Performance : 5.52 ms/loop ( 9.10x )
Doc Length : 1000, OT Length : 100, Performance : 9.02 ms/loop ( 9.26x )
Doc Length : 10000, OT Length : 5, Performance : 2.20 ms/loop ( 3.38x )
Doc Length : 10000, OT Length : 10, Performance : 2.57 ms/loop ( 5.07x )
Doc Length : 10000, OT Length : 20, Performance : 2.95 ms/loop ( 6.33x )
Doc Length : 10000, OT Length : 50, Performance : 5.97 ms/loop ( 6.92x )
Doc Length : 10000, OT Length : 100, Performance : 10.92 ms/loop ( 8.94x )
inverse_apply
function
=== baseline ===
Doc Length : 100, OT Length : 5, Performance : 8.26 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 10, Performance : 15.00 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 20, Performance : 27.50 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 50, Performance : 56.86 ms/loop ( 1.00x )
Doc Length : 100, OT Length : 100, Performance : 129.10 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 5, Performance : 6.35 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 10, Performance : 16.14 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 20, Performance : 22.65 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 50, Performance : 67.26 ms/loop ( 1.00x )
Doc Length : 1000, OT Length : 100, Performance : 113.74 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 5, Performance : 8.79 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 10, Performance : 10.16 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 20, Performance : 22.46 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 50, Performance : 54.26 ms/loop ( 1.00x )
Doc Length : 10000, OT Length : 100, Performance : 129.20 ms/loop ( 1.00x )
=== python ===
Doc Length : 100, OT Length : 5, Performance : 6.05 ms/loop ( 1.37x )
Doc Length : 100, OT Length : 10, Performance : 11.30 ms/loop ( 1.33x )
Doc Length : 100, OT Length : 20, Performance : 21.16 ms/loop ( 1.30x )
Doc Length : 100, OT Length : 50, Performance : 44.43 ms/loop ( 1.28x )
Doc Length : 100, OT Length : 100, Performance : 101.05 ms/loop ( 1.28x )
Doc Length : 1000, OT Length : 5, Performance : 10.06 ms/loop ( 0.63x )
Doc Length : 1000, OT Length : 10, Performance : 12.38 ms/loop ( 1.30x )
Doc Length : 1000, OT Length : 20, Performance : 24.55 ms/loop ( 0.92x )
Doc Length : 1000, OT Length : 50, Performance : 42.64 ms/loop ( 1.58x )
Doc Length : 1000, OT Length : 100, Performance : 96.43 ms/loop ( 1.18x )
Doc Length : 10000, OT Length : 5, Performance : 9.42 ms/loop ( 0.93x )
Doc Length : 10000, OT Length : 10, Performance : 11.89 ms/loop ( 0.85x )
Doc Length : 10000, OT Length : 20, Performance : 25.74 ms/loop ( 0.87x )
Doc Length : 10000, OT Length : 50, Performance : 58.58 ms/loop ( 0.93x )
Doc Length : 10000, OT Length : 100, Performance : 97.37 ms/loop ( 1.33x )
=== cython ===
Doc Length : 100, OT Length : 5, Performance : 1.12 ms/loop ( 7.37x )
Doc Length : 100, OT Length : 10, Performance : 1.69 ms/loop ( 8.90x )
Doc Length : 100, OT Length : 20, Performance : 2.80 ms/loop ( 9.82x )
Doc Length : 100, OT Length : 50, Performance : 5.49 ms/loop ( 10.35x )
Doc Length : 100, OT Length : 100, Performance : 12.22 ms/loop ( 10.56x )
Doc Length : 1000, OT Length : 5, Performance : 1.36 ms/loop ( 4.68x )
Doc Length : 1000, OT Length : 10, Performance : 2.25 ms/loop ( 7.19x )
Doc Length : 1000, OT Length : 20, Performance : 2.98 ms/loop ( 7.61x )
Doc Length : 1000, OT Length : 50, Performance : 6.26 ms/loop ( 10.75x )
Doc Length : 1000, OT Length : 100, Performance : 11.14 ms/loop ( 10.21x )
Doc Length : 10000, OT Length : 5, Performance : 2.35 ms/loop ( 3.75x )
Doc Length : 10000, OT Length : 10, Performance : 3.62 ms/loop ( 2.81x )
Doc Length : 10000, OT Length : 20, Performance : 4.50 ms/loop ( 4.99x )
Doc Length : 10000, OT Length : 50, Performance : 7.07 ms/loop ( 7.68x )
Doc Length : 10000, OT Length : 100, Performance : 14.20 ms/loop ( 9.10x )
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for python_ottype-20.5.0-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 624ce3a0c49b72ab56b58ad4a1406acc915331df67f74c9926e35eac92d0fd15 |
|
MD5 | ed0a4ddde0ca5f3d31f6be33f799de0b |
|
BLAKE2b-256 | 798a3e73ebb228c7a5e0e07b20d61969fb575823c2bc7dc7c48a22d80aa7f87e |
Hashes for python_ottype-20.5.0-cp38-cp38-manylinux2010_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6779c0a901d00f68eedc4869aeb4349d7602771bc2d608fe8b08c7d93a39a57b |
|
MD5 | ea6b724c3614ef6b6ac805e1bc64f77f |
|
BLAKE2b-256 | 662dc98c6e600090330a03abe25c925a7bef32d6b1aab6dc52b4a09e1aca07f8 |
Hashes for python_ottype-20.5.0-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7eb9942eb8a4645b961171f845610b2a2aeff93a77ca618e2e20d762562200b0 |
|
MD5 | a4ef088cc2dff6171074e56dedb36b16 |
|
BLAKE2b-256 | 69112a2315b60c49510e2c77b7e78331b61179601803304b9330a5374a359c0c |
Hashes for python_ottype-20.5.0-cp38-cp38-manylinux1_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 32f03a80e29bd91007d804ec481ce29daffab2658f9e3e3b6fa6d995cf7dda7b |
|
MD5 | 54b7f5c30e150ed8e794e5570f385683 |
|
BLAKE2b-256 | 57f499cc8588098414921c65158a2ca22fdcdc72bad64f399ce48fff33fe5d8c |
Hashes for python_ottype-20.5.0-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c1bc7cf9544fa94766bc8efa7deeb0443e20cc6b3bc3fb979dd147018fc2b56 |
|
MD5 | 2f32c7de97d9d086e6f1a21ea13367d2 |
|
BLAKE2b-256 | 5868c7a19ccaefa9f59f04ee72c3c55beaa28058c45b84991a062e1a05442b98 |
Hashes for python_ottype-20.5.0-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 165570bdc4be349b45dd80d956135e71b7e67b6617e95b1196e9a2d7d0f91a22 |
|
MD5 | d1fba104dbcf430900eac8d69ccb5805 |
|
BLAKE2b-256 | 0ad0483f7f0e7a8b61a239e0cc90b600e4a10a3635496bbb53d31a55522d1633 |
Hashes for python_ottype-20.5.0-cp37-cp37m-manylinux1_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 039cc400920c2bc3b27f1b7ff3db2a8984be16fbe1c20ab36e789f22b115d99b |
|
MD5 | 066a88f32bde8228e7196d3b248ebc4c |
|
BLAKE2b-256 | 4d95e2331f8a4b9401b0598319bae5a5917e6c5be236650aa6301c2128a632a4 |