perform experiments to evaluate the performance of CRDT editing librarys.
simulate the editing of a text, perform N edits to an array. normally, inserting another token immediately after the preceding token, but jumping to another position with probabilty J.
between and bisecting-between are compared.
between
performs better when there is a high probability of an insert
With 10% jumps, the better algorithm becomes bisecting. Running this test multiple times sometimes produces a different result.
after the chance of jump gets lower, bisecting-between
becomes clearly more efficient.
experiment to find the performance of between vs bisect as a function of J. from J=0.5 to 0.01 perform 1000 random inserts. run each trial 20 times, and calculate stdev.
This shows the mean performance for between cross bisect at about 7.5% (used % here, due to limitations of graph generating library)
between is significantly more efficient to the right of that point, but curves upwards dramatically when J get lower.
study the uncertainty in the inflection point by showing bounds in the graph (value+-stdev) and see where that overlaps.
Maybe rerun the experiments with deterministic randoness so that the algorithms can be compared across the same set of edits.
MIT