Find the difference between two 1d arrays to form a 2d array of those differences in the shortest time

Question

I am trying to find the absolute difference between every element of one array and every element of another to form a matrix.

I have achieved this using for loops but it is slow and I need it to be faster. I can do it faster in R for example by using the dist method but I am struggling to make it fast in C#.

double[] array1 = new double [] { 1.1, 2.0, 3.0, 4.0, 5.0 };
double[] array2 = new double[] { 6.1, 7.0, 8.0};    
double[,] final_array = new double[5, 3];
for (int i = 0; i < 5; i++)
{
    for (j = 0; j < 3; j++)
    {
        final_array[i,j] = Math.Abs(array1[i] - array2[j])
    }
}

# expected result of final_array
5    4.1    3.1     2.1     1.1
5.9  5      4       3       2
6.9  6      5       4       3

Although this result is the correct answer I want to do this faster as I will need to do this calculation for arrays of up to 15,000 in size.

Multi-dimensional arrays in .NET tend to be slow. Do you require the result to be in a multi-dimensional array (as opposed to a jagged array - an array of arrays) — Damien_The_Unbeliever, Jan 16 '19 at 13:44
This is an [embarrassingly parallel](https://en.wikipedia.org/wiki/Embarrassingly_parallel) problem, so writing a parallel solution shouldn't be too hard. — Matthew Watson, Jan 16 '19 at 13:52
Yeldar Kurmangaliyev. I was confused that R can achieve the result so much faster. It takes approx. 5 seconds using R dist method compared with 30 seconds in C#. — Daniel Wyatt, Jan 16 '19 at 13:57
You can use a combination of `Numerics.Vector` and TPL to make use of all cores and their SIMD instructions. That should speed up your calculation considerably. — Sefe, Jan 16 '19 at 14:02

Sefe · Accepted Answer · 2019-01-16T21:17:39.570

You can use vectors in the System.Numerics namespace. The caveat is that it will only work with float, not with double. That shouldn't be a problem for subtraction though:

float[] array1 = new float[] { 1.1F, 2.0F, 3.0F, 4.0F, 5.0F };
float[] array2 = new float[] { 6.1F, 7.0F, 8.0F };    
float[,] final_array = new float[array1.Length, array2.Length];

int vectorCount = array2.Length / 4;
Vector4[] array2Vectors = new Vector4[vectorCount];
Parallel.For(0, vectorCount, i =>
{
    int offset = i * 4;
    array2Vectors[i] = new Vector4(array2[offset], array2[offset + 1],
        array2[offset + 2], array2[offset + 3]);
});

Parallel.For(0, array1.Length, i =>
{
    Vector4 v1 = new Vector4(array1[i], array1[i], array1[i], array1[i]);
    for (int j = 0; j < array2Vectors.Length; j++)
    {
        Vector4 result = Vector4.Abs(Vector4.Subtract(v1, array2Vectors[j]));
        int offset = j * 4;
        final_array[i, offset] = result.X;
        final_array[i, offset + 1] = result.Y;
        final_array[i, offset + 2] = result.Z;
        final_array[i, offset + 3] = result.W;
    }

    for (int j = vectorCount * 4; j < array2.Length; j++)
    {
        final_array[i,j] = Math.Abs(array1[i] - array2[j]);
    }
});

Since you are using vectors now, you will make use of the CPU's SIMD instructions, which should speed up your task.

Additional performance gains come from parallel execution with Parallel.For, which makes use of all available CPU cores.

You can try it out here.

@DanielWyatt: I'd be intersted to know how much it did speed up your code. — Sefe, Jan 17 '19 at 14:06
So I need to use doubles and so I have just copied my code into the Parallel.For loop. The time taken for arrays of 10000 went from 65 seconds down to 15 seconds. — Daniel Wyatt, Jan 17 '19 at 16:28
@DanielWyatt: Do you really need a `double` range and/or precision? If not, you can cast first to single and back to double after the operation. — Sefe, Jan 17 '19 at 21:00
Unfortunately I think I do if I want 100% accuracy in my matrix. I could sacrifice a bit of accuracy for speed though which may be a worthwhile trade-off. — Daniel Wyatt, Jan 21 '19 at 09:21

Yeldar Kurmangaliyev · Answer 2 · 2019-01-16T14:09:21.017

There is no way to do this faster in terms of algorithmic complexity. It requires exactly O(n * m) operations to calculate this result, at least because you have the resulting array of that size.

There are some ways to slightly improve the performance of the code itself.
The easiest one is to switch to jagged arrays, as already suggested in the comments:

double[] array1 = new double [] { 1.1, 2.0, 3.0, 4.0, 5.0 };
double[] array2 = new double[] { 6.1, 7.0, 8.0};    
double[][] final_array = new double[5][];

for (int i = 0; i < 5; i++)
{
    final_array[i] = new double[3];
    for (int j = 0; j < 3; j++)
    {
        final_array[i][j] = Math.Abs(array1[i] - array2[j]);
    }
}

You can read more about multidimensional array vs jagged arrays and their performance here:
What are the differences between a multidimensional array and an array of arrays in C#?

You could also go further and increase performance by using unsafe pointers to access multidimensional array or by utilizing advanced processor instructions (intrinsics), but... the question is: is this really something you need to think of? Is it an only bottle neck in an extremely high-load system? If it is not, then just leave your code as it is, in a clearly readable and understandable form. Saying about performance, O(n * m) asymptotic complexity is perfectly fine for arrays of size 15000.

Find the difference between two 1d arrays to form a 2d array of those differences in the shortest time

2 Answers2