Thread: Any faster intersection method?

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    163

    Any faster intersection method?

    I'm trying to intersect ArrayA and ArrayB values and put them into ArrayC. Is there any faster method than this?
    Code:
     
     while (i<ArrayA_size && j<ArrayB_size) {
        if (ArrayA[i] == ArrayB[j]) {
          ArrayC[index++] = ArrayA[i];
          i++;
          j++;
        }
        else if (ArrayA[i] < ArrayB[j]) {    
    	i++;
        }
        else
          j++;
      }
    Thanks for your help!

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Is there any faster method than this?
    Trusting that both your sets are sorted, O(M + N) is about the best you're going to get for a straight intersection, and that's what you've got right now. Why, are you having performance issues? Or is this some misguided attempt at premature eja^H^H^Hoptimization?
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    yea, i'm having optimization issues. my program spent about 40% of the total running time on this function, so i'm thinking on how to improve it

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    this may or may not help much -- removed array indexing
    Code:
    while (i<ArrayA_size && j<ArrayB_size) {
        int a = ArrayA[i];
        int b = ArrayB[j];
        if (a == b) {
          ArrayC[index++] = a;
          i++;
          j++;
        }
        else if (a < b) {    
    	i++;
        }
        else
          j++;
      }

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Okay, then if this isn't homework, let's try set_intersection and see if it does any better. The standard library is more likely to have a highly tuned algorithm than your handrolled version.
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    does array indexing slows down access? I will try it out. Thanks guys for your suggestions.
    This is my job. Now I need to optimize my program, which is even harder than to make the program work. There is 2 ways I'm tackling it now. First is to improve the algorithm and coding details. Second is to implement memory management into the program.
    Any comments on it?

  7. #7
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    for the set_intersection, it puts the result in the iterator result. I declare an array and put this array address in the iterator result, but how do I know how many elements are there in the result?
    right now, after finish intersecting, i use a while loop to read the array to count the number of elements in the result

    After hours of trying, I find a solution, hee.....

    Code:
    inline int Transactiondb::CreateSubg(int *set, int setcount, int *set_sub, structtid *r) {
    int i=0, j=0, index=0, *add;
    
    add = set_intersection(set, set+setcount, r->tidptr, r->tidptr+(r->transnum), set_sub);
    
    index = (add - set_sub)-1 / sizeof(int); // since add is the last pointer in set_sub
      
      return index;
    }
    Last edited by franziss; 10-25-2005 at 12:14 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. on method pointers and inheritance
    By BrownB in forum C++ Programming
    Replies: 2
    Last Post: 03-02-2009, 07:50 PM
  2. Overriding a method in C
    By DavidDobson in forum C Programming
    Replies: 1
    Last Post: 07-05-2008, 07:51 AM
  3. Replies: 2
    Last Post: 01-22-2008, 04:22 PM
  4. Merge and Heap..which is really faster
    By silicon in forum C++ Programming
    Replies: 2
    Last Post: 05-10-2005, 04:06 PM
  5. Faster method than GetFrontBuffer()
    By extent in forum Game Programming
    Replies: 2
    Last Post: 05-04-2005, 10:36 AM