Clojureでクイックソート

書いてみる。

まずはletの中にベタ書き。

(defn quick-sort [col]
  (if (>= 1 (count col))
    col
    (let [i      (rand-int (count col))
          pivot  (nth col i)
          heads  (take i col)
          tails  (drop (inc i) col)
          col2   (concat heads tails)
          lesser (filter #(< % pivot) col2)
          bigger (filter #(>= % pivot) col2)]
      (concat (quick-sort lesser) 
              [pivot] 
              (quick-sort bigger)))))

末尾再帰じゃないが、基本的に再帰の階層の数はlogNなので大丈夫なはず。Cとかでもquick sortの実装は大抵再帰を使うし。

なんとなく、「並べるものが何もなければcolをそのまま返す」と書いた方が少し意図がはっきりするように感じるので変更。

(defn quick-sort [col]
  (if (empty? (rest col))
    col
    (let [i      (rand-int (count col))
          pivot  (nth col i)
          heads  (take i col)
          tails  (drop (inc i) col)
          col2   (concat heads tails)
          lesser (filter #(< % pivot) col2)
          bigger (filter #(>= % pivot) col2)]
      (concat (quick-sort lesser) 
              [pivot] 
              (quick-sort bigger)))))

まあこれは好みの問題だろう。速度的には、私のPCだと後者の方が10%ほど早かったが正直そこは現段階ではpremature optimizationの部類だろう。

各local変数を別々に定義しているのは、それぞれの関係性がはっきりしない。destructuringを使って関連する変数は同時に束縛したい。

まずはpivot, heads, tails：

(defn quick-sort [col]
  (if (empty? (rest col))
    col
    (let [[heads [pivot & tails]]
           (split-at (rand-int (count col)) col)
           
          col2   (concat heads tails)
          lesser (filter #(< % pivot) col2)
          bigger (filter #(>= % pivot) col2)]
      (concat (quick-sort lesser) 
              [pivot] 
              (quick-sort bigger)))))

(split-at (rand-int (count col)) col)でcolを二つに分割。先頭のリストは空リストになり得るが、後ろの方は必ず一つは要素が含まれる。

後者のリストもさらにpivotとtailsにdestructuringする。pivotは必ず存在するが、tailsは空リストの可能性がある。

ちょっと長くなるので二行に分けざるを得ないのが玉に瑕だが、一つのsequenceを三つに分割しているのが明確に表現されていると思う。

lesserとbiggerもいっぺんに定義できる：

(defn quick-sort [col]
  (if (empty? (rest col))
    col
    (let [[heads [pivot & tails]]
           (split-at (rand-int (count col)) col)
           
          {lesser true, bigger false}
          (group-by #(< % pivot) (concat heads tails))]
      (concat (quick-sort lesser) 
              [pivot] 
              (quick-sort bigger)))))

group-by #(< % pivot) col)で{true pivot未満のリスト, false pivot以上のリスト}というhash-mapに変換。

destructuringでlesserとbiggerに変数束縛できる。

その一つの利点としては、(concat heads tails)を一回しか使わないので別に定義する必要がない。正直な話、ちゃんと意味のある変数名をつけようと思ったら「col-without-pivot」のような微妙なものになるので、できれば命名せずに済ましたかった。

そしてやはり、一つのリストをpivot未満・以上にわけて二つの変数に束縛している、というのがコードにちゃんと現れている（気がする）。

ちなみにパフォーマンス的にはdestructuringを使った方がいい。一番初めのコードに比べて大体25％ほど向上しているようだ。

追記：

しかし見直すと、最初のdestructuringが少し仕事をしすぎている気がする。

(defn quick-sort [col]
  (if (empty? (rest col))
    col
    (let [pivot-index
          (rand-int (count col))

          [heads [pivot & tails]]
          (split-at pivot-index col)
           
          {lesser true, bigger false}
          (group-by #(< % pivot) (concat heads tails))]
      (concat (quick-sort lesser) 
              [pivot] 
              (quick-sort bigger)))))

こんなもんでどうじゃろ。

追追記：

そうすると前言撤回してこう書いてもいい気がしてくる。

(defn quick-sort [col]
  (if (empty? (rest col))
    col
    (let [pivot-index
          (rand-int (count col))

          [heads [pivot & tails]]
          (split-at pivot-index col)
          
          col-ex-pivot
          (concat heads tails)
           
          {lesser true, bigger false}
          (group-by #(< % pivot) col-ex-pivot)]
      (concat (quick-sort lesser) 
              [pivot] 
              (quick-sort bigger)))))