Largest Palindrome

[Chris Dollin]

(e-mail address removed) wrote:
(fx:snip)


is it september already?

For the last ten years.

 

[Frederick Gotham]

lovecreatesbeauty posted:

Hello Old Wolf and Richard, could you write some graceful versions of
palindromic function

Here's how I'd probably go about it.

I'd start off with a function signature like:

int IsPalindrome(char const *p,
int (* const Equality)(char,char),
int (* const Immune)(char) )

I'd create a pointer to the start of the string, and a pointer to the end
of the string. I'd increment the former, and decrement the latter, each
time firstly checking if either char is immune from the test (e.g. non-
alphabetic), and then checking their equality.

The bare bones would be something like:


(Unchecked code, likely to contain errors)


#include <stddef.h>
#include <string.h>

int IsPalindrome(char const *p_start,
int (* const Equal)(char,char),
int (* const Immune)(char) )
{
size_t const len = strlen(p);

char const *p_end = p_start + (len - 1);

for( ; ; ++p_start, --p_end)
{
if(p_end - p_start <= 0) return 1;

while(Immune(*p_start)) ++p_start;
while(Immune(*p_end)) --p_end;

if(p_end - p_start <= 0) return 1;

if(!Equal(*p_start,*p_end)) return 0;
}
}

 

[Michael Wojcik]

If it does, it only saves it in the case where the first half of the
or-expression is true, ie if *right points to an uppercase letter
which is the same letter as pointed to by *left. In normal English
prose, uppercase letters are relatively infrequent, so the second
call would only be skipped in rather uncommon circumstances when
operating on normal input.

If it *is* skipped, on a typical modern general-purpose CPU, you're
likely to have a branch misprediction penalty, so there go any
savings.

Or if toupper and tolower are implemented as efficient macros your
method might be slower.

Indeed it might, since it introduces another branch.

More important, though, is that there's no evidence that this
"optimization" is at all justified. Is the runtime of this loop
crucial to any outside process? Who needs to shave a millisecond
off the time taken to find the palindrome?

So what we have is premature optimization, and probably adverse
optimization at that.

--
Michael Wojcik (e-mail address removed)

Poe said that poetry was exact.
But pleasures are mechanical
and know beforehand what they want
and know exactly what they want. -- Elizabeth Bishop

 

[lovecreatesbeauty]

If it does, it only saves it in the case where the first half of the
or-expression is true, ie if *right points to an uppercase letter
which is the same letter as pointed to by *left. In normal English
prose, uppercase letters are relatively infrequent, so the second
call would only be skipped in rather uncommon circumstances when
operating on normal input.

Yeah! It's more efficient after exchange those two function call, make
it as:

