Do you know where your variables are? | |
PerlMonks |
Re: Find repeated patterns in stringsby tlm (Prior) |
on Aug 27, 2005 at 17:54 UTC ( [id://487171]=note: print w/replies, xml ) | Need Help?? |
Actually, there's a much simpler solution (codewise): Though I suspect that, for long strings, a solution like the one you proposed but testing only cycles whose lengths are divisors of the input length would be faster. I'll do some benchmarking when I get a chance. Update: Caveat: take my benchmarks with a barrel of salt; despite many burns, I still manage to botch benchmarks routinely. OK, one could test many possible variants. Below I test the case of a string of length about 10_000, consisting of a repeating pattern whose length is given as an input to the benchmarking script. I test three solutions: (0) the original algorithm (plus the minor optimization of not testing cycles longer than half the original string); (1) the modification of the original that tests only cycles whose lengths are divisors of the input string's slength; (2) the regex solution above. For a cycle length of 101 (in a string of length 9999), the results are: So, contrary to my expectation, the regex solution wins handily. On the other hand, for a cycle-free string of comparable length (9973), solution 1 is the clear winner:
And for short cycles in a long string, your original solution cleans house: That's for a cycle of length 3 in a string of length 9999. Full code below:
the lowliest monk
In Section
Cool Uses for Perl
|
|