Palindromes (Clojure)

* Update 2009-12-27 * Using lists instead of vectors brings the Clojure version down from around 20x to 10X slower than the CL version. One reader correctly stated that when doing performance comparisons between languages and implementations you want the code and data structures to be as identical as possible.

“A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted.”

Here we look at an implementation of a function(in Clojure) that finds the longest palindrome in some text. Let’s also look at the worst case time and space performance.

First a naive version of the core function :

(defn longest-pals-naive
  "O(n^2) time complexity, O(n) space complexity"

  (let* [afirst 0
         alast (dec (count text))
         positions (transient [])]

        (letfn [(ext-pal-around
                 [start end]
                 (if (or (< start 0) (> end alast) 
                         (not (= (nth text start) (nth text end))))
                   (- end start 1)
                   (recur (dec start) (inc end))))
                 (let [pos (long (/ position 2))
                       nstart (dec (+ afirst pos))
                       nend (cond (even? position) (+ afirst pos)
                                  (odd? position) (+ afirst pos 1))]
                   (ext-pal-around nstart nend)))]

          (dotimes [n (* 2 (inc alast))]
            (conj! positions (pal-len-around n)))
          (persistent! positions))))

The best of 3 runs on a very underpowered netbook (1.6GHz atom cpu) :

user=> (#'i27.palindromes/big-test)
1000 X ' amanaplanacanalpanama ' 
naive : "Elapsed time: 6011.032 msecs"

Now a more optimized and slightly more complex version that runs in linear time :

(defn longest-pals-fast
  "O(n) time & space complexity"

  (letfn [(final-centers
           [n tcenters centers]
            (<= n 1)
            (let [n (dec n)]
              (recur n
                     (rest tcenters)
                     (concat (vector 
                              (min (first tcenters) n))
           [strn n centers tcenters cdist]
            (= 0 cdist)
            #(ext-tail strn (inc n) 1 centers)
            (= (dec cdist) (first tcenters))
            #(ext-tail strn n (first tcenters) centers)
            #(ext-centers strn n 
                           (vector (min (first tcenters) (dec cdist))) 
                          (rest tcenters) (dec cdist))))

           [strn n curr-tail centers]
            (> n (dec (count strn)))
            #(final-centers curr-tail centers
                            (concat (vector curr-tail) centers))
            (= (- n curr-tail) 0)
            #(ext-centers strn n 
                          (concat (vector curr-tail) centers)
                          centers curr-tail)
            (= (nth strn n) (nth strn (- n curr-tail 1)))
            #(ext-tail strn (inc n) (+ 2 curr-tail) centers)
            #(ext-centers strn n
                          (concat (vector curr-tail) centers)
                          centers curr-tail)))
           (reverse (trampoline #(ext-tail strn 0 0 []))))]

    (pal-around-centers text)))

It’s obviously much quicker than the naive version and some Clojure experts might even be able to come up with a few tricks for tweaking the code (possibly using lists instead of vectors and consing instead ?).

