bytestring-trie icon indicating copy to clipboard operation
bytestring-trie copied to clipboard

Asymptotic complexity of functions deleting values

Open wrengr opened this issue 2 years ago • 1 comments

When using the internal functions arc, arc_, arcNN, or prepend to rebuild the spine after deleting values, under certain circumstances we can end up chaining those together and thus encounter an asymptotic slowdown similar to #25 (albeit greatly reduced in scope and severity). However, unlike #25, the bug here is not intrinsic to the data structure. We should be able to adjust those functions to behave more like a zipper, and only do the bytestring concatenation once an arc is "complete" (akin to the use of RevLazyByteString in the priority-queue functions).

wrengr avatar Dec 15 '21 05:12 wrengr