Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re^2: Finding longest palindrome from a string

by cLive ;-) (Parson)
on Aug 13, 2004 at 19:48 UTC ( #382817=note: print w/ replies, xml ) Need Help??


in reply to Re: Finding longest palindrome from a string
in thread Finding longest palindrome from a string

And so you should be :) Here are the benchmarks...

Rate bgreenlee jasper japhy ccn cLive murugu deiby +z BUU jdporter Random_Walk aristotle fizbin Limbic_Region BrowserUK +elgon bgreenlee 1.99/s -- -44% -45% -50% -88% -90% -90 +% -96% -98% -98% -99% -99% -100% -100% +-100% jasper 3.57/s 79% -- -1% -10% -78% -81% -82 +% -93% -96% -97% -98% -99% -99% -99% + -99% japhy 3.62/s 82% 1% -- -9% -78% -81% -82 +% -93% -96% -97% -98% -99% -99% -99% + -99% ccn 3.99/s 100% 12% 10% -- -76% -79% -80 +% -92% -96% -97% -98% -99% -99% -99% + -99% cLive 16.4/s 723% 359% 353% 311% -- -15% -17 +% -69% -84% -86% -92% -96% -96% -96% + -97% murugu 19.3/s 868% 440% 433% 384% 18% -- -3 +% -63% -81% -84% -90% -95% -95% -96% + -96% deibyz 19.9/s 897% 456% 449% 399% 21% 3% - +- -62% -80% -83% -90% -95% -95% -96% + -96% BUU 52.2/s 2520% 1362% 1343% 1210% 218% 171% 163 +% -- -48% -56% -73% -86% -88% -89% + -89% jdporter 101/s 4965% 2727% 2690% 2432% 515% 423% 408 +% 93% -- -14% -48% -74% -76% -78% + -79% Random_Walk 118/s 5800% 3193% 3150% 2850% 617% 510% 492 +% 125% 16% -- -39% -69% -72% -74% + -75% aristotle 194/s 9646% 5339% 5269% 4773% 1084% 907% 878 +% 272% 92% 65% -- -49% -54% -58% + -59% fizbin 382/s 19041% 10583% 10444% 9470% 2226% 1878% 1820 +% 631% 278% 224% 96% -- -9% -17% + -20% Limbic_Region 420/s 20973% 11662% 11509% 10437% 2461% 2077% 2014 +% 704% 316% 257% 116% 10% -- -8% + -12% BrowserUK 457/s 22836% 12701% 12535% 11368% 2687% 2270% 2200 +% 775% 353% 289% 135% 20% 9% -- + -5% elgon 480/s 23958% 13328% 13153% 11929% 2823% 2386% 2313 +% 818% 375% 308% 147% 26% 14% 5% + --

japhy can be excused since he was golfing. I haven't got much of an excuse though!

I also amended a couple of them to work with @_ correctly :)

cLive ;-)

ps - here's the code I ran. Let me know if I did it wrong (I'm no Benchmark expert):

my @users = qw(BUU ccn Random_Walk cLive murugu jasper deibyz Limbic_R +egion bgreenlee BrowserUK fizbin aristotle jdporter elgon japhy); my $palims = {'2710327103701371111111111111111111611111111111111111111 +116602611111111111111111111111111111111111111111111111111161111111111 +1111111',, '61111111111111111111111111111111111111111111111111 +116', 'abcdefghijklmnopqrstuvwxyz12345678987654321zyxwvutsrqpo +nmlkjihgfedcba', 'abcdefghijklmnopqrstuvwxyz12345678987654321zyxwvuts +rqponmlkjihgfedcba', 'ababcbabcdcbabcdedcbabcdefedcbabcdefgfedcbababcbabcdcba +bcdedcbabcdefedcbabcdefgfedcba', 'edcbabcdefedcbabcde', 'abcdedcbabcdefgfedcbabcdefghijklmnonmlkjihgfedcbabcdefg +hijklkjihgfedcbabcdefghijklmnoponmlkjihgfedcba', 'onmlkjihgfedcbabcdefghijklkjihgfedcbabcdefghijklmno +'}; my $data={}; cmpthese(0, { map { $_ => "test_palindrome('$_')" } @users } ); for my $user (keys %{$data}) { for (keys %{$palim}) { $data->{$user}->{$_} eq $palim->{$_} or print "--$user failed to find $palim->{$_} in $_\n"; } } sub test_palindrome { my $user = $_[0]; my @this_test = keys %{$palims}; $data->{$user}->{$_}=&$user($_) for @this_test; }

