# Any faster intersection method?

• 10-24-2005
franziss
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!
• 10-24-2005
Prelude
>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?
• 10-24-2005
franziss
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
• 10-24-2005
Ancient Dragon
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++;   }```
• 10-24-2005
Prelude
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.
• 10-24-2005
franziss
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?
• 10-24-2005
franziss
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; }```