Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
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":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
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 avoiding work at the Monastery: (4)
As of 2021-06-16 20:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What does the "s" stand for in "perls"? (Whence perls)












    Results (80 votes). Check out past polls.

    Notices?