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:
Any suggestions or tips will be appreciated!Code:int array[3][3]={ {1,1,1}, {2,1,3}, {3,1,2} }; probability for array[0][0]=5/9; array[1][0]=2/9; and so...
'The bigger they are, the harder they fall' ~Yang
I'm lost.
Explain again what you are trying to do.
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:
I need to find the probability of arr[0][0] to arr[2][2] with an efficient way( not my stupid 4 for loops). I hope this makes my question somewhat clearer?Code:int arr[3][3]={ {1,1,1}, {1,1,1}, {2,3,4} };
'The bigger they are, the harder they fall' ~Yang
You could flatten the array, and sort it, so you have
From that you can build a table of "value and count" pairsCode:int a[] = { 1, 1, 1, 1, 1, 2, 2, 3, 3 };
Though with some effort, you could probably skip the flatten and sort step.Code:struct { int val; int count; }[] = { {1,5},{2,2},{3,2} };
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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.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!
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).
7. It is easier to write an incorrect program than understand a correct one.
40. There are two ways to write error-free programs; only the third one works.*
this is the code, it is terribly inefficient for larger 2 d arrays.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; } }
'The bigger they are, the harder they fall' ~Yang
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.
When all else fails, read the instructions.
If you're posting code, use code tags: [code] /* insert code here */ [/code]
they are all integer numbers, positive. No range restriction.
'The bigger they are, the harder they fall' ~Yang
The typical way to count the number of instances in an array efficiently is:
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.Code:int cInstances[MAX_VALUE+1] = { 0 }; for(loop through array) { cInstances[array[index]]++; }
hi anonytmouse, your suggested way did work, however, could you explain what this means:
I have not seen this before.Code:cInstances[array[index]]++;
'The bigger they are, the harder they fall' ~Yang
Well, let testarray[0][0] = 54. All this does is increment the int at cInstances[54]. If the value of the array item is 93 then the int at cInstances[93] is incremented and so on. So then you can later print it out: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] ]++; } }
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.Code:printf("The number 54 occurred %d times.", cInstances[54]); printf("The number 93 occurred %d times.", cInstances[93]); // To print every count... for(i=0;i<=MAX_VALUE;i++) { printf("The number %d occurred %d times", i, cInstances[i]); }
Use a binary search tree (or a link list) to store the frequency count.
When all else fails, read the instructions.
If you're posting code, use code tags: [code] /* insert code here */ [/code]
