Palindromes
Title: Palindromes
Date: 2008 08 17
Icon: programming
Tags: programming, d language, c, python

The problem is to create a function that returns true if the given input string is Palindrome, ignoring the case of chars and non-alphanumeric chars.

A short high-level Python version:

def is_pali(s):
    s2 = filter(str.isalpha, s.lower())
    n2 = len(s2) // 2
    return s2[:n2][::-1] == s2[n2 + len(s2) % 2:]

The same translated to D, using my libs:

import d.all, std.ctype;
import std.string: tolower;

bool is_pali(string s) {
    string s2 = filter(&isalpha, s.tolower());
    int n2 = len(s2) / 2;
    return s2[0 .. n2].reverse == s2[n2 + len(s2) % 2 .. $];
}

A faster lower-level D version:

bool is_pali(string s) {
    if (!s.length)
        return true;
    char* p1 = &s[0];
    char* p2 = &s[$ - 1];
    while (*p1 < *p2) {
        if ((97 <= *p1 && *p1 <= 122) || (65 <= *p1 && *p1 <= 90)) {
            if ((97 <= *p2 && *p2 <= 122) || (65 <= *p2 && *p2 <= 90)) {
                if (((*p1) | 32) != ((*p2) | 32)) {
                    return false;
                } else {
                    p1++;
                    p2--;
                }
            } else {
                p2--;
            }
        } else {
            p1++;
        }
    }

    return true;
}

unittest {
    assert(is_pali(""));
    assert(is_pali("a"));
    assert(is_pali("aia"));
    assert(is_pali("aiA"));
    assert(!is_pali("aie"));
    assert(is_pali("a,"));
    assert(is_pali("a,a"));
    assert(is_pali("A,A,a"));
    assert(is_pali("aiia"));
    assert(is_pali("l'aia'l"));
    assert(is_pali("Madam I'm Adam"));
    assert(is_pali("Asor Rosa"));
    assert(!is_pali("Hello"));
    assert(is_pali(".,"));
}

void main() {
    int r;
    for (int i; i < 30_000_000; i++) {
        r = is_pali("") +
            is_pali("a") +
            is_pali("aia") +
            is_pali("aiA") +
            is_pali("aie") +
            is_pali("a,") +
            is_pali("a,a") +
            is_pali("A,A,a") +
            is_pali("aiia") +
            is_pali("l'aia'l") +
            is_pali("Madam I'm Adam") +
            is_pali("Asor Rosa") +
            is_pali("Hello") +
            is_pali(".,");
    }
    
    printf("%d\n", r);
}

My faster version, in C:

#include "ctype.h"
#include "stdio.h"

int is_pali(char* s, int n) {
    if (!n)
        return 1;
    char* p1 = &s[0];
    char* p2 = &s[n - 1];

    while (*p1 < *p2) {
        if ('A' <= *p1 && *p1 <= 'Z') {
            if ('A' <= *p2 && *p2 <= 'Z') {
                if (*p1 == *p2) {
                    p1++;
                    p2--;
                } else {
                    return 0;
                }
            } else if ('a' <= *p2 && *p2 <= 'z') {
                if (((*p1) | 32) == *p2) {
                    p1++;
                    p2--;
                } else {
                    return 0;
                }
            } else {
                p2--;
            }
        } else if ('a' <= *p1 && *p1 <= 'z') {
            if ('A' <= *p2 && *p2 <= 'Z') {
                if (*p1 == ((*p2) | 32)) {
                    p1++;
                    p2--;
                } else {
                    return 0;
                }
            } else if ('a' <= *p2 && *p2 <= 'z') {
                if (*p1 == *p2) {
                    p1++;
                    p2--;
                } else {
                    return 0;
                }
            } else {
                p2--;
            }
        } else {
            p1++;
        }
    }

    return 1;
}

int main() {
    int i, r;
    for (i = 0; i < 30000000; i++) {
        r = is_pali("", 0) +
            is_pali("a", 1) +
            is_pali("aia", 3) +
            is_pali("aiA", 3) +
            is_pali("aie", 3) +
            is_pali("a,", 2) +
            is_pali("a,a", 3) +
            is_pali("A,A,a", 5) +
            is_pali("aiia", 4) +
            is_pali("l'aia'l", 7) +
            is_pali("Madam I'm Adam", 14) +
            is_pali("Asor Rosa", 9) +
            is_pali("Hello", 5) +
            is_pali(".,", 2);
    }
    printf("%d\n", r);
    return 0;
}

Timings, n = 30_000_000:
C: 0.66 s
D: 2.84 s

I don't know why the faster D version isn't the same as the C version, maybe because the DMD D compiler is less good than GCC in optimizing branches.
The C version on average takes a little more than 4 CPU clock ticks for each of the input strings.