8000 Immutable TreeMap/TreeSet performance (SI-5331) by erikrozendaal · Pull Request #82 · scala/scala · GitHub
[go: up one dir, main page]
Skip to content

Immutable TreeMap/TreeSet performance (SI-5331) #82

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.

Sign up for GitHub

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

Merged
merged 37 commits into from
Feb 16, 2012
Merged

Immutable TreeMap/TreeSet performance (SI-5331) #82

Changes from 1 commit
Commits
Show all changes
37 commits
Select commit Hold shift + click to select a range
540ad02
Use RedBlack.iterator to create iterators for TreeSet/TreeMap.
erikrozendaal Dec 17, 2011
88ed930
Use custom implementation for iterating over RedBlack trees. Raw
erikrozendaal Dec 17, 2011
edcec03
Optimized implementations of head/headOption/last/lastOption for
erikrozendaal Dec 17, 2011
9cdede8
Optimized implementation of init/tail for TreeSet/TreeMap.
erikrozendaal Dec 17, 2011
b7e6714
RedBlack.scala: Change count from 'def' to 'val' in NonEmpty tree
erikrozendaal Dec 17, 2011
95cb7bc
Implemented drop/take/slice/splitAt/dropRight/takeRight for
erikrozendaal Dec 18, 2011
8d67823
Implemented takeWhile/dropWhile/span to use tree splitting. This
erikrozendaal Dec 18, 2011
3f66061
Switched from isSmaller to ordering.
erikrozendaal Dec 19, 2011
7ec9b0b
Moved from implicit ordering value to implicit parameter.
erikrozendaal Dec 19, 2011
a02a815
Moved from Empty case object to case class in preparation of moving
erikrozendaal Dec 19, 2011
418adc6
Moved type parameter A from RedBlack to Tree.
erikrozendaal Dec 19, 2011
6c0e036
Changed abstract class RedBlack to singleton object.
erikrozendaal Dec 19, 2011
d2706db
Use single shared Empty instance across all RedBlack trees.
erikrozendaal Dec 19, 2011
6b95074
Make sure the redblack test compiles and runs.
erikrozendaal Dec 21, 2011
b9699f9
Made RedBlack private to the scala.collection.immutable package.
erikrozendaal Dec 27, 2011
32171c2
TreeMap/TreeSet no longer keep track of the size (the RedBlack tree
erikrozendaal Dec 27, 2011
b421bba
Performance improvements for iteration (foreach and iterator).
erikrozendaal Dec 27, 2011
4a0c4bb
Improved performance of RedBlack.NonEmpty.nth (helps take/drop/split/…
erikrozendaal Dec 27, 2011
ad0b09c
Added some tests for TreeMap/TreeSet.
erikrozendaal Dec 28, 2011
c51bdea
Minimize number of calls to ordering.
erikrozendaal Dec 28, 2011
6d8dca7
Moved key/value/left/right fields up to NonEmpty class. Don't rely
erikrozendaal Jan 2, 2012
82374ad
Implemented deletes without pattern matching.
erikrozendaal Jan 2, 2012
3dea251
Implemented range without using pattern matching.
erikrozendaal Jan 2, 2012
5c05f66
Use null to represent empty trees. Removed Empty/NonEmpty classes.
erikrozendaal Jan 2, 2012
72ec0ac
Optimize foreach and iterators.
erikrozendaal Jan 4, 2012
d735d0f
Move nth method to RedBlack. Inline factories for tree nodes.
erikrozendaal Jan 5, 2012
388ff47
Add implementation notes. Consistently use eq/ne to compare with null.
erikrozendaal Jan 5, 2012
7e92b3c
Deprecate TreeMap.isSmaller and TreeSet.isSmaller.
erikrozendaal Jan 6, 2012
f656142
Restore old RedBlack class to maintain backwards compatibility.
erikrozendaal Jan 6, 2012
288874d
Renamed object RedBlack to RedBlackTree.
erikrozendaal Jan 7, 2012
e61075c
Tests for takeWhile/dropWhile/span.
erikrozendaal Jan 7, 2012
8b3f984
Fix silly copy-paste error.
erikrozendaal Jan 7, 2012
f26f610
Test for maximum height of red-black tree.
erikrozendaal Jan 8, 2012
00b5cb8
Optimized implementation of TreeMap/TreeSet#to method.
erikrozendaal Jan 15, 2012
7824dbd
Custom coded version of range/from/to/until.
erikrozendaal Jan 21, 2012
78374f3
Custom implementations of drop/take/slice.
erikrozendaal Jan 22, 2012
51667dc
Removed TODOs.
erikrozendaal Jan 24, 2012
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
8000
Prev Previous commit
Next Next commit
Improved performance of RedBlack.NonEmpty.nth (helps take/drop/split/… 
…etc).
  • Loading branch information
@erikrozendaal
erikrozendaal committed Dec 28, 2011
commit 4a0c4bbd092af26c8c6eea10e668e2cbc3c366a7
5 changes: 3 additions & 2 deletions src/library/scala/collection/immutable/RedBlack.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -262,8 +262,9 @@ object RedBlack {
def last = if (right eq Empty.Instance) key else right.last
val count = 1 + left.count + right.count
protected[immutable] def nth(n: Int) = {
if (n < left.count) left.nth(n)
else if (n > left.count) right.nth(n - left.count - 1)
val count = left.count
if (n < count) left.nth(n)
else if (n > count) right.nth(n - count - 1)
else this
}
}
Expand Down
0