user=> (#'i27.palindromes/big-test)
1000 X ' amanaplanacanalpanama '
fast  : "Elapsed time: 524.958 msecs"

A Common Lisp implementation looks very similar …

(defun longest-pals-fast (text)
  "O(n) time & space complexity"

  (declare (optimize (speed 3) 
                     (compilation-speed 0) 
                     (space 0) (debug 0)))

  (labels ((final-centers (n tcenters centers)
               ((<= n 0) centers)
                (let ((n (- n 1)))
                   (rest tcenters)
                    (min n (first tcenters))
           (ext-centers (text n centers tcenters cdist)
               ((= 0 cdist)
                (ext-tail text (+ 1 n) 1 centers))
               ((= (- cdist 1) (first tcenters))
                (ext-tail text n (first tcenters) centers))
                (ext-centers text n 
                               (min (- cdist 1) (first tcenters))
                             (rest tcenters) (- cdist 1)))))
           (ext-tail (text n curr-tail centers)
               ((> n (- (length text) 1))
                (final-centers curr-tail centers 
                               (cons curr-tail centers)))
                ((= (- n curr-tail) 0)
                 (ext-centers text n 
                              (cons curr-tail centers)
                              centers curr-tail))
                ((eql (elt text n) (elt text (- n curr-tail 1)))
                 (ext-tail text (+ 1 n) (+ 2 curr-tail) centers))
                 (ext-centers text n
                              (cons curr-tail centers)
                              centers curr-tail))))
           (pal-around-centers (text)
             (ext-tail text 0 0 '())))
    (pal-around-centers text)))

… except that the CL version is about 20X quicker :

triton:palindromes jgrant$ sbcl --noinform --load palindromes.lisp  
                                --eval "(progn (big-test) (quit))"

1000 X ' amanaplanacanalpanama ' 

fast : 
Evaluation took:
  0.024 seconds of real time
  0.023747 seconds of total run time (0.022532 user, 0.001215 system)
  100.00% CPU
  38,248,776 processor cycles
  460,656 bytes consed

All code can be found here :
Common Lisp and
(an imperative implementation for comparison but beware it’s buggy !).

Winter 2009 reading

Sonoluminescence: A Galaxy of Nanostars Created in a Beaker (NASA)

The Idea Factory – Learning to Think at MIT, Pepper White :

“This is a personal story of the educational process at one of the world’s great technological universities. Pepper White entered MIT in 1981 and received his master’s degree in mechanical engineering in 1984. His account of his experiences, written in diary form, offers insight into graduate school life in generalβ€”including the loneliness and even desperation that can result from the intense pressure to succeedβ€”and the purposes of engineering education in particular. The first professor White met at MIT told him that it did not really matter what he learned there, but that MIT would teach him how to think. This, then, is the story of how one student learned how to think.”

Bio-Inspired Artificial Intelligence – Theories, Methods, and Technologies, Dario Floreano and Claudio Mattiussi :

“New approaches to artificial intelligence spring from the idea that intelligence emerges as much from cells, bodies, and societies as it does from evolution, development, and learning. Traditionally, artificial intelligence has been concerned with reproducing the abilities of human brains; newer approaches take inspiration from a wider range of biological structures that that are capable of autonomous self-organization. Examples of these new approaches include evolutionary computation and evolutionary electronics, artificial neural networks, immune systems, biorobotics, and swarm intelligenceβ€”to mention only a few. This book offers a comprehensive introduction to the emerging field of biologically inspired artificial intelligence that can be used as an upper-level text or as a reference for researchers.”

On the Edge – The Spectacular Rise and Fall of Commodore, Brian Bagnall :

“Filled with first-hand accounts of ambition, greed, and inspired engineering, this history of the personal computer revolution takes readers inside the cutthroat world of Commodore. Before Apple, IBM, or Dell, Commodore was the first computer maker to market its machines to the public, eventually selling an estimated 22 million Commodore 64s. These halcyon days were tumultuous, however, owing to the expectations and unsparing tactics of founder Jack Tramiel. Engineers and managers share their experiences between 1976 and 1994 of the groundbreaking moments, soaring highs, and stunning employee turnover that came with being on top of the PC world in the early computer business.”

The Road to Reality : A Complete Guide to the Laws of the Universe – Roger Penrose :

“At first, this hefty new tome from Oxford physicist Penrose (The Emperor’s NewMind) looks suspiciously like a textbook, complete with hundreds of diagrams and pages full of mathematical notation. On a closer reading, however, one discovers that the book is something entirely different and far more remarkable. Unlike a textbook, the purpose of which is purely to impart information, this volume is written to explore the beautiful and elegant connection between mathematics and the physical world. Penrose spends the first third of his book walking us through a seminar in high-level mathematics, but only so he can present modern physics on its own terms, without resorting to analogies or simplifications (as he explains in his preface, “in modern physics, one cannot avoid facing up to the subtleties of much sophisticated mathematics”). Those who work their way through these initial chapters will find themselves rewarded with a deep and sophisticated tour of the past and present of modern physics. Penrose transcends the constraints of the popular science genre with a unique combination of respect for the complexity of the material and respect for the abilities of his readers. This book sometimes begs comparison with Stephen Hawking’s A Brief History of Time, and while Penrose’s vibrantly challenging volume deserves similar success, it will also likely lie unfinished on as many bookshelves as Hawking’s. For those hardy readers willing to invest their time and mental energies, however, there are few books more deserving of the effort.”

Born to Run – A Hidden Tribe, Super Athletes, and the Greatest Race the World Has Never Seen, Christopher McDougall :

“Full of incredible characters, amazing athletic achievements, cutting-edge science, and, most of all, pure inspiration, Born to Run is an epic adventure that began with one simple question: Why does my foot hurt? In search of an answer, Christopher McDougall sets off to find a tribe of the world’s greatest distance runners and learn their secrets, and in the process shows us that everything we thought we knew about running is wrong.”