Skip to content
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

few improvements - performance, flexibility of usage #1

Open
slepic opened this issue Jun 14, 2019 · 3 comments
Open

few improvements - performance, flexibility of usage #1

slepic opened this issue Jun 14, 2019 · 3 comments
Labels
enhancement New feature or request

Comments

@slepic
Copy link

slepic commented Jun 14, 2019

Your implementation is kinda inefficient.
I have a few suggestions to improve it.
I know it might not be an issue, if one needs to calculate just a single line or maybe a few.
But if one want to calculate bulk of lines, it may become noticable.

So my suggestions are here:

  1. The public api uses angles in degrees, but all calculations are done in radians. Store the angles in radians and just provide methods to set them in degrees, converting to radians inside your setters. (provide separate setters for degrees and radians for convenience - let the users choose their prefered unit of angle.)
  2. avoid deg2rad and rad2deg functions since they are several times slower then the two operators expression they are wrapping
    $ time php -r 'for ($i=0; $i<100000000; ++$i) deg2rad(45);'
    real 0m1,302s
    user 0m1,302s
    sys 0m0,000s
    $ time php -r 'for ($i=0; $i<100000000; ++$i) (45*M_PI/180.0);'
    real 0m0,384s
    user 0m0,372s
    sys 0m0,012s
  3. make the objects immutable - get rid of setters (i know, i mentioned adding setters for degrees and radians and now i suggest removing them alltogether, but these are just suggestions...) - i pretty much doubt anyone is going to use those setters, you want to create a point then use it to solve geodesic problem, you are unlikely to want to change that point, and if you do you should just creat eanother one anyway... to cope with the degrees/radians flexibility, provide factory methods - one accepting radians, one accepting degrees.
  4. Your classes are implementing unrelated code that it only should depend on - by this i mean the protected methods - generaly the API is quite bad, youd better off with a service that implements methods solving the geodesic problems. Think of a real-life analogy: Have you ever seen a point tell you distance to another point (This is what your classes do)? No. Usualy you take a ruler and meassure the distance. The ruler here is the analogy of the service I'm suggesting.

for example it'd be much more flexible to use

$endPoint = $geoService->getEndPoint(new Point($latitude, $longitude),  $bearing, $distance);
...
$result = $geoService->getGeodesic($point1, $point2); //calculation is done inside, reducing the number of sines and cosines needed to calculate distance and initial bearing separately.
$result->getDistance(); //just getter, no calculation
$result->getBearing(); //just getter, no calculation

then point only implement methods I would expect from a point:
Point::getLattitude()
Point::getLogitude()
and line (might need renaming)
Line::getDistance()
Line::getBearing()
...plus constructors ofc...
I dont know how about you but i would not expect a point to tell me anything more than this. Putting those methods on the Point a Line classes couples them together with this specific algorithms, although a point is just a point. And you can run dozens of different algorithms over point structures and none of them will need these specific methods....

@knifefencer
Copy link
Contributor

Good suggestion. Probably, there will be some more things for optimization. If necessary, do pull request, please.

@slepic
Copy link
Author

slepic commented Jun 15, 2019

Well I have created a brief implementation here: https://github.com/slepic/geo-problems
But it is actualy a very different thing, like a 2.0 or so... totaly incompatible with yours...

The point structure works on radians and converting from degrees is rather responsibility of the consumer of the library, although I have added static named constructors on the class as well for convenience. But I'd prefer not to have any static methods anyway...

Unlike you, I didnt take care of converting data types like int or string to float, that is also responsibility of the consumer of the library.

There is a simple unit test that runs over random data. It first runs the direct problem then the inverse problem on the output of the direct problem, and check if it was able to get back where it started from.
If you run this test several times you will eventualy hit misexpectations, I think it is because of some edge cases. Like going from South pole will alway mean you have to go north no matter where you wanna go and so forth...

I have also replaced the Earth radius constant wth a private variable of the solver class, making it possible to work on other geo structures as well.

EDIT:
Oh and also I have ommited the final bearing since it is really just turning 180° around.
And I have omitted the midpoint since it is just the same as trying to get end point within half the distance, which is more flexible because that way you can get thirds, fourths, any fraction you want...

I have also added an experimental formatter for the positions, so it gets more convenint to display those coordinates in whatever format you want instead of just radians.

EDIT2:
Added a simple benchmark to compare our implementations:

$ php bench/bench.php 
Direct problem:
Comparing TeamA vs. Slepic implementation with 1000000 random samples.
TeamA: 2.0863010883331
Slepic: 1.2146902084351
Slepic / TeamA: 58.22%
Slepic is 41.78% faster then TeamA
TeamA / Slepic: 171.76%
TeamA is 71.76% slower then Slepic

Inverse problem:
Comparing TeamA vs. Slepic implementation with 1000000 random samples.
TeamA: 1.506157875061
Slepic: 1.2453169822693
Slepic / TeamA: 82.68%
Slepic is 17.32% faster then TeamA
TeamA / Slepic: 120.95%
TeamA is 20.95% slower then Slepic

@knifefencer
Copy link
Contributor

Great! Thank you for your feedback, we will take note in future releases.

@knifefencer knifefencer added the enhancement New feature or request label Jun 17, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants