Closed albertwoo closed 2 years ago
I also ran into that issue yesterday, I'll investigate what can be done about it. Basically it's a thread deleting unused Indices from the double-linked-list which could also be done synchronously when threads are not supported. I'm quite busy today & tomorrow so it'll take a few days...
Cool, thanks!!!
What would be an alternative implementation of Index (except for real numbers)?
On fable we used rationals with bigint, but that's not really optimal due to memory and non-constant comparison runtimes.
Essentially Index represents real numbers, so i can't think of anything without relabeling really...
Our implementation isn't asymptotically optimal O(log^2 N)
(amortized) for insertions, but the O(1)
implementations out there were just too complicated.
Could you please point me to some O(1)
implementations (a paper, blogpost, etc.)?
The original paper is called "Maintaining order in a generalized linked list" by Athanasios K. Tsakalidis but sadly i can't find a working link to a PDF anymore
also, i think acar et al. used an implementation based on Dietz and Sleator "Two Algorithms for Maintaining Order in a List" (1988) In 2002, Bender et al. took up on this again, in Two Simplified Algorithms for Maintaining order in a list", https://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf There is also an implementation in a paper actually working on immutable arrays which i can't find anymore (see below). Janestreet's incremental also has order maintenance they tweaked several times according to their videos (e.g. link).
Found it O'Neill and Burton, A new Method for Functional Arrays- First off, this paper gives a good overview of related work, secondly in its appendinx it revisits the list order problem starts with O(log n)
and later refines to O(1)
.
Btw @albertwoo i had a little time to spare today and switched to a task-based implementation for the Index-deletion, so everything should be fine now in package version 1.2.8
Sadly I had some trouble with the automated package push, so the github release might be missing
@krauthaufen Thanks, it works great now. 👍
I am using this library with blazor WASM, and got below error:
Looks like we cannot run this in WASM: https://github.com/fsprojects/FSharp.Data.Adaptive/blob/a4807a26e9eec83a7cf5aa150ff151e51c97c0b1/src/FSharp.Data.Adaptive/Datastructures/Index.fs#L174
Any suggestion for this?