Declarative Query Processing in Relational Database Systems - Automated Physical Database Design and Tuning - page 5

int countMatches1 ( int [] R, int [] S) {
int c=0;
foreach ( int r in R)
foreach ( int s in S)
if (r == s) c++;
return c;

}

int countMatches2 ( int [] R, int [] S) {
Dictionary < int, int >ht= new Dictionary < int,int >();
foreach ( int r in R)
if (ht.ContainsKey(r)) ht[r]++;
else ht.Add(r, 1);
int c=0;
foreach ( int s in S)
if (ht.ContainsKey(s)) c += ht[s];
return c;

}

int countMatches3 ( int [] R, int [] S) {
int c=0;
int pR=0,pS=0;
while (pR < R.Length && pS < S.Length)
if (R[pR] < S[pS]) pR++;
else if (R[pR] > S[pS]) pS++;
else { // R[pR]==S[pS]
int cR=1,cS=1;
while (pR + cR < R.Length && R[pR] == R[pR + cR]) cR++;
while (pS + cS < S.Length && S[pS] == S[pS + cS]) cS++;
c+=cR*cS;
pR += cR;
pS += cS;

}
return c;

}

int countMatches4 ( int [] R, int [] S) {
int c=0;
foreach ( int r in R) {
int pS = getSmallestPositionGE(S, r);
while (pS < S.Length && S[pS] == r) {
c++;
pS++;

}
return c;

}

FIGURE 1.1 Different implementations of function countMatches .