I need to calculate distances between every pair of points in an array and only want to do that once per pair. Is what I've come up with efficient enough or is there a better way? Here's an example, along with a visual to explain what I'm trying to obtain:

e.g., first get segments A-B, A-C, A-D; then B-C, B-D; and finally, C-D. In other words, we want A-B in our new array, but not B-A since it would be a duplication.

```
var pointsArray = new Point[4];
pointsArray[0] = new Point(0, 0);
pointsArray[1] = new Point(10, 0);
pointsArray[2] = new Point(10, 10);
pointsArray[3] = new Point(0, 10);
// using (n * (n-1)) / 2 to determine array size
int distArraySize = (pointsArray.Length*(pointsArray.Length - 1))/2;
var distanceArray = new double[distArraySize];
int distanceArrayIndex = 0;
// Loop through points and get distances, never using same point pair twice
for (int currentPointIndex = 0; currentPointIndex < pointsArray.Length - 1; currentPointIndex++)
{
for (int otherPointIndex = currentPointIndex + 1;
otherPointIndex < pointsArray.Length;
otherPointIndex++)
{
double xDistance = pointsArray[otherPointIndex].X - pointsArray[currentPointIndex].X;
double yDistance = pointsArray[otherPointIndex].Y - pointsArray[currentPointIndex].Y;
double distance = Math.Sqrt(Math.Pow(xDistance, 2) + Math.Pow(yDistance, 2));
// Add distance to distanceArray
distanceArray[distanceArrayIndex] = distance;
distanceArrayIndex++;
}
}
```

Since this will be used with many thousands of points, I'm thinking a precisely dimensioned array would be more efficient than using any sort of IEnumerable.

If you have n points, the set of all pairs of points contains n * (n-1) / 2 elements. That's the number of operations you are doing. The only change I would do is using Parallel.ForEach() to do the operations in parallel.

Something like this (needs debugging)

```
int distArraySize = (pointsArray.Length * (pointsArray.Length - 1)) / 2;
var distanceArray = new double[distArraySize];
int numPoints = pointsArray.Length;
Parallel.ForEach<int>(Enumerable.Range(0, numPoints - 2),
currentPointIndex =>
{
Parallel.ForEach<int>(Enumerable.Range(currentPointIndex + 1, numPoints - 2),
otherPointIndex =>
{
double xDistance = pointsArray[otherPointIndex].X - pointsArray[currentPointIndex].X;
double yDistance = pointsArray[otherPointIndex].Y - pointsArray[currentPointIndex].Y;
double distance = Math.Sqrt(xDistance * xDistance + yDistance * yDistance);
int distanceArrayIndex = currentPointIndex * numPoints - (currentPointIndex * (currentPointIndex + 1) / 2) + otherPointIndex - 1;
distanceArray[distanceArrayIndex] = distance;
});
});
```

I've had to perform operations like this in the past, and I think your immediate reaction to high number crunch operations is "there must be a faster or more efficient way to do this". The only other even remotely workable solution I can think of would be to hash the pair and place this hash in a HashSet, then check the HashSet before doing the distance calculation. However, this will likely ultimately work out worse for performance.

You're solution is good. As j0aqu1n points out, you're probably going to have to crunch the numbers one way or another, and in this case you aren't ever performing the same calculation twice.

It will be interesting to see if there are any other solutions to this.

Looks good to me, but don't you have a bug?

Each of the inner iterations will overwrite the previous one almost completely, except for its first position. Won't it?

That is, in `distanceArray[otherPointIndex]`

otherPointIndex gets values from `currentPointIndex + 1`

to `pointsArray.Length - 1`

.

In your example, this will range on [0-3] instead of [0-6].

I think, it's a bit faster to use `xDistance*xDistance`

instead of `Math.Pow(xDistance, 2)`

. Apart from this, if you really always need to calculate all distances, there is not much room for improvement. If, OTOH, you sometimes don't need to calculate all, you could calculate the distances lazily when needed.

Similar Questions

I was wondering what would be the most efficient way to make a map in 2D for a java game? I know this does depend on the way the game will be seen and made so I have included info about this. View: Fr

