[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17477344#comment-17477344
]
Matt Juntunen commented on GEOMETRY-142:
----------------------------------------
I tried a few more optimizations and it looks like {{varoctree}} is still the
best algorithm, especially since I improved the {{remove}} performance. The
final results are below.
||Benchmark||(dist)||(impl)||(randomSeed)||(shape)||Mode||Cnt||Score||Error||Units||
|get|random|treemap|1|teapot|avgt|5|8201248.381|± 885353.659|ns/op|
|get|random|varoctree|1|teapot|avgt|5|9954012.963|± 1467457.747|ns/op|
|get|random|kdtree|1|teapot|avgt|5|12047536.590|± 3986439.960|ns/op|
|get|random|rebuilding-kdtree|1|teapot|avgt|5|11241847.287|± 4950094.941|ns/op|
|get|random|bucket-kdtree|1|teapot|avgt|5|14269957.001|± 2984764.586|ns/op|
|get|random|bucket-leaf-kdtree|1|teapot|avgt|5|12613411.642|± 1912904.807|ns/op|
|put|random|treemap|1|teapot|avgt|5|4466342.881|± 829095.368|ns/op|
|put|random|varoctree|1|teapot|avgt|5|6498643.402|± 1110163.867|ns/op|
|put|random|kdtree|1|teapot|avgt|5|7788556.065|± 1568465.224|ns/op|
|put|random|rebuilding-kdtree|1|teapot|avgt|5|6924748.449|± 1312331.439|ns/op|
|put|random|bucket-kdtree|1|teapot|avgt|5|8580674.695|± 3265464.066|ns/op|
|put|random|bucket-leaf-kdtree|1|teapot|avgt|5|6440019.212|± 3284091.562|ns/op|
|remove|random|treemap|1|teapot|avgt|5|160111.447|± 14035.741|ns/op|
|remove|random|varoctree|1|teapot|avgt|5|191145.633|± 45804.812|ns/op|
|remove|random|kdtree|1|teapot|avgt|5|164994.365|± 78422.804|ns/op|
|remove|random|rebuilding-kdtree|1|teapot|avgt|5|197497.579|± 86483.448|ns/op|
|remove|random|bucket-kdtree|1|teapot|avgt|5|226619.480|± 69024.069|ns/op|
|remove|random|bucket-leaf-kdtree|1|teapot|avgt|5|188944.887|±
84743.239|ns/op|
Unless there are any objections or additional ideas, I'm going to start working
on {{PointMap}} implementations for Euclidean 2D and 3D based on this algorithm.
> Point Set/Map
> -------------
>
> Key: GEOMETRY-142
> URL: https://issues.apache.org/jira/browse/GEOMETRY-142
> Project: Apache Commons Geometry
> Issue Type: New Feature
> Reporter: Matt Juntunen
> Priority: Major
>
> It would be very useful to have set and map implementations that accepts
> points and vectors as keys and use "fuzzy" look up logic, where values are
> compared using a precision context. This would have uses in a number of
> situations, including the implementation of GEOMETRY-110.
> Options for the implementation of such classes include
> * BSP trees (as already implemented)
> * k-d trees
> * quadtrees/octrees
> * r-trees
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
