我是很新的哈斯克尔，和我有什么性能改进可以通过使用不纯（可变）数据结构进行了质询。我试图拼凑出我听到了一些不同的东西，所以请原谅我，如果我的术语是不完全正确的，或者有一些小错误。

I'm very new to Haskell, and I have a question about what performance improvements can be had by using impure (mutable) data structures. I'm trying to piece together a few different things I've heard, so please bear with me if my terminology is not entirely correct, or if there are some small errors.

为了使这个具体的，考虑到快速排序算法（从哈斯克尔维基拍摄）。

To make this concrete, consider the quicksort algorithm (taken from the Haskell wiki).

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

这是不是真正的快速排序。阿真快速排序算法是就地，这是没有的。这是非常低效的内存

This is not "true quicksort." A "true" quicksort algorithm is in-place, and this is not. This is very memory inefficient.

在另一方面，也可以使用载体在Haskell实现就地快速排序。一个例子在这个计算器的答案。

On the other hand, it is possible to use vectors in Haskell to implement an in-place quicksort. An example is given in this stackoverflow answer.

快多少是第二算法比第一？大O符号并不能帮助这里，因为性能的提升将是从更有效地使用内存，没有更好的算法（右？）。我累了构建一些测试情况下我自己，但我不得不跑难以得到的东西。

How much faster is the second algorithm than the first? Big O notation doesn't help here, because the performance improvement is going to be from using memory more efficiently, not having a better algorithm (right?). I tired to construct some test cases on my own, but I had difficult getting things running.

这是理想的答案会给一些想法是什么让就地哈斯克尔算法快理论上，而且在一些测试数据集运行时间的例子比较。

An ideal answer would give some idea of what makes the in-place Haskell algorithm faster theoretically, and an example comparison of running times on some test data set.

推荐答案

没有什么比一个测试没有好，对不对？其结果是这点毫不奇怪：随机整数的范围 [0 ..百万] ，

There's nothing better than a test, right? And the results are not unsurprising: for lists of random integers in range [0 .. 1000000],

list size: 200000         ghc              -O2     -fllvm  -fllvm-O2
────────                   ────────   ────────   ────────   ────────
Data.List.sort            0.878969s  0.883219s  0.878106s  0.888758s
Naïve.quicksort           0.711305s  0.870647s  0.845508s  0.919925s
UArray_IO.quicksort       9.317783s  1.919583s  9.390687s  1.945072s
Vector_Mutable.quicksort   1.48142s  0.823004s  1.526661s  0.806837s

下面， Data.List.sort 只是它是什么，Naïve.quicksort的算法，你引述， UArray_IO.quicksort 和 Vector_Mutable.quicksort 从您链接到的问题采取：的