Id say if you can speed things up by assuming only a fixed width keyset then do so. However I was intending at some point to convert mine and ysths to a variable width set so it might be worthwhile going both ways. *shrug* For now its safe to assume the search keys are fixed width. :-)

I looked at the optimisation you mentioned regarding moving certain logic outside of the keyloop in your second version. Im not sure if its a good idea to cache those strings, although it will of course speed things up I think it also may be problematic as it drammatically mushrooms the amount of memory your solution needs. For instance with 100_000 keys searching 100k strings you are going to have serious memory issues. So i guess its a tradeoff. I may build a memory ceiling into the test suit so that an object may be at most 400MB or so. While this may be somewhat small its necessary IMO because its around there that my machine will start thrashing and thus blow the utility of any benchmark.

But yeah sure feel free to wait to see the full picture. I just figured youd prefer to get a contender suited up. I have already converted your original solution, and the uncached second solution you posted, and i thought you should have right of reply before i posted them in the new thread.

---
demerphq

In reply to Re^7: Fuzzy Searching: Optimizing Algorithm ( A few improvements). by demerphq
in thread Fuzzy Searching: Optimizing Algorithm Selection by Itatsumaki

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.