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

[BrowserUk]

what is it ... that I have overlooked?

Well, apart from the obvious: whatever any one of the other several hundred monks might think of that neither you and I did; you are asking the wrong question.

Instead, try asking yourself: "What did I contribute to the thread?".

And then you might ask yourself the same of Re: windows 7 HardwareID, amongst many others.

[sundialsvc4]

Esteemed colleague, I never intend to “fail to contribute to” any thread that I make or that I comment on ... in a genuinely meaningful way ... and may I cautiously suggest that to hammer me in public with regard to your opinions of my comments ... “does not contribute to the thread?”   I have no quarrel with you.   I regret that you seem to have an unending quarrel with me.   I hope some day to bury that hatchet, because I have never held that weapon in my hand and still don’t.

The “C” solution that you recently posted is both informative and, as I am sure many of us suspected it would be, straightforward.   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.   I appreciate you posting the source-code of what you came up with.

[BrowserUk]

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:

  <Reveal this spoiler or all in this thread>

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.