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
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!

²) 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

update

On 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...

update

In 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 reply to Re: Fast Way to find one array in second array (updated) by LanX
in thread Fast Way to find one array in second array by melmoth

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.