how to speed up calculation of average distance between a huge amount of points?

The interconnectPoints component in Kangaroo creates lines between each pair of points within a group of points.

It gets really slow when the number of points increases and almost all the memories are consumed during the calculation.

E.g. in the example attached, the calculation for 2000+ points took only a few seconds. But the calculation for 8000+ points takes like forever... although I understand that there are 34 millions lines to create in this case....

May I ask how to speed up the calculation of average distance between a group of points?

Thanks!

Attachments:

avg dist issue.gh, 54 KB

Replies to This Discussion

Permalink Reply by Grasshope on November 5, 2016 at 9:44am

So far, Kangaroo's interconnectPoints is still the fastest component to calculate average distance between points:

Does this mean the the GH component written in C++ or C# and compiled is significantly more efficient than GhPython component for heavy duty calculation task?

Appreciate your kind advice!

Attachments:

avg dist issue 2.gh, 62 KB

Permalink Reply by David Rutten on November 5, 2016 at 9:53am

If you must have an exact answer then you probably can't make it faster. You're going to have to actually calculate all the distances, which is an O(N^2) operation. You can however reduce memory to O(1) by computing a rolling average, but I don't think there's any component out there that does that.

The question is what exactly do you need this value for and will you settle for an approximation?

Permalink Reply by Grasshope on November 5, 2016 at 10:16am

Thank you very much, David!

Yes, I think I need to step back and think about if this kind of calculation is necessary.

Interesting to know about the Big O Notation as you mentioned. Found the following information:

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Permalink Reply by David Rutten on November 5, 2016 at 11:22am

Big O notation tells you how quickly an algorithm slows down as you increase the input size. For example computing the length of a curve is O(N). If you have twice as many curves, it'll take twice as long to compute all the lengths. O(N^2) means that if you double the side of the input, it'll take four times as long. O(1) means that no matter the size of the input, it'll always take the same amount of time.

Note that big-O notation doesn't tell you how fast an algorithm is, it only tells you how well it scales.

RSS