Comments (3)
rsned
commented on May 26, 2024
One thing that might assist in me debugging it is to get a sense of the
number of edges those thousands of cities ends up being. Can you print
out index.NumEdges()? Is it in the 10's of thousands, millions, tens of
millions?
Is your slow time just the time on the Query, or does it include the
building of the ShapeIndex?
…On Fri, Feb 7, 2020 at 1:33 PM Stepan ***@***.***> wrote:
Hello @rsned <https://github.com/rsned>
I use your golang package for finding the nearest polygon from geo point &
i try to make it following this:
index := s2.NewShapeIndex()
// More than 4000 polygons of cities added to index// ...
q := s2.NewClosestEdgeQuery(index, s2.NewClosestEdgeQueryOptions().MaxResults(1).IncludeInteriors(true))target := s2.NewMinDistanceToPointTarget(s2.PointFromLatLng(s2.LatLngFromDegrees(40.853544, -73.099544)))res := q.FindEdges(target)
I've got a problem, the method's implementation time is about 30 sec which
is quite slow.
Maybe i did smth wrong or it is an expected result?
if I exactly did smth wrong, could you please tell me how to realize it in
a right way?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#59?email_source=notifications&email_token=ACBHGBAAH5RVTRX3CRNFUVTRBXHRNA5CNFSM4KRVHQH2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IL5VC3Q>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACBHGBFWRINZLGFR77TQZOTRBXHRNANCNFSM4KRVHQHQ>
.
from geo.
pshopper
commented on May 26, 2024
Slow time is just the time on the Query. NumEdges is 429636.
from geo.
rsned
commented on May 26, 2024
OK, I tried it on a 5 million edge polygon, and the query took ~200 seconds to complete.
My guess is that the reason it's really slow with the large edge count is because so far, only the Brute Force implementation is done on it. See: https://github.com/golang/geo/blob/master/s2/edge_query.go#L466
It was the simplest of the code to port to get the code running
If you look at the original C++, the switch over point from brute force to optimized is set at ~100 edges.
https://github.com/google/s2geometry/blob/master/src/s2/s2closest_edge_query.cc#L46
Running the C++ benchmarks, optimized gains dramatically the larger the data inputs.
Benchmark Time(ns) Optimized Brute Opt gain
-------------------------------------------------------------
BM_FindClosest<Fractal>/12 286 276 ~1x
BM_FindClosest<Fractal>/48 899 894 ~1x
BM_FindClosest<Fractal>/192 2077 3268 ~1.5x
BM_FindClosest<Fractal>/768 3679 12611 ~4x
BM_FindClosest<Fractal>/3k 6064 49593 ~8x
BM_FindClosest<Fractal>/12k 9068 195660 ~20x
BM_FindClosest<Fractal>/48k 12929 830409 ~60x
BM_FindClosest<Fractal>/192k 17310 3302094 ~190x
BM_FindClosest<Fractal>/768k 23289 13361211 ~575x
BM_FindClosest<Fractal>/3M 33153 58392773 ~1750x
So, while probably not quite as dramatic as the C++, the Go optimized implementation which should provide considerable savings once it's completed. I don't have a specific ETA on when it will be completed, but I am still working through the porting to get it completed.
from geo.
Related Issues (20)
- Calculate S2 of polygon with OOM Error in golang
- AllNeighbors has a bug
- PolygonBuilder HOT 2
- Invalid input loops to PolygonFromOrientedLoops HOT 2
- Having trouble with RegionCoverer
- Loop.Area() unit HOT 1
- Find Closest Edge Performance with Many Polylines
- Porting bug
- Bug on Polygon Contains (linked to https://github.com/golang/geo/issues/77 ?) HOT 1
- High memory usage in getting s2 cell covering HOT 3
- Polygon.Intersects() method not working for some inputs? HOT 1
- golang-s2 momory leak HOT 1
- Q: How do you calculate the distance in km between 2 lat/lng points? HOT 7
- ppc64le - TestPredicatesRobustSignEqualities failure due to floating point precision differences HOT 1
- ppc64le - TestPointMeasuresPointArea failure due to floating point precision differences
- ppc64le - TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance failure due to floating point precision differences HOT 1
- Inverted params HOT 1
- Get a random point from a shape HOT 2
- Subdivide polygon
- Memory Leak when a loop contains point multiple time HOT 2
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 geo.