Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Doing it in C and with moderate performance requirements (e.g. ~100_000 elements in each list), I'd go samtregar's way and compare both lists sorted (this is probably faster than sorting the one and binary-searching the other through it when both lists have lengths of the same order).

Doing it in C, but in a high performance situation, I'd try to change the data representation. If we can recast the problem such that the lists can be stored as bit strings, nothing can beat an AND. On a modern processor I can compare 64 elements at a time; unroll the loop 4--8 times and you'll be running about as fast as is possible.

If elements of the lists are integers in a known range, this method is obviously suitable. In other cases, it might be possible to use a hash table (probably called a "symbol table") to translate list elements into indices, and then represent each list as a bitmap.

Note that this approach might or might not be suitable, depending on the precise character of the code. Unfortunately, high-performance solutions often suffer from this problem.

samtregar's solution is also useful in another advanced programming environment. In a shell script, to get common elements of files <samp>AAA</samp> and <samp>BBB</samp> efficiently and in sorted order, try

sort -u AAA > AAA.sorted sort -u BBB > BBB.sorted comm -12 AAA.sorted BBB.sorted > common
This technique works amazingly well, in fact.

In reply to Re: TIMTOWTDI and other languages by ariels
in thread TIMTOWTDI and other languages by Ovid

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, 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, 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.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others rifling through the Monastery: (2)
    As of 2018-04-20 05:41 GMT
    Find Nodes?
      Voting Booth?