What is the most memory efficient way to remove duplicate lines in a large text file using C++? Let me clarify, I'm not asking for code, just the best method. The duplicate lines are not guaranteed to

Given an UIImage and a CGRect, what is the most efficient way (in memory and time) to draw the part of the image corresponding to the CGRect (without scaling)? For reference, this is how I currently d

Say you have a 2D grid of tiles (This is for a 2D tile based game), most tiles occupy 1 spot, however some larger objects can fill in multiple spots. I use an indexer on my array to automatically r

In C++/CLI, What's the most efficient way to convert an array of strings to native char**? I am doing this: array<String^>^ tokenArray = gcnew array<String^> {TokenONE, TokenTWO}; int

In C++, I use a singleton class and refer to the only instance in another class. I'm wondering what is the most efficient way to access this instance since it is a large data structure. I considered t

So my title might not be the most descriptive but essentially I am doing this in one class: Launching a perl script that creates a series of files In another function within the same class, I would l

Let's say I have an array of quantity ranges: [{min=1, max=500}, {min=2, max=1000}, ...] What is the most efficient way to validate that the ranges do not overlap (the above would fail validation)?

I need to randomly 'sort' a list of integers (0-1999) in the most efficient way possible. Any ideas? Currently, I am doing something like this: bool[] bIndexSet = new bool[iItemCount]; for (int iCurIn

I am sending gps coordinates from a windows mobile phone to a webserver using a basic program I wrote in C#. The problem is the data plan on the phone only allows 4 MB per month. I was planning on upd

I have a list of X items. I want the first 10 to be randomized. Then, the 2nd 10 items to be randomized. Then the 3rd. What's the most efficient way to do this?

I've got a lot of objects with according ranges: Object1 => 0 - 23 Object2 => 24 - 84 Object3 => 85 - 103 ... Those ranges vary, now I'm looking for the most efficient way in Objective-C to

What is the most efficient way from the time consumed to read a text file into a list of binary strings in erlang ? The obvious solution -module(test). -export([run/1]). open_file(FileName, Mode) ->

I've something like this Object[] myObjects = ...(initialized in some way)... int[] elemToRemove = new int[]{3,4,6,8,...} What's the most efficient way of removing the elements of index position 3,4,

Given an array of non-negative integers, what is the fastest and most efficient way to find the maximum no. that can be obtained by performing bitwise and (i.e, & operator) on 2 DISTINCT elements

I'm looking for the fastest, most efficient way to debug my java application for BlackBerry. I noticed that it takes forever just to attach the debugger to the device, using a Torch 9800 in my case. D

I'm new to Javascript and wrote the code below to determine if a string is a palindrome. I'm curious as to what is the most efficient way to accomplish the same task. var isPalindrome = function (stri

Using the Twitter API, what would be the most efficient way to find which users favorited a specific tweet? And also it possible to do this in retrospective, or must the streams be tapped prior the fa

So I have an inner loop situation with a buffer of floating point and integer values that are to be copied over to a another buffer in string format. What are my alternatives to round and insert a tho

This question already has an answer here: Variable appears to change size on every loop iteration - what? 3 answers I have a program trying to read in around 30 .jpg images (will be able to go

What would be the most efficient way to SELECT this, then DELETE it immediately. SELECT * from `usersOnline` WHERE timestamp>NOW()-INTERVAL 5 SECOND ORDER BY rand() LIMIT 1; How could I take this

Given any character from a to z, what is the most efficient way to get the next letter in the alphabet using PHP?

What is the most efficient and fastest way to compare elements in a vector of class using two iterators? The vector is not a sortable one and I have an overloaded > operator for the class. I use

What is the most efficient way to iterate through all DOM elements in Java? Something like this but for every single DOM elements on current org.w3c.dom.Document? for(Node childNode = node.getFirstChi

I have a Java program using JNI which is designed to load and display images in a custom file format, read through a c++ library. The data is loaded into an array of byte data on the c++ side, and tra

Let v1 be the target vector, v2 needs to be appended to the back of it. I'm now doing: v1.reserve(v1.size() + v2.size()); copy(v2.begin(), v2.end(), back_inserter(v1)); Is this the most efficient way

What is the most memory efficient way to loop through an NSMutableArray of custom objects? I need to check a value in each object in the array and return how many of that type of object is in the arra

Looking for most efficient way to write this INSERT query (and least code): INSERT INTO [exportnote] ( [versionnumber], [createdate], [LabAccessioningNumber], [Text], [exporttestresultreportid] ) SELE

What's the most efficient way to remove the text 2010-04-07 14:25:50,773 DEBUG This is a debug log statement - from a log file like the extract below using Vim? 2010-04-07 14:25:50,772 DEBUG This is

I am finishing a Cocoa App which will use CocoaFob for licensing and I am wondering about the most efficient and secure way to implement a trial period in cocoa. Thanks in advance for your help, Reg

message = hello %s , how are you %s, welcome %s%(john,john,john) What is the most pythonic way to avoid specifying john 3 times and instead to specify one phrase.

If I have a string: std::string Pooptacular = Pooptacular and I want to convert it to a char array, I have some options one being: char* poopCArr = Pooptacular.c_str(); or I can do something with

I have an unsorted list, from which I want to remove duplicates. What is the most efficient to perform this in C. In my case, the list is a linked list of arrays. In other words several arrays linked

I'd like to ask what is the most efficient (and fastest) way to search for data between 2 dates? Let's consider having following simple query: SELECT Date_,counter1,counter2,... WHERE (date range cond

Given two inclusive integer ranges [x1:x2] and [y1:y2], where x1 <= x2 and y1 <= y2, what is the most efficient way to test whether there is any overlap of the two ranges? A simple implementatio

Basic Question: I have a k dimensional box. I have a vector of upper bounds and lower bounds. What is the most efficient way to enumerate the coordinates of the vertices? Background: As an example, sa

Reader's digest version: What is the most efficient way of requesting an image from a server and placing it into the DOM using AJAX (or AJAI, perhaps? : ) )? Here's the long version: Hello SO, I'm set

What's the best and most efficient book to learn JavaScript?

This question already has an answer here: Given an array of numbers, find out if 3 of them add up to 0 5 answers Let's say my list is l = [1,2,3,4,5], and x = 8. I'm thinking that I should ite

I'm trying to figure out what is the most efficient way to parse data from a file using Lua. For example lets say I have a file (example.txt) with something like this in it: 0, Data 74, Instance 42949

This question already has an answer here: Create List of Single Item Repeated n Times in Python 5 answers What is the most efficient way to create list of the same number with n elements?

What is the most portable way to delete element from multidimensional sparse array in javascript? Will following work well if rows can be undefined sometimes? if( content[row] ) { delete content[row][

Given an NSMutableArray of dynamic CGPoints, what is the fastest and most efficient way to draw lines from array[0] to array[1], array[1] to array[2], etc.? Should I rewrite my function in C or C++ fo

I have a string that contains some values I need to extract. Each of these values is surrounded by a common character. What is the most efficient way to extract all of these values into an array? For

I'm looking for the most efficent way (i.e. the lesser keys pressed) to indexing the last element of an array. Then something like a <- c(1,2,3) n <- length(a) b <- a[n] should not be used,

I run a website that needs to routinely loop through a bunch of PNGs with transparency's and merge them together. Sometimes this can be a LONG process so I was wondering what is the most efficient way

I'm trying to figure out the most efficient way to send multiple queries to a MySQL database with PHP. Right now I'm doing two separate queries but I know there are more efficient methods, like using

What is the most efficient way given to raise an integer to the power of another integer in C? // 2^3 pow(2,3) == 8 // 5^5 pow(5,5) == 3125

Is there a known 'most efficient' version of the A* search algorithm? I know some people write papers on the most efficient way to compute common operations, has this been done for A*? specifically th

Say my url is www.example.com/usa/california/redding/ What is the most efficient way to return the following: $urls = array ( 0 => '/usa/', 1 => '/usa/california/', 2 => '/usa/california/redd