Quciksort in Python: Functional vs Non-functional

最近學了 SML 和 Racket 後，開始對 Functional Programming 很有興趣。 不過在學的過程中，一直有一個疑問: immutable 不會讓程式變很慢嗎？(因為為做很多copy?) 所以想拿個例子分別寫 Functional / Non-functional 的寫法來比較看看速度。就選用最好寫的 Quicksort 好了，程式碼如下:

#!/usr/bin/env python

from timeit import timeit
from random import randint

def quicksort_impl(v, start, end):
    if start + 1 >= end:
        return

    pv = v[end - 1]
    partition = start

    for i in range(start, end):
        if v[i] < pv:
            v[partition], v[i] = v[i], v[partition]
            partition += 1

    v[partition], v[end - 1] = v[end - 1], v[partition]

    quicksort_impl(v, start, partition)
    quicksort_impl(v, partition + 1, end)

def quicksort(v):
    quicksort_impl(v, 0, len(v))
    return v

def quicksort_fp(v):
    if len(v) == 0:
        return []
    else:
        return quicksort_fp([x for x in v[:-1] if x < v[-1]]) + \
                [v[-1]] + \
                quicksort_fp([x for x in v[:-1] if x >= v[-1]])

def quicksort_fp_nl(v):
    if len(v) == 0:
        return []
    else:
        lt = []
        ge = []

        for x in v[:-1]:
            if x < v[-1]:
                lt.append(x)

        for x in v[:-1]:
            if x >= v[-1]:
                ge.append(x)

        return quicksort_fp_nl(lt) + [v[-1]] + quicksort_fp_nl(ge)

data = [randint(1, 5000) for x in range(1000)]

def main():
    print timeit('quicksort(data)', number=100,
                  setup='from __main__ import quicksort, data')
    print timeit('quicksort_fp(data)', number=100,
                  setup='from __main__ import quicksort_fp, data')
    print timeit('quicksort_fp_nl(data)', number=100,
                  setup='from __main__ import quicksort_fp_nl, data')
    print timeit('sorted(data)', number=100,
                 setup='from __main__ import data')

main()

出乎我意料之外的，結果如下:

% python sort.py
16.3728518486
11.5754849911
16.1211020947

補記：後來 Google 一下後發現原來有可能是因為 Python 的 list comprehension 是用 C optimized 的，所以用 FP 那樣的寫法才會比較快。可以參考這篇。 於是我加入了一個新的function quicksort_fp_nl，代表非list comprehension 寫法的 FP quicksort。果然 quicksort_fp_nl 和 quicksort 跑的時間就差不多了，所以這告訴我們在 Python 裡真的要盡量用 list compreshension。 

 內建的sort應該是用C寫的所以很快不用說。加上 python recursive 應該不像其他的Functional Programming語言會做 TCO (Tail call optimization)，所以 recursive 會比較慢可以想像的。不過可以看出，quicksort_fp 竟然跑得比 quicksort 還要快! 雖然在沒有做更多的 profiling 之下無法得知 bottle neck 在哪裡(我覺得有可能是 recursive 本身讓程式變很慢)，不過確可以得知在 Python 裡 QuickSort 用 FP 的寫法是比較快的。看那 quicksort_fp 優雅的寫法，以後根本不會想寫 quicksort 的寫法XD

接下來比較有興趣的語是 Scala， 因為上 BigData 的時候發現 Shark 竟然也是 Scala 寫的! 加上他同時支援 OOP 和 FP 這兩種 Paradigm 讓我感到非常有興趣! 所以接下來應該會好好的學一下。

學了 FP 後才發現其實很多以前在寫的東西就是 FP 了，比如說 make。make 本身的 functional call 就是 FP 的寫法！今天又剛好看到 GNU Make 4.0 release了，而且內建 GNU Guile 的支援。而 Guile 其實就是 Scheme (Racket 的前身) 的一個實作，主要用在 GNU 系列裡做為嵌入式的腳本語言。好奇下載來 compile 了一發，另外發現有趣的事情：早上看 GNU make 首頁上的 document 還是 3.8 版本的，結果晚上看就更新成 4.0 版的 doc 了！真奇妙XD