Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re^6: The sum of absolute differences in the counts of chars in two strings.

by BrowserUk (Patriarch)
on Nov 24, 2011 at 15:01 UTC ( [id://939908]=note: print w/replies, xml ) Need Help??


in reply to Re^5: The sum of absolute differences in the counts of chars in two strings.
in thread The sum of absolute differences in the counts of chars in two strings.

It might as you say appear to be “brute force,” but, a digital computer is a brutally-powerful machine.The problem space is small and unchanging, and microseconds matter. The overhead of “fancy pants” data structures is pointless and unwanted. The algorithm you wrote runs as fast as it can, such that if you need it to run faster you just have to increase the clock-speed.

It is exactly the above kind of pat, assumptive, bland, non-sequitous, utterly meaningless drivel that you continuously spout, that pretty much guarantees that there'll be no hatchet burying ceremony any time soon.

For an apparently intelligent man with (apparently) lots of computer experience, it beggars belief that you haven't understood the concept that a good algorithm (well implemented) always trumps brute force.

  • Example 1: String in string search.

    Searching for one string inside another string is, according to your logic above, something that can only run as fast as the machine will let it.

    C runtime libraries implement strstr() something like this:

    char *strstr(char *s1, *s2 ) { register char *p = s1; extern char *strchr(); extern int strncmp(); register int len = strlen( s2 ); for( ; (p = strchr( p, *s2 ) ) != 0; p++ ) { if( strncmp( p, s2, len ) == 0 ) { return (p); } } return (0); }

    If you're lucky, then a descent compiler will optimise away (inline) the incestuous function calls in that and may even fold away the multiple calls to strlen() that result, but it is fairly easy to code a solution -- assuming the same constraints and failure modes -- that will beat that implementation.

    So, you would conclude, brute force wins.

    But then what of Boyer-moore, Rabin-Karp, Knuth-Morris-Pratt and Bitap algorithms?

  • Example 2: Fuzzy matching. (N-misses string comparison).

    By your conclusions, a brute force C implementation something like this:

    // Assumes equal length ascii strings and no embedded nulls. int fuzzyMatch( char *a, char *b ) { int sum = 0; while( *a ) if( !( *a++ - *b++ ) ) ++sum; return sum; }

    Should win hands down. And be much quicker than anything one might write in Perl.

    And yet, if we compare that with (the right) pure perl implementation:

    ( $s[ $ai ] ^ $s[ $_ ] ) =~ tr[\0][\0]

    We get the following benchmark results:

    C:\test>fuzzy-b Rate a b a 7.33/s -- -20% b 9.16/s 25% --

    What if I tell you that the pure Perl implementation is tagged 'b' above. That the two-pass, exclusive-OR the two strings and then count the nulls (in Perl) runs 25% faster than the one-pass, pretty optimal, brute force C version? Surprised? Disbelieving?

    Try it for yourself. I very much look forward to your sage analysis and profound wisdom on how this could possibly be so.

    Benchmark code:

What I have a problem with in your posts is the same thing now as when I wrote this back in February. You are still trotting out "potted wisdoms". Usually completely inappropriate to the subject, frequently totally misleading and incorrect, never backed by research or code, nor even citing any actual, tangible evidence.

If you trace our interactions back, you'll (re-)discover that in my earlier attempts to get you to start considering the negative affects of your posts, I was polite, giving you the benefit of the doubt -- but still you continued. As you continued, so did I. And the tone of my refutations grows in strength over time. An attempt to shock you into actually applying some thought prior to posting. It hasn't had any affect.

So, whilst you feel free to proffer such garbage, I continue to feel free, if not obliged, to take issue with it.


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (4)
As of 2024-03-29 05:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found