Your skill will accomplish what the force of many cannot |
|
PerlMonks |
Re: Fast Way to find one array in second array (updated)by LanX (Saint) |
on Aug 14, 2016 at 21:20 UTC ( [id://1169766]=note: print w/replies, xml ) | Need Help?? |
Let X < Y denote set X included in set Y. Instead of speeding up the process to check X < Y , let's reduce the potential number of such checks. At the moment you are ordering all sets S and testing for each X if you find a bigger Y with X < Y, and then you go on with the next X'. This means a worst case of n(n-1)/2 tests for n sets (no inclusions found) And at some point you start checking all sets bigger Y to find a Z with Y < Z. BUT
X < Y < Z => X < Z So instead of stopping after finding Y record all X* := { S | X < S } and push X into Y° := { S | S < Y }. Once you reach Y you'll only have to check Y against the sets S in the intersection of all X* for X in Y°. The worst case of this approach is the same, but I'm sure it'll be faster on average.² Such algorithms can certainly be found in literature, but I don't have the time to check now. ³ HTH
Cheers Rolf
²) I suppose this approach is more efficient if you stop growing a X* after it reached a certain size - like n/2 or so - and take X out of consideration. ³) probably looking for keyword "posets" = partially ordered sets
updateOn second thought, restricting to calculate X* only for those X ( atoms ) which don't have a lower neighbor, i.e. there is no X' < X <=> X° is empty so far , should be good enough. Then - visually speaking - those X with an X* form "axes" of the poset and the Y° are the "coordinates" of Y - like when embedded in a n* dimensional cube. I'll implement this after YAPC, feel free to do earlier...
updateIn hindsight for this particular task it might be more efficient to apply this to the dual poset. That is starting with the biggest sets and on the fly calculating the coatoms Y, which have no superset. For any S with S < X there must be a coatom with S < X <= Y.
In Section
Seekers of Perl Wisdom
|
|