New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
TreeMap from, to and range methods are O(n) instead O(log n) #4026
Comments
Imported From: https://issues.scala-lang.org/browse/SI-4026?orig=1 |
@axel22 said: Have you tried this with the trunk, after a recent commit: |
@dcsobral said:
Actually, that was a different issue. The original The problem referred to is here ( val ntree = tree.range(from,until)
new TreeMap[A,B](ntree.count, ntree) Specifically, that It would make the memory footprint of |
@axel22 said: But, as far as the memory footprint goes, currently I wouldn't say that would hurt the memory footprint considerably, since clients of red black trees are already aware of them. So, I'd vote for adding the |
@retronym said: |
Calls to
TreeMap.from
,TreeMap.to
,TreeMap.range
run in timeO(n)
with respect of number of the items in the returned subtree.Valuable comment from Nathan Bronson, I got on the scala-user discussion list:
Expected behaviour: the time should be
O(log n)
with respect to the number of all items in the tree.Reproducibility: always.
How to reproduce: Create a large
TreeMap
and call one of the mentioned methods, to return a large portion of the tree.What versions of the following are you using?
Scala: 2.8.1.final
Java: 1.6.0 update 22 (both server and client)
Operating system: Windows Vista Home Premium
The text was updated successfully, but these errors were encountered: