「数字混じり文字列ソートをClojureで」を改良してみた

Clojure

一昨日のコードがどうも納得いかなかったので改良しました。
元ネタはどう書く？.org 「数字混じり文字列ソート」

;; clojure 1.2.1
(use 'clojure.contrib.str-utils
     'clojure.contrib.core)

(defn apply-flip [f a b]
  (f b a))

(defn parse [s]
  (->> (re-partition #"\d+" s)
       (apply-flip concat [nil])
       (partition 2)
       (mapcat (juxt first #(-?> % second Integer/parseInt)))))

(defn mixed-compare [parse a b]
  (let [pa (parse a)
        pb (parse b)
        len (max (count pa) (count pb))]
    (compare (->> (concat pa (repeat nil)) (take len) vec)
             (->> (concat pb (repeat nil)) (take len) vec))))

(defn mixed-sort [xs]
  (sort (partial mixed-compare parse) xs))

parse で出題リストの中の文字列を (文字列 数値 文字列 数値 ...) というシーケンスに変換。mixed-compare は sort に渡せる comparator です。
ただし mixed-compare はそのまま sort に渡すのではなく、第一引数に parse 関数を部分適用する必要があります。この parse 関数を使って文字列 a b を「文字列-数値 シーケンス」にしてから２つのコレクションを compare します。
なお compare する前に。

  • シーケンスの長さをそろえる
  • シーケンスをベクタに変換する

という処理も行っています。
長さをそろえる処理を parse の前ではなく後に行うことで、前回あった無駄を最小限に抑えることができている（はず）です。
また、Lazy Seq を compare しようとすると。

java.lang.ClassCastException: clojure.lang.LazySeq cannot be cast to java.lang.Comparable
  [Thrown class java.lang.RuntimeException]

と怒られるので Persistent なコレクション（今回はベクタ）にしてます。

memoize

何故 mixed-compare を素直に compare と同じシグネチャにせず高階関数にしたかというと、これがやりたかったから。memoize です。sort は何度も mixed-compare を呼ぶので parse を memoize できれば高速化が望めます。

(defn memoized-mixed-sort [xs]
  (sort (partial mixed-compare (memoize parse)) xs))

time で測ったら、大体半分くらいの処理時間になってました。