Comments (9)
This is exactly why I suggested the slicing approach (another name change, but slicing is better as subsetting, as you have said) -- because slicing can be done quickly (in amortized constant time per level).
Nevertheless, the problem is, that after we have shaved some amount of the FingerTree, the Nodes are becomming deeper, so lookup in the tree being shaved is taking more time O(depth of current Nodes), which will be probably something like O(levels that were traversed to get to this spot). Well -- that would actually work, because for a node at level i, the lookup time would be O(i) to get that deep, O(i) to perform the slicing and O(i) to perform lookup in the Nodes of the tree being shaved, which have O(i) bound. This is all based on the fact that when we traversed to the depth d of the "original" tree (not being sliced), we could have only traversed O(d) leves in the tree being sliced, which I think is true.
from containers.
There's still a tradeoff with memory behavior, which seems to me a bigger
potential nastiness, but you might be able to convince me.
from containers.
I've thought about this a bit more, and I'm increasingly skeptical about our chances of doing much better. There's an inherent challenge that finger trees having the same number of elements can have different structures at all scales. It might (I'm not sure) be possible to get better constant factors with slicing, but I'm pretty sure you won't get better than polylogarithmic immediate indexing.
from containers.
Well it can hardly be better than polylogarithmic :-) But I believe we can make it log(i) instead of log(i)^2, where i is the lesser distance of an indexed element from either end of the sequence.
It is true that the structure can be different, but there are still both upper and lower bounds, which guarantee that if an element is in depth d in one structure of size n, it is in depth \Theta(d) in any structure of size n.
What I am not 100% sure is whether the constant factors of the slicing factor would be better -- the slicing checks will take some time. So it may happen that the splitting approach would work better for sequences of depth <= 3 for example.
from containers.
I still don't see how you're going to be able to use slicing to get all the
way to O(log(min{i,n-i})) without breaking the O(n) total. Explain? One
other constant-factor cost of slicing is the memory to hold the slice
constructors—it's not huge, but it's there.
from containers.
Oh, you are right that the straightforward O(log(min{i,n-i})) will be O(n log n) in total, because the deep _Node_s are not split and will therefore cause the O(n log n). In order to get O(n), one would have to split the deep _Node_s too, and I am not sure that even that would guarantee O(n).
If someone ever has desire to try this, we will see the numbers :-)
from containers.
Well, you can try the naive way very easily using
zipWith' f xs ys = mapWithIndex (\i x -> f x $ ys `index` i) xs
from containers.
It is true that the structure can be different, but there are still both upper and lower bounds, which guarantee that if an element is in depth d in one structure of size n, it is in depth \Theta(d) in any structure of size n.
This is what keeps me wondering if there's some kind of magic trick I'm missing, but every time I try to think of a way around this, something seems to get in the way. It's driving me nuts.
from containers.
I don't think this is going anywhere anytime soon. It probably can't get too much better.
from containers.
Related Issues (20)
- Symmetric difference for sets
- Incorrect order of Applicative actions in mergeA when using filterAMissing HOT 4
- `IntMap` `isProperSubmapOfBy` test failure HOT 4
- More accurate Set and Map size warnings HOT 3
- Complexity of IntMap-IntMap operations
- Is this repo up to date? HOT 7
- Consider maintaining the x.y.z.a versioning HOT 7
- Rewrite rules for IntMap: intersectionWithKey/mapWithKey HOT 8
- Faster Eq and Ord HOT 4
- Tidy up IntSet/IntMap bitwise stuff
- Improve strictness tests HOT 4
- Data.Map.Strict.mergeWithKey does not force the result of the combining function HOT 5
- Add "Unsafe" modules HOT 6
- mapKeys can be more efficient HOT 1
- Data.Map.Internal does not export insertMin HOT 1
- Repo: remove merged branches?
- Contribution guide outdated?
- Potential memory optimization for IntMap and IntSet HOT 8
- Errors when trying to generate a test coverage report HOT 10
- Full IntSets? HOT 5
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from containers.