Thread: help to improve program efficiency and speed

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    31

    Question 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[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...
    Any suggestions or tips will be appreciated!
    'The bigger they are, the harder they fall' ~Yang

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,608
    I'm lost.

    Explain again what you are trying to do.

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    31
    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[3][3]={
               {1,1,1},
               {1,1,1},
               {2,3,4}
                };
    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?
    'The bigger they are, the harder they fall' ~Yang

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,058
    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.
    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.

  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005

    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).
    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.*

  6. #6
    Registered User
    Join Date
    Jun 2003
    Posts
    31
    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.
    'The bigger they are, the harder they fall' ~Yang

  7. #7
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    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]

  8. #8
    Registered User
    Join Date
    Jun 2003
    Posts
    31
    they are all integer numbers, positive. No range restriction.
    'The bigger they are, the harder they fall' ~Yang

  9. #9
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    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. #10
    Registered User
    Join Date
    Jun 2003
    Posts
    31
    hi anonytmouse, your suggested way did work, however, could you explain what this means:

    Code:
          cInstances[array[index]]++;
    I have not seen this before.
    'The bigger they are, the harder they fall' ~Yang

  11. #11
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    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[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:
    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]);
    }
    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. #12
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    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]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Future Contests: Speed Coding
    By Eibro in forum Contests Board
    Replies: 58
    Last Post: 03-09-2003, 08:31 AM
  2. Results - 4th contest, saturday, august 11
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 08-12-2002, 09:41 AM
  3. Results for *easy* contest:
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 07-27-2002, 11:35 AM
  4. Results for the Encryption Contest -- June 23, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 07-07-2002, 08:04 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM