Wishful Coding

Didn't you ever wish your
computer understood you?

Blogging like a Ruby Hacker

Kind of a weird thing to say for someone who does not program Ruby, don’t you think?

I have been wanting to move away from Posterous for quite a while now. I’ve searched for solutions in languages I know and even spent some time writing something in Clojure.

All in all, I wasn’t getting anywhere, so I just said to myself that I wanted to have my blog in a static site generator today.

I chose Jekyll because it’s the first and most popular one I knew. It’s also used by Github and is named after “The Strange Case of Dr Jekyll and Mr Hyde”. Only, it’s in Ruby.

It turns out Ruby syntax is quite easy to guess right for a Python dev. Before I could get started, I had to hack a Posterous migrator to support my old links, tags and images.

So, I hope you like my new old theme and that you don’t find to much broken stuff.

I don’t have comments for the moment, so you’ll have to email me when you have problems. I do plan to add search from Tapir soon.

Published on

My Bookshelf 3/5: Seven Languages in Seven Weeks

Phew, that took a while. I actually did some languages in under a day, but overall, 7 weeks is about what it took me.

My Bookshelf 3/5: Seven Languages in Seven Weeks

You can argue endlessly about which languages to include in the book, but I think he made a balanced choice that leads to a progressive increase in new concepts.

The book starts easy with Ruby, a mainstream OO language that is the native tongue of the author. Then, we move to prototype inheritance(Io), Logic programming(Prolog), and take the plunge into functional programing with Scala, followed by Erlang, Clojure, and finally the most functional of them all; Haskell.

If you want to learn on specific language well, this book is not for you. But if you are the kind of person who wants to taste every cake in existence, it's great!

My Bookshelf 3/5: Seven Languages in Seven Weeks

The author recommends you to do all the exercises "otherwise it'll just be some syntax". I disagree here. For languages where I did not do the exercises, I remember only concepts, not any syntax at all. This is why I'm reading it, because of concepts, not to actually work with Io(though it's a gem).

So, it's a nice book, but if you want to learn some really wicked stuff, I suggest you also check out these languages suggested by Michael Fogus. (who is also the co-author of the next book on my shelf, Joy of Clojure)
Published on

Lazy sorting

I was inspired by Edmund's post to try some other lazy sorts. These are far from competitive to Java's timsort, but they are an interesting concept.

It is not possible to make timsort lazy because it uses insertion sort which does not work that way.

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. For selection sort these are the k smallest elements, while in insertion sort they are whatever the first k elements were in the unsorted array.

A chunked lazy timsort might be attempted though. Another option might be to use selection sort instead, or use another compounded sort like introsort.

Update: I added an insertion sort and a chunked lazy timsort, without all the frills that make it actually run fast.

all    #'clojure.core/sort "Elapsed time: 67.987 msecs"
sorted #'clojure.core/sort "Elapsed time: 22.214 msecs"
first  #'clojure.core/sort "Elapsed time: 56.249 msecs"

all    #'test/qsort "Elapsed time: 717.93 msecs"
sorted #'test/qsort "Elapsed time: 12388.316 msecs"
first  #'test/qsort "Elapsed time: 30.976 msecs"

all    #'test/msort "Elapsed time: 1317.334 msecs"
sorted #'test/msort "Elapsed time: 945.077 msecs"
first  #'test/msort "Elapsed time: 708.803 msecs"

all    #'test/hsort "Elapsed time: 83.909 msecs"
sorted #'test/hsort "Elapsed time: 75.235 msecs"
first  #'test/hsort "Elapsed time: 28.91 msecs"

all    #'test/isort "Elapsed time: 140.147 msecs"
sorted #'test/isort "Elapsed time: 23.097 msecs"
first  #'test/isort "Elapsed time: 110.453 msecs"

all    #'test/tsort "Elapsed time: 310.026 msecs"
sorted #'test/tsort "Elapsed time: 187.124 msecs"
first  #'test/tsort "Elapsed time: 72.164 msecs"
(ns lazy-sort)

(defn qsort [[head & tail]]
  (when head
    (lazy-cat (qsort (filter #(< % head) tail))
              [head]
              (qsort (remove #(< % head) tail)))))

(defn merge*
  [[f1 & r1 :as l1] [f2 & r2 :as l2]]
  (cond
    (nil? f1) l2
    (nil? f2) l1
    (<= f1 f2) (lazy-seq (cons f1 (merge* r1 l2)))
    (> f1 f2) (lazy-seq (cons f2 (merge* l1 r2)))))

(defn msort [s]
  (if (next s)
    (let [[left right] (split-at (/ (count s) 2) s)]
      (merge* (msort left) (msort right)))
    s))

(defn hsort [s]
  (let [heap (java.util.concurrent.PriorityBlockingQueue. s)]
    (repeatedly (count s) #(.take heap))))

(defn insert [^java.util.LinkedList s x]
  (let [i (.listIterator s (.size s))]
    (while (and (.hasPrevious i) (> (.previous i) x)))
    (.add i x)
    s))

(defn isort [s] ; not lazy
  (seq (reduce insert (java.util.LinkedList.) s)))

(defn treeduce [f s]
  (loop [s (partition-all 2 s)]
    (let [s (map (fn [[x y]] (f x y)) s)]
      (if (< 1 (count s))
        (recur (partition-all 2 s))
        (first s)))))

(defn tsort [s] ; naive
  (treeduce merge* (map isort (partition-all 128 s))))

(defn speed []
  (doseq [s [#'sort #'qsort #'msort #'hsort #'isort #'tsort]
          :let [sort (var-get s)]]
    (println)
    (print "all   " s "")
    (time (dotimes [_ 100] (dorun (sort (shuffle (range 1000))))))
    (print "sorted" s "")
    (time (dotimes [_ 100] (dorun (sort (range 1000)))))
    (print "first " s "")
    (time (dotimes [_ 100] (first (sort (shuffle (range 1000))))))))

Published on