# Thread: help to improve program efficiency and speed

1. ## help to improve program efficiency and speed

Hi, how would I improve the speed of finding probability of the occurency of each variable in a 2-dimenstional array? I am now currently using 4 for loops, it worked fine for small arrays like 3x3, but big one like 400x400, the program just basically runs on forever.

for example:
Code:
```          int array={
{1,1,1},
{2,1,3},
{3,1,2}
};

probability for array=5/9;
array=2/9; and so...```
Any suggestions or tips will be appreciated! 2. I'm lost.

Explain again what you are trying to do. 3. Sorry about not making it too clear, what I mean is to find the probability of occurences in each individual element in the 2d mentional array.

So say if I have this 3x3 array:

Code:
```            int arr={
{1,1,1},
{1,1,1},
{2,3,4}
};```
I need to find the probability of arr to arr with an efficient way( not my stupid 4 for loops). I hope this makes my question somewhat clearer? 4. You could flatten the array, and sort it, so you have
Code:
`int a[] = { 1, 1, 1, 1, 1, 2, 2, 3, 3 };`
From that you can build a table of "value and count" pairs
Code:
`struct { int val; int count; }[] = { {1,5},{2,2},{3,2} };`
Though with some effort, you could probably skip the flatten and sort step. 5. ## Re: help to improve program efficiency and speed

Originally posted by godhand
Hi, how would I improve the speed of finding probability of the occurency of each variable in a 2-dimenstional array? I am now currently using 4 for loops, it worked fine for small arrays like 3x3, but big one like 400x400, the program just basically runs on forever.

Any suggestions or tips will be appreciated!
Could the "runs on forever" be because you are outputting to the screen using printf? If so, you might want to pipe the output to a file.

Posting a reasonably-sized snippet of actual compilable code that demonstrates your problem would allow for further nitpicking or suggestions -- "4 for loops" can leave a lot to the imaginiation (and it's harder to debug someone else's imagination than code). 6. Code:
```  for(outrow=0;outrow<in->rows;outrow++)
{

for(outcol=0;outcol<in->cols;outcol++)
{

temp=testarray[outrow][outcol];

for(row=0;row<in->rows;row++)
{

for(col=0;col<in->cols;col++)
{

if(temp==testarray[row][col])
{
counter++;
printf("row-col:%d %d\n",row,col);
}

}

}

printf("counter=%d\n",counter);
counter=0;

}

}```
this is the code, it is terribly inefficient for larger 2 d arrays. 7. What are the restrictions on the numbers in the array (the data). Are they all positive, all < 10, or anything like that? This will make a difference to how you can process it. 8. they are all integer numbers, positive. No range restriction. 9. The typical way to count the number of instances in an array efficiently is:

Code:
```int cInstances[MAX_VALUE+1] = { 0 };

for(loop through array) {
cInstances[array[index]]++;
}```
This means you have to only loop through the array once. However, since your MAX_VALUE is something like four billion you will have to use some sort of 'sparse' array or other data structure to hold the instance counts. You can probably do this with some sort of hash or efficient insert into a sorted linked list. I think this is like what the C++ stl map does so there should be some code around or search for "sparse arrays" source code c. 10. hi anonytmouse, your suggested way did work, however, could you explain what this means:

Code:
`      cInstances[array[index]]++;`
I have not seen this before. 11. Code:
```int cInstances[MAX_VALUE+1] = { 0 };

for(outrow=0;outrow < in->rows;outrow++) {
for(outcol=0;outcol < in->cols;outcol++) {

cInstances[ testarray[outrow][outcol] ]++;
}
}```
Well, let testarray = 54. All this does is increment the int at cInstances. If the value of the array item is 93 then the int at cInstances is incremented and so on. So then you can later print it out:
Code:
```printf("The number 54 occurred %d times.", cInstances);
printf("The number 93 occurred %d times.", cInstances);

// To print every  count...
for(i=0;i<=MAX_VALUE;i++) {
printf("The number %d occurred %d times", i, cInstances[i]);
}```
Obviously, this code will only work when MAX_VALUE is a few tens of thousands or less. You can increase this to a few hundred thousand by using malloc. 12. Use a binary search tree (or a link list) to store the frequency count. Popular pages Recent additions 