It'll run in O(n^2), which is reasonable for what you're doing. However, you can speed that up some, so it runs in more like n log n, for the non-pathological cases. 
foreach my $itemIndex (1 .. $items->Count)
{
    my ($body) = $items->Item($itemIndex)->Body =~ /MessageBody>(.*)<\
+/Mess/s;

    if ($body !~ /\S/)
    {
        die "Some appropriate error on index $itemIndex.";
    }

    CACHE_CHECK:
    foreach my $cachedItem (@cache)
    {
        my $compare = $cachedItem->[0];
        my $len = length($body) > $length($compare) ? length($body) : 
+length($compare);

        if (distance($body, $compare) / $len < $threshold)
        {
            @toBeMoved[$itemIndex, $cachedItem->[1]] = (1, 1);
            last CACHE_CHECK;
        }
    }
}

[download]

The primary differences here are:

  1. I have made @toBeMoved into kind of a bit-flag. You loop through that list later and only deal with the items marked true
  2. Once I find a match, I stop looking.

The second item is the major speed-up. You might not agree with it. If not, then get rid of the last. My thought was that your operation is transitive, or if A & B work and B & C work, then A & C will work. If that's not the case, then change it.

------
We are the carpenters and bricklayers of the Information Age.

The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6

... strings and arrays will suffice. As they are easily available as native data types in any sane language, ... - blokhead, speaking on evolutionary algorithms

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

In reply to Re: Quicker Array Searching by dragonchild
in thread Quicker Array Searching by Anonymous Monk

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.