Programming Exercise #1

[Kristi]

Originally Posted by Tolnaftate2004

PHP Code:

function S3(arrA,arrB) {
  temp.intersect.clear();
  temp.sets.clear();
  if (arrA.size() > arrB.size()) temp.c = {arrB,arrA};
  else                           temp.c = {arrA,arrB};

  for (elmt: temp.c[0]) {
    if (elmt in temp.c[0])
      temp.intersect.add(elmt);
  }

  temp.len = temp.intersect.size();
  for (temp.i=0; temp.i<temp.len-2; temp.i++) {
    for (temp.j=temp.i+1; temp.j<temp.len-1; temp.j++) {
      for (temp.k=temp.j+1; temp.k< temp.len; temp.k++) {
        temp.sets.add({temp.intersect[temp.i],temp.intersect[temp.j],temp.intersect[temp.k]});
      }
    }
  }
  return temp.sets;
} 


This has O(N+N!/((N-3)!*3!)), N ≤ min{a.size(),b.size()}.

^_^ this is an open discussion. Please explain why this is better then the naive algorithm
Also, in your big O, did you include the search time for the "in" operator in your intersect portion? I can see a few ways to optimize that.

[Tolnaftate2004]

Originally Posted by Kristi

Also, in your big O, did you include the search time for the "in" operator in your intersect portion? I can see a few ways to optimize that.

A good point: O(N1*N2 + N!/((N-3)!*3!))

I had originally intended to do something along these lines:

PHP Code:

  for (elmt: temp.c[0]) {
    if (elmt in temp.c[1])
      temp.intersect.add(elmt);
  } 


becomes

PHP Code:

  while (temp.c[0].size()) {
    temp.elmt = temp.c[0][0];
    if (temp.elmt in temp.c[1]) {
      temp.intersect.add(temp.elmt);
      temp.c[0].remove(elmt);
      temp.c[1].remove(elmt);
    } else temp.c[0].delete(0);
  } 


Still O(N1*N2), but often less.
It just slipped my mind. Silly me.
Also, first thing should be if (arrA.size() > 2 && arrB.size() > 2)...

As for the naive algorithm, It has O(N2^3*N1!/((N1-3)!*3!)) (?), I think.

[Kristi]

Originally Posted by Tolnaftate2004

A good point: O(N1*N2 + N!/((N-3)!*3!))

I had originally intended to do something along these lines:

PHP Code:

  for (elmt: temp.c[0]) {
    if (elmt in temp.c[1])
      temp.intersect.add(elmt);
  } 


becomes

PHP Code:

  while (temp.c[0].size()) {
    temp.elmt = temp.c[0][0];
    if (temp.elmt in temp.c[1]) {
      temp.intersect.add(temp.elmt);
      temp.c[0].remove(elmt);
      temp.c[1].remove(elmt);
    } else temp.c[0].delete(0);
  } 


Still O(N1*N2), but often less.
It just slipped my mind. Silly me.
Also, first thing should be if (arrA.size() > 2 && arrB.size() > 2)...

As for the naive algorithm, It has O(N2^3*N1!/((N1-3)!*3!)) (?), I think.

Deleting elements from the array and etc is actually going to make it take longer to process.

Anyway, hashes would optimize finding the intersect, but graal has no support for it. However, we can dynamically name variables, so we can emulate it well enough for this situation.

code snippet:

PHP Code:

for(e: temp.array1)
   temp.b.("v"@e) = true;

for(e: temp.array2)
   if(temp.b.("v"@e))
     temp.intersect.add(e); 


with larger datasets, this gets exponentially faster. with 5000-10000 element arrays, its literally 120x faster then searching through the arrays for intersects.

Also, it would be slightly faster to make an array with the max possible size first, so you're not resizing the array (and thus possibly moving it to a new location in memory constantly.)

PHP Code:

  temp.intersect = new[smallerarray.size()];

  for(e: temp.largerarray)
   temp.b.("v"@e) = true;

  for(e: smallerarray)
   if(temp.b.("v"@e)) {
     temp.intersect[temp.j] = e;
     temp.j++;
   } 


This does in fact improve performance, although it's not terribly noticeable.

I'll optimize finding the sets from the intersects later. Lets let this soak in first.