Finding palindromes in 10+ languages

I wanted to find some palindromes. So I went digging for a dictionary on my laptop and found a few. There's one in particular which is located at /usr/share/dict/words that is also a linux standard. It's plain text and newline seperated which means easy access. Let's do this.

First attempt: JavaScript
var fs = require('fs')
var words = fs.readFileSync('/usr/share/dict/words').toString().split("\n")
words.map(function(word) {
var forwards = word.toLowerCase().replace(/\W/g, '')
var backwards = forwards.split("").reverse().join("")
if (forwards === backwards) console.log(word + "is a palindrome")
})

That worked and found 197 palindromes as verified by | wc -l. But was it fast? My roommate said he thinks python would be faster.

Python (Credit to gkze for making it more pythonic)
words = open('/usr/share/dict/words', 'r').read().split()
for word in words:
forwards = word.lower()
if forwards == forwards[::-1]:
print word + " is a palindrome"

Turns out they're pretty even if you factor cpu:

Node 0.11.13:    0.18s user   0.03s system   100% cpu   0.213 total
Python 2.7.8:    0.18s user   0.06s system    95% cpu   0.244 total
What about a bash script?
#!/bin/sh
for word in $(cat /usr/share/dict/words);
do
forwards=$(echo $word | awk '{print tolower($0)}')
backwards=$(echo $forwards | rev)
if [ $forwards = $backwards ] ; then
echo "$word is a palindrome"
fi
done

Holy hell was that slow. I only let it finish once and it was minutes of disapointment.

Update: Kenan Kalajdzic sent me the following one-liner that runs in less than half a second!

rev /usr/share/dict/words | paste /usr/share/dict/words - | tr 'A-Z' 'a-z' | paste /usr/share/dict/words - | awk '$2 == $3 { print $1 " is a palindrome" }'
But wait, I bet Go is way faster!
package main
import (
"bufio"
"fmt"
"log"
"os"
"unicode"
)
func main() {
file, err := os.Open("/usr/share/dict/words")
defer file.Close()
if err != nil {
log.Fatal(err)
}
scanner := bufio.NewScanner(file)
for scanner.Scan() {
word := scanner.Text()
a := []rune(word)
a[0] = unicode.ToLower(a[0])
lowercase := string(a)
n := len(lowercase)
runes := make([]rune, n)
for _, rune := range lowercase {
n--
runes[n] = rune
}
backwards := string(runes[n:])
if lowercase == backwards {
fmt.Printf("%s is a palindrome\n", word)
}
}
}

I was correct, Golang runs about twice* as fast as Node and Python:

Golang 1.3.1:    0.11s user   0.01s system   101% cpu   0.112 total
Node 0.11.13:    0.18s user   0.03s system   100% cpu   0.213 total
Python 2.7.8:    0.18s user   0.06s system    95% cpu   0.244 total

* I've since optimized the Go code down to half of this!

Always keep learning

At this point I was interested and wrote it in six more languages. The format of implementing the same logic is great for getting a grasp on a new language very quickly. It was my first time for many of them and I must say a great learning experience.

I won't go through every language for the sake of brevity here were my results after just a day:

Clang 600.0.51:  0.03s user   0.00s system    96% cpu   0.031 total
Rust 0.12.0:     0.03s user   0.00s system    95% cpu   0.036 total
GO 1.3.1:        0.11s user   0.01s system   101% cpu   0.112 total
Ruby 2.0.0:      0.15s user   0.01s system    99% cpu   0.154 total
Haskell 7.8.3:   0.20s user   0.01s system    99% cpu   0.211 total
Node 0.11.13:    0.18s user   0.03s system   100% cpu   0.213 total
Python 2.7.8:    0.18s user   0.06s system    95% cpu   0.244 total
Java 1.6.0:      0.35s user   0.04s system   154% cpu   0.253 total
Scala 2.11.2:    0.67s user   0.08s system   138% cpu   0.538 total
Bash 3.2.53:     It's still running... :P

Optimizing the code

Over the day and going from beginning to end I progressed my view on how to solve the problem. By the end I was thinking about only changing the first character of the string where before it was just lowercase every word. The Rust implementation was originally slow until I added the optimization flag rustc --opt-level=3 which made it jump up to less that 1/20th of a second.

See all the code, compiler settings and more stats on GitHub!

Update:

I've added even more languages and built a benchmarking tool to make comparisons easier.

Here's a sample of the updated results:

benchmarker --quiet -s -r 10 | jq '[.[] | {name: .name, avg: .results.average}]'
[
{
"name": "C",
"avg": 31
},
{
"name": "Rust",
"avg": 31
},
{
"name": "Go",
"avg": 64
},
{
"name": "Lua",
"avg": 115
},
{
"name": "D",
"avg": 134
},
{
"name": "Ruby",
"avg": 143
},
{
"name": "Haskell",
"avg": 176
},
{
"name": "JavaScript",
"avg": 201
},
{
"name": "Python",
"avg": 221
},
{
"name": "PHP",
"avg": 227
},
{
"name": "Java",
"avg": 252
},
{
"name": "Julia",
"avg": 499
},
{
"name": "Scala",
"avg": 523
}
]