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) ==...