# Sorting numbers into bins

I have two 2D arrays of doubles a and b. Both have two rows and different numbers of columns.

a [[ 1,2,3][4,5,6]]


The list b represents a number of bins of numbers and the list is a list of numbers I'm trying to sort into these bins.

I need to go through each of the numbers in b to look for its corresponding bin. Here's the code I have, which works perfectly but I need to optimize it. Any ideas?

        int k = 0;
for (int i = 0; i < a.GetLength(1); i++) {
for (int j = 0; j < b.GetLength(1); j++) {

//if fragment falls in bin, add it to the new object
if (a[0, i] <= (b[0, j] + binSize / 2) &&
a[0, i] > (b[0, j] - binSize / 2)) {

c[0, k] = a[0, i];
c[0, k] = b[0, j];

c[1, k] = a[1, i];
c[1, k] = b[1, j];
k++;

}
if (k >= a.GetLength(1)) {
break;
}
}
}

-
You should add how is binSize is declared, it would help us to understand your code. – TopinFrassi Aug 19 '14 at 12:06
What is the purpose of c[0, k] = a[0, i]; followed by c[0, k] = b[0, j];? Are you sure the code is working correctly? – Emanuele Paolini Aug 19 '14 at 12:38
One optimization I would do is create a variable for binSize / 2 outside your loops and place that new variable in your if statement. That way that calculation isn't made 2*O(n^2) times. I would also do the same for your a.GetLength(1) and b.GetLength(1) for the same reason. – M K Aug 19 '14 at 13:21
This question would have substantially better answers if you provided more context on what sorts of values the binSizes can be, whether values can 'fall between' different bins, and whether binSizes are at regular intervals – rolfl Aug 19 '14 at 14:47

## 1 Answer

Here's the code I have, which works perfectly

int k = 0;
for (int i = 0; i < a.GetLength(1); i++) {
for (int j = 0; j < b.GetLength(1); j++) {

//if fragment falls in bin, add it to the new object
if (a[0, i] <= (b[0, j] + binSize / 2) &&
a[0, i] > (b[0, j] - binSize / 2)) {

c[0, k] = a[0, i];
c[0, k] = b[0, j];

c[1, k] = a[1, i];
c[1, k] = b[1, j];
k++;

}
if (k >= a.GetLength(1)) {
break;
}
}
}


It is obviously better to extract the binSize / 2 outside of the for loops, as binSize is never changed. So the repeating binSize / 2 isn't needed. Assuming binSize is an int:

int halfBinSize = binSize / 2;


Also a.GetLength(1) and b.GetLength(1) won't change, but are queried each time in the inner loop so refactor like this:

int lengthA = a.GetLength(1);
int lengthB = b.GetLength(1);


As you overwrite the values of

            c[0, k] = a[0, i];
c[0, k] = b[0, j];

c[1, k] = a[1, i];
c[1, k] = b[1, j];


this can be reduced to

c[0, k] = b[0, j];
c[1, k] = b[1, j];


As the context isn't known let's keep the check for k >= a.GetLength(1)

the check for k >= a.GetLength(1) can be removed as you are using the a[,] only to compare with b[,] the check can be removed completely

but we place it to the looping condition

for (int j = 0; k >= lengthA && j < lengthB; j++)


and we should refactor a[0,i] to outside the inner loop

double currentA = a[0,i];


which results overall in

int halfBinSize = binSize / 2;
int lengthA = a.GetLength(1);
int lengthB = b.GetLength(1);
double currentA;

int k = 0;
for (int i = 0; i < lengthA; i++)
{

currentA = a[0,i];

for (int j = 0; k >= lengthA && j < lengthB; j++)
{
//if fragment falls in bin, add it to the new object
if (currentA  <= (b[0, j] + halfBinSize) &&
currentA  > (b[0, j] - halfBinSize))
{

c[0, k] = b[0, j];

c[1, k] = b[1, j];
k++;

}
}
}

-