Skip to content

Optimize ColorMap - #1648

Merged
lossyrob merged 10 commits into
locationtech:masterfrom
fosskers:fix/cgw/optimize-colormap
Oct 5, 2016
Merged

Optimize ColorMap#1648
lossyrob merged 10 commits into
locationtech:masterfrom
fosskers:fix/cgw/optimize-colormap

Conversation

@fosskers

@fosskers fosskers commented Oct 3, 2016 •
edited
Loading

Copy link
Copy Markdown
Contributor

TODO

Let: k be the number of pixels to colour, and n the number of colour breaks, where usually k > n by several orders of magnitude

  • Use a TrieMap to memoize IntColorMap.map results
    • Worst case (all unique pixel values): O(kn)
    • Best case (all pixels same value): O(k + n)
  • Write BTree[T]
  • Use a custom BTree for DoubleColorMap
    • Via B-tree: O(nlogn + klogn) == O((n + k)logn) ~= O(klogn)
  • Fix tests
  • BTree.pretty should return String
  • Use BTree for IntColorMap

Motivation

This addresses #1489 . Currently every call to IntColorMap.map or DoubleColorMap.map performs a O(n) search for the correct colour ramp value, given some raster's pixel value. The total cost to colour a raster is then O(kn).

Next Steps

Use Spire to generalize over Int and Double?

fosskers added 10 commits October 3, 2016 08:29
@fosskers
(color map) Optimize IntColorMap
f91dcb7 
- Memoize the results of `map` in a `TrieMap` for faster subsequent lookups.
A more involved custom binary search could be employed for faster lookups in
`DoubleColorMap`, as it can't take advantage of `TrieMap` in the same way.
@fosskers
(color map) Implemented a balanced, immutable BTree
b526c92
@fosskers
(color map) Added BTree.searchWith
8b0b413 
- A generalized binary search with a custom "target test" predicate.
@fosskers
(color map) Much simpler API for BTree.searchWith
c529c5d
@fosskers
(color map) Use BTree in DoubleColorMap.map
4ec6d85
@fosskers
(color map) Made BTree.searchWith branch predicate into a val
dd9cf0f
@fosskers
(color map) Use correct branching logic
b2c21b5 
- Also, `BTree` can print itself now. Should convert to returning a `String`
instead.
@fosskers
(color map) BTree.pretty returns a String
3b95ac3
@fosskers
(color map) Be more terse about BTree.pretty
3db79ef
@fosskers
(color map) Use BTree for IntColorMap as well
9ed445e
@fosskers fosskers changed the title [WIP] Optimize ColorMap Optimize ColorMap Oct 5, 2016
@fosskers

fosskers commented Oct 5, 2016 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

Bonus, BTrees have a nice string representation:

└── 4
    ├── 6
    │   ├── 7
    │   │   ├── ∅
    │   │   └── ∅
    │   └── 5
    │       ├── ∅
    │       └── ∅
    └── 2
        ├── 3
        │   ├── ∅
        │   └── ∅
        └── 1
            ├── ∅
            └── ∅

@fosskers

fosskers commented Oct 5, 2016

Copy link
Copy Markdown
Contributor Author

Don't merge yet: I still need to run benchmarks.

@fosskers

fosskers commented Oct 5, 2016 •
edited
Loading

Copy link
Copy Markdown
Contributor Author 
1280x1280 pixel Tile, 50 Breaks, 5 trials each, same JVM

 ORIGINAL LINEAR
 ---------------
 Rendering => 176.53 ms
 Rendering => 180.56 ms
 Rendering => 170.98 ms
 Rendering => 170.94 ms
 Rendering => 170.47 ms

 Mean: 173.89 ms

 WITH BTREE
 ----------
 Rendering => 120.25 ms
 Rendering => 117.32 ms
 Rendering => 121.19 ms
 Rendering => 117.35 ms
 Rendering => 116.86 ms

 Mean: 118.6 ms

 Speedup: ~47%

@lossyrob
lossyrob merged commit b88c3dc into locationtech:master Oct 5, 2016
@lossyrob lossyrob added this to the 1.0 milestone Oct 18, 2016
@fosskers fosskers mentioned this pull request Oct 19, 2016
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

1.0

Development

Successfully merging this pull request may close these issues.

2 participants

@fosskers @lossyrob