if (tolower(*left) == *right || toupper(*left) == *right){

/* the previous one was:
if (toupper(*left) == *right || tolower(*left) == *right){ */

Palindromes are rather common English (so the latest change may not be
more efficient), and no one knows what the largest palindrome will be.

Madam, I'm Adam!
A man, a plan, a canal - Panama!
Able was I, ere I saw Elba.
Ana voli Milovana

lovecreatesbeauty

 

[lovecreatesbeauty]

/*palindrome.c*/

#include <stddef.h>
#include <string.h>
#include <ctype.h>

/*determine a sentence if it is a palindrome. s: the string to be
determined. return 1 for identifying a successful palindrome, 0 for
not. The code is mainly derived from Robert Gamble's code. - jhl, Jul 2006*/

int palindrome(const char *s)
{
int pln = 1;
const char *left, *right;

if (s != NULL){
left = s;
right = s + strlen(s) - 1;
while (left < right){
if (!isalnum(*left)){
++left;
continue;
}
if (!isalnum(*right)){
--right;
continue;
}

if (toupper(*left) == *right || tolower(*left) == *right){
++left;
--right;
continue;
} else {
pln = 0; /*charaters occur mismatched, it is not palindrome*/
break;
}
}
}

return pln;
}

The code is mainly derived from Robert Gamble's code. Thanks.

 

[Michael Wojcik]

Yeah! It's more efficient after exchange those two function call, make
it as:

if (tolower(*left) == *right || toupper(*left) == *right){

Well, there's a small lesson: when optimizing, concentrate on the
most common cases first, as a general rule.

But this was the least important of my points. As Flash originally
pointed out, on most implementations it's likely that:

if (tolower(*left) == tolower(*right))

is more efficient than either of your variations, as well as being
shorter and arguably clearer. (This style of coding may also be less
prone to error, as you only have to get the identifiers "left" and
"right" correct once.)

And *far* more important is the realization that *performance almost
certainly does not matter here*. Prefer instead to concentrate on
correctness and readability.

 

[Flash Gordon]

Well, there's a small lesson: when optimizing, concentrate on the
most common cases first, as a general rule.

But this was the least important of my points. As Flash originally
pointed out, on most implementations it's likely that:

if (tolower(*left) == tolower(*right))

is more efficient than either of your variations,

There is another lesson as well. Optimisation really is for experts
only, because if you are not an expert on the specific implementation it
is quite easy for your supposed optimisation to actually produce code
that is almost certain to be slower (as with lovecreatsbeauty's original
suggestion).

> as well as being
shorter and arguably clearer. (This style of coding may also be less
prone to error, as you only have to get the identifiers "left" and
"right" correct once.)

And *far* more important is the realization that *performance almost
certainly does not matter here*. Prefer instead to concentrate on
correctness and readability.

Even where performance does matter I would still concentrate on clarity,
correctness and maintainability first. If, having done that, I can't get
the required performance, I will look at what the compiler produces and
see if that suggests any optimisations (with one Pascal compiler,
replacing constant calculations with the *commented* calculated value
was a good optimisation since it did the calculation at run time!). When
that does not allow me to optimise it enough, I have stopped wasting
time trying to guess how to get the compiler to produce good enough code
and written the *small* (usually) critical section directly in
assembler, but I've only needed to do that with one small piece of code
I knew would be hard for any compiler to optimise on the DSP processor,
and one entire project where the processor was a real bitch for a
horrible processor and the hardware was a long way under specified.

Oh, and ensuring that where lots of large structures are passed around
they are passed by reference (this was Pascal, so passing a pointer to
the struct in C) rather than passing the large structures by value.
Having done that, I politely pointed out to my manager that the original
design was completely wrong, so even though I have more than doubled the
speed of the code (thus making it work) it should not have been anything
like that design in the first place. Then he told me that he had
originally designed it, which made me very glad I had been polite about
it! Another thing this taught me was the importance of designing
software so that when overloaded it degrades gracefully rather than
having the first overload cause a slow down leading to more overload
leading to more slow down leading very quickly to it all grinding to a
halt as soon as the critical threshold is exceeded. Admittedly this last
lesson is not appropriate in all instances, but it does often mean that
people will get possibly a little annoyed about some jerkiness instead
of extremely pissed off with it suddenly not working.

 

[av]

There is another lesson as well. Optimisation really is for experts
only, because if you are not an expert on the specific implementation it
is quite easy for your supposed optimisation to actually produce code
that is almost certain to be slower (as with lovecreatsbeauty's original
suggestion).

if "Optimisation" is for experts only, nobody could optimise anything.

 

[Richard Heathfield]

av said:

if "Optimisation" is for experts only, nobody could optimise anything.

Hold that thought. It will serve you well.

Until you realise that optimisation is a function of design rather than
programming, you're not ready. By the time that lesson sinks in, you're
probably well on the way to becoming an expert anyway.

 

[Richard Bos]

if "Optimisation" is for experts only, nobody could optimise anything.

First rule of optimisation: Don't Do It.
Second rule of optimisation (for expert only): Don't Do It Yet.

HTH; HAND.

Richard

 

[av]

First rule of optimisation: Don't Do It.
Second rule of optimisation (for expert only): Don't Do It Yet.

noone become expert if not try to optimize
so if noone of not expert optimize there will be no expert

 

[Frederick Gotham]

av posted:

noone become expert if not try to optimize
so if noone of not expert optimize there will be no expert

noone learn read and rite witout lerning alfabet & lerning gramar & how 2
spel.

 

[Keith Thompson]

noone become expert if not try to optimize
so if noone of not expert optimize there will be no expert

Fortunately, real life doesn't work that way. There are plenty of
experts who are capable of optimizing code. If they're experts, they
know when not to do it.