Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Comment on

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

lindsay_grey:

I've been plunking around for about 4 hours on this one (it's an interesting problem!). I first built a test data generator to generate some datasets.

#!/usr/bin/perl # # gen_random_string.pl <CNT> <SYMS> <minlen> <maxlen> # # Generate <CND> random strings between <minlen> and <maxlen> ch +aracters # using only the characters in <SYMS>. # use strict; use warnings; my $cnt = shift; my $SYMS = shift; my $min = shift; my $max = shift or die usage('Missing args!'); die "CNT ('$cnt') must be numeric!\n" if $cnt =~ /[^0-9]/; die "MIN ('$min') must be numeric!\n" if $min =~ /[^0-9]/; die "MAX ('$max') must be numeric!\n" if $max =~ /[^0-9]/; die "SYMS must be longer than 0 characters!\n" if length($SYMS) < 1; if ($min>$max) { print "Min must be <= Max, swapping!\n"; my $t=$min; $min=$max; $max=$t; } my @syms = split //,$SYMS; #print join(", ", @syms),"\n"; while ($cnt) { my $len=$min + int(($max-$min)*rand); my $t=''; $t .= $syms[int(rand(@syms))] for 1 .. $len; print "$t\n"; --$cnt; }

My primary datasets are 100, 200, 500, 1000, 2000, 5000 and 10000 strings each, where the strings are between 15 and 25 characters long. I generated them like:

$ for J in {1,2,5}0{0,00,000}; do echo $J; perl gen_random_string.pl $ +J ACGTN 15 25 >t.$J; done

I next created a trivial brute-force solver:

#!/usr/bin/perl # # multi-string-match_brute_force.pl <FName> # use strict; use warnings; use feature ':5.10'; my $fname = shift; open my $FH, '<', $fname or die; my @candidates = <$FH>; @candidates = grep { /^[ACGTN]+$/ } # delete the comments map { s/^\s+//; s/\s+$//; $_ } @candidates; my $start = time; @candidates = sort { length($a) <=> length($b) || $a cmp $b } @candida +tes; my @unique; my $cnt_dup=0; OUTER: while (my $t = shift @candidates) { for my $u (@unique) { if ($t =~ /$u/) { ++$cnt_dup; next OUTER; } } push @unique, $t; } my $end = time - $start; print scalar(@unique), " unique items.\n"; print "$cnt_dup rejected.\n"; print "$end seconds\n";

The brute force solver told me that all my datasets contained only unique strings. So I created some datasets with plenty of duplicates:

$ cat t.100 t.100 t.100 > t.300 $ cat t.1000 t.1000 t.1000 > t.3000 $ cat t.10000 t.10000 t.10000 > t.30000 $ cat t.100 t.300 > t.400 $ cat t.1000 t.3000 > t.4000 $ cat t.10000 t.30000 > t.40000

I've been monkeying with some different bits, but my best two (so far) give me the times:

num brute strings force Robo1 Robo2 ------- ------- ----- ----- 100 .125 .125 .110 200 .234 .172 .125 300 .202 .141 .110 400 .234 .156 .110 500 1.030 .187 .125 1000 3.916 .265 .188 2000 15.288 .390 .265 3000 11.435 .546 .328 4000 15.319 .656 .422 5000 93.600 .858 .546 10000 377.412 1.638 1.029 20000 3.151 1.981 30000 4.493 2.621 40000 5.866 3.417 50000 4.929

I then created a few datasets with strings between 200 and 300 characters to see how my better one did:

# str Robo2 Notes ------ ------ -------------- 1000 0.687 unique 2000 1.264 1000 unique 10000 6.412 unique 20000 11.887 10000 unique 100000 65.224 unique 200000 126.190 100000 unique

I'll wait a little while before posting my solution, as I don't want to spoil things for people still working on it right now.

...roboticus

When your only tool is a hammer, all problems look like your thumb.


In reply to Re: list of unique strings, also eliminating matching substrings by roboticus
in thread list of unique strings, also eliminating matching substrings by lindsay_grey

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!
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            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?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others examining the Monastery: (5)
    As of 2014-09-18 00:01 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (101 votes), past polls