Quote:
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.