Update: Here's another rough benchmark using just one string that's about 5 times longer than the longest I used in the original Benchmark:

Rate bgreenlee ccn japhy jasper deibyz cLi +ve murugu jdporter BUU aristotle Random_Walk BrowserUK fizbin Limbi +c_Region elgon bgreenlee 4.26e-02/s -- -49% -49% -52% -87% -9 +6% -98% -100% -100% -100% -100% -100% -100% + -100% -100% ccn 8.31e-02/s 95% -- -0% -6% -74% -9 +1% -96% -99% -100% -100% -100% -100% -100% + -100% -100% japhy 8.35e-02/s 96% 1% -- -5% -74% -9 +1% -96% -99% -100% -100% -100% -100% -100% + -100% -100% jasper 8.82e-02/s 107% 6% 6% -- -72% -9 +1% -96% -99% -100% -100% -100% -100% -100% + -100% -100% deibyz 0.316/s 642% 280% 279% 258% -- -6 +7% -86% -98% -98% -99% -99% -100% -100% + -100% -100% cLive 0.955/s 2144% 1050% 1044% 983% 202% +-- -58% -93% -95% -97% -98% -99% -99% + -100% -100% murugu 2.25/s 5186% 2610% 2596% 2452% 612% 13 +6% -- -85% -88% -92% -96% -98% -98% + -99% -99% jdporter 14.6/s 34124% 17442% 17354% 16422% 4511% 142 +5% 547% -- -20% -51% -74% -88% -90% + -95% -95% BUU 18.2/s 42589% 21781% 21672% 20509% 5652% 180 +3% 708% 25% -- -38% -67% -85% -88% + -94% -94% aristotle 29.4/s 69070% 35354% 35177% 33292% 9220% 298 +3% 1208% 102% 62% -- -47% -75% -80% + -90% -90% Random_Walk 55.8/s 131043% 67119% 66784% 63211% 17570% 574 +5% 2381% 283% 207% 90% -- -53% -63% + -81% -82% BrowserUK 119/s 278816% 142861% 142148% 134549% 37481% 1233 +2% 5176% 715% 553% 303% 113% -- -21% + -60% -61% fizbin 150/s 352026% 180385% 179486% 169892% 47345% 1559 +5% 6561% 929% 725% 409% 169% 26% -- + -49% -51% Limbic_Region 297/s 697051% 357231% 355450% 336456% 93833% 3097 +4% 13088% 1937% 1533% 908% 432% 150% 98% + -- -2% elgon 304/s 712846% 365327% 363506% 344081% 95961% 3167 +8% 13386% 1983% 1570% 931% 444% 156% 102% + 2% --

Update 2: Ack, nice one BroswerUK (in reply below). Mine fails on the "wrapped string palindrome" too. I think we may need a new thread on this when the test cases are updated.


Comment on Re^2: Finding longest palindrome from a string
Select or Download Code
Re^3: Finding longest palindrome from a string
by BrowserUk (Pope) on Aug 13, 2004 at 21:38 UTC

    Unfortunately, the benchmark doesn't tell the whole story. Many of the regex-based solutions fail on unescaped regex characters.

    All of the faster ones fail to correctly find the longest string when fed either of:

    1111111121111111111112111111111111111111111112111111111111211111 ababacababacadacababacadaeadacabaz

    (Including mine, which is sad, as the first one is my publish test string:()


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Re^3: Finding longest palindrome from a string
by ccn (Vicar) on Aug 13, 2004 at 23:44 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://382817]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2014-08-30 02:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (291 votes), past polls