palindrome function

[Jonathan M Davis]

On Saturday 07 August 2010 16:56:08 ex wrote:
> Hello!
> I'm learning D and I was wondering on what can be optimized of my
> implementation of a palindrome function:
> 
> bool isPalindrome(int num) {
>     string s = text(num);
>     int len = s.length;
>     for (int i = 0; i < len / 2; ++i) {
>         if (s[i] != s[len - 1 - i]) {
>             return false;
>         }
>     }
>     return true;
> }
> 
> 1) Is std.conv.text() the best function to call here to convert a number to
> string?

Use to!string(num) instead of text(num).

> 2) Does using a variable to store the string length is more efficient than
> calling the length method?

length is a property, not a method. I find it highly unlikely that storing length 
in a variable is going to make it any faster.

> 3) This example use numeric characters but if the string were UTF8 the []
> operator would be OK for multibyte characters?

Using [] with strings is a _bad_ idea. [] gives you the chars (or wchars in the 
case of wstring). chars are UTF-8 code units, and wchars are UTF-16 code units. 
If you want to use [] with a string, use a dstring, since dchars are UTF-32 code 
units, and unlike UTF-8 and UTF-16, a code unit and a code point are the same 
size. A code point represents what you would usually consider a character, while 
a code unit is one portion of a character's encoding (which could be the whole 
thing if the character is only one code unit which ASCII characters would be).

For instance, if you're looping over a string or wstring, you need to use dchar 
even if though the array itself is char or wchar:

foreach(dchar c; str)
{
  //...
}

The compiler understands the conversion and loops over the code points rather 
than the code units. [] isn't going to work with strings and wstrings if you 
want code points (characters) rather than code units. So, in your function, 
you'd want to use dstring rather than string. So, you'd do

auto s = to!dstring(num)

to get your string.


> 
> Not related:
> 
> 4) Is some way to declare the nested functions at the end, this way I could
> create nice "routines" of a function.

You can declare nested functions, but I think that they're like local variables 
in that they have to be declared before you can use them. Otherwise, the symbol 
isn't in scope yet when you try and use it.

> 5) I could not find in the documentation if when I declare a variable
> inside a block (a loop for example) that variable creation is optimized by
> the compiler.

Whether the compiler optimizes stuff or not is not likely to be in the 
documentation. That's not part of the D spec and is entirely implementation-
dependent. You're going to have to look at the generated assembly code if you 
want to know what it actually, does.


As for a better way to do what you're doing, I'd do this:

bool isPalindrome(int num)
{
    auto s = to!dstring(num);

    while(!s.empty)
    {
        if(s.length == 1)
            return true;

        if(s.front != s.back)
            return false;

        s.popFront();
        s.popBack();
    }

    return true;
}

It would be more typical to use strings as ranges in this manner. Also, in this 
case, it doesn't matter whether you use string, wstring, or dstring, since 
front, back, popFront(), and popBack() all deal with the unicode properly. front 
and back return dchar in all cases, and popFront() and popBack() always pop a 
code point rather than a code unit. It's probably better to use a dstring in 
this case because then no conversions have to take place from UTF-8 or UTF-16 to 
UTF-32, but it probably doesn't matter unless you're calling the function a lot.

In addition, this version of the code is easier to read than having to deal with 
array indicies.

- Jonathan M Davis