3 ms·
https://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-Sequence.html https://hackage.haskell.org/package/containers-0.6.5.1/docs/... log(n) slowdown
by savingsPossible 4y ago
https://hackage.haskell.org/package/containers-0.6.5.1/docs/Data-Sequence.html https://hackage.haskell.org/package/containers-0.6.5.1/docs/...
log(n) slowdown to add in the end
but the cost to add in the middle is cheaper then the trivial array (see insertAt)
- UncleMeat 4y agoThe asymptotic behavior is not the entire story. Because persistent data structures almost necessarily need to have their data allocated non-contiguously they have terrible cache performance and prefetching/speculation behavior in comparison to data structures that take advantage of contiguous memory locations. I also mentioned sets, not lists.
- savingsPossible 4y agoNot that this answers all your objections (it does not, caching might be a problem!) But sets are also a mere log(n) away https://hackage.haskell.org/package/containers-0.6.6/docs/Data-IntMap-Lazy.html https://hackage.haskell.org/package/containers-0.6.6/docs/Da...