很多这些功能都可能在标准库
确实。如果您import Data.List，这使得sort可用，maximum和minimum可从Prelude获得。从Data.List开始的sort比准快速排序更有效率，特别是因为这里的列表中有很多排序的块。
descending :: (Ord a) => [a] -> Bool
descending [] = True
descending (h:[]) = True
descending (h:t)
| h > (max_list t) = descending t
| otherwise = False
是低效 - O(n²) - 因为它遍历每个步骤中的整个左尾，虽然如果列表按降序，最大尾必须是其头部。但是这里有一个很好的结果。它阻止了thunk的建立，因为succ_list的第三个等式的第一个后卫迫使列表被完全评估。但是，这可以通过明确强制一次来更有效地完成。
descending (h:[email protected](ht:_)) = h > ht && descending t
会使其成线性。那
在注意到我的程序需要一段时间运行后，我写了一个等效的C程序进行比较。
这将是不寻常的。很少有人会使用C语言中的链表来实现懒惰评估，这将是一件非常有意义的事情。
编写一个相当于程序在C中将是非常unidiomatic。在C中，实现该算法的自然方式将使用数组和就地变异。这在这里自动更有效率。
我的猜测是，Haskell的延迟评估会导致apply_times函数在实际开始评估结果之前在内存中构建一个巨大的列表。
不完全是，它是建立一个巨大的thunk，
apply_times 999999 succ_list [0,1,2,3,4,5,6,7,8,9]
~> apply_times 999998 succ_list (succ_list [0 .. 9])
~> apply_times 999997 succ_list (succ_list (succ_list [0 .. 9]))
~> apply_times 999996 succ_list (succ_list (succ_list (succ_list [0 .. 9])))
...
succ_list (succ_list (succ_list ... (succ_list [0 .. 9])...))
，并在此形实转换已建成之后，必须进行评估。为了评估最外层的调用，必须对下一层进行评估，以找出最外层调用中哪些模式匹配。因此，最外层的呼叫被压入堆栈，并且下一个呼叫开始被评估。为此，必须确定哪种模式匹配，因此需要第三个调用结果的一部分。因此第二个电话被压入堆栈......。最后，你在堆栈上有999998个调用，并开始评估最内层的调用。然后，在每次调用和下一次外部调用之间（至少，依赖关系可能会进一步扩展），在堆栈中冒出并弹出调用时，您会发挥一点乒乓功能。
是有可能被用来减少内存消耗
是，迫使中间的列表进行评估，他们成为apply_times前面的参数任何好的技巧。在这里你需要全面的评估，所以香草seq不够好
import Control.DeepSeq
apply_times' :: (NFData a, Integral n) => n -> (a -> a) -> a -> a
apply_times' 0 _ x = x
apply_times' k f x = apply_times' (k-1) f $!! f x
阻止的thunk的积聚，因此你不需要比在succ_list构建短短列出更多的内存，柜台。
如何最大限度地减少复制和垃圾收集，因为列表反复创建，而C实现可以完成所有工作。
对，这仍然会分配（和垃圾收集）很多。现在，GHC是分配和垃圾收集短命的数据非常好（在我的盒子，它可以很容易地在每MUT 2GB的速度分配第二而不慢），但尽管如此，不分配所有这些列表会快点。
所以，如果你想推它，使用就地突变。上
STUArray s Int Int
或拆箱可变矢量（我更喜欢由array包中提供的接口，但最喜欢的vector工作界面;在性能方面，vector包有很多内置的优化技术的你，如果你使用array包，你必须自己编写快速代码，但编写良好的代码在所有实际应用中都是相同的）。
我已经做了一些测试了。我没有测试原始的懒惰apply_times，只有一个deepseq每个应用程序f，并已将所有涉及的实体的类型固定为Int。
随着该设置，与Data:list.sort替换sort_list减少的运行时间1.82秒〜1.65（但增加分配的字节数）。没有什么区别，但是这些清单不足以让准快速排序的糟糕情况真正发生。
那么最大的区别来自于不断变化的descending提议，带来的时间缩短至0.48秒的Alloc率每MUT 2170566037个字节第二，0.01秒GC时间（再利用sort_list代替sort带来的时间长达0.58秒）。
用更简单的方法替换列表结尾段的排序reverse - 该算法确保在排序时按降序排序 - 将时间降至0.43秒。
要使用的算法拆箱可变数组的一个相当直接翻译，在0.15秒
{-# LANGUAGE BangPatterns #-}
module Main (main) where
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Control.Monad (when, replicateM_)
sortPart :: STUArray s Int Int -> Int -> Int -> ST s()
sortPart a lo hi
| lo < hi = do
let lscan !p h i
| i < h = do
v <- unsafeRead a i
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan !p l i
| l < i = do
v <- unsafeRead a i
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
v <- unsafeRead a i
unsafeRead a j >>= unsafeWrite a i
unsafeWrite a j v
sloop !p l h
| l < h = do
l1 <- lscan p h l
h1 <- rscan p l1 h
if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
| otherwise = return l
piv <- unsafeRead a hi
i <- sloop piv lo hi
swap i hi
sortPart a lo (i-1)
sortPart a (i+1) hi
| otherwise = return()
descending :: STUArray s Int Int -> Int -> Int -> ST s Bool
descending arr lo hi
| lo < hi = do
let check i !v
| hi < i = return True
| otherwise = do
w <- unsafeRead arr i
if w < v
then check (i+1) w
else return False
x <- unsafeRead arr lo
check (lo+1) x
| otherwise = return True
findAndReplace :: STUArray s Int Int -> Int -> Int -> ST s()
findAndReplace arr lo hi
| lo < hi = do
x <- unsafeRead arr lo
let go !mi !mv i
| hi < i = when (lo < mi) $ unsafeWrite arr mi x >> unsafeWrite arr lo mv
| otherwise = do
w <- unsafeRead arr i
if x < w && w < mv
then go i w (i+1)
else go mi mv (i+1)
look i
| hi < i = return()
| otherwise = do
w <- unsafeRead arr i
if x < w
then go i w (i+1)
else look (i+1)
look (lo+1)
| otherwise = return()
succArr :: STUArray s Int Int -> Int -> Int -> ST s()
succArr arr lo hi
| lo < hi = do
end <- descending arr lo hi
if end
then return()
else do
needSwap <- descending arr (lo+1) hi
if needSwap
then do
findAndReplace arr lo hi
sortPart arr (lo+1) hi
else succArr arr (lo+1) hi
| otherwise = return()
solution :: [Int]
solution = runST $ do
arr <- newListArray (0,9) [0 .. 9]
replicateM_ 999999 $ succArr arr 0 9
getElems arr
main :: IO()
main = print solution
完成。用更简单的零件倒置代替分类可将其降至0.11。
将算法分解为小顶层函数，每个小任务执行一项任务使其更具可读性，但价格昂贵。需要在这些函数之间传递更多的参数，因此并不是所有的参数都可以传递到寄存器中，并且一些传递的参数（数组边界和元素数量）完全不会被使用，因此传递的是自重。使所有其他功能solution本地功能降低了整体的分配和一定程度上的运行时间（0.13秒排序，0.09倒车），因为现在需要传递只在必要的参数。
从给定的算法进一步偏差，并使其工作后到前，
module Main (main) where
import Data.Array.ST
import Data.Array.Base
import Data.Array.Unboxed
import Control.Monad.ST
import Control.Monad (when)
import Data.Bits
lexPerm :: Int -> Int -> [Int]
lexPerm idx num = elems (runSTUArray $ do
arr <- unsafeNewArray_ (0,num)
let fill i
| num < i = return()
| otherwise = unsafeWrite arr i i >> fill (i+1)
swap i j = do
x <- unsafeRead arr i
y <- unsafeRead arr j
unsafeWrite arr j x
unsafeWrite arr i y
flop i j
| i < j = do
swap i j
flop (i+1) (j-1)
| otherwise = return()
binsearch v a b = go a b
where
go i j
| i < j = do
let m = (i+j+1) `unsafeShiftR` 1
w <- unsafeRead arr m
if w < v
then go i (m-1)
else go m j
| otherwise = swap a i
upstep k j
| k < 1 = return()
| j == num-1 = unsafeRead arr num >>= flip (back k) (num-1)
| otherwise = nextP k (num-1)
back k v i
| i < 0 = return()
| otherwise = do
w <- unsafeRead arr i
if w < v
then nextP k i
else back k w (i-1)
nextP k up
| k < 1 || up < 0 = return()
| otherwise = do
v <- unsafeRead arr up
binsearch v up num
flop (up+1) num
upstep (k-1) up
fill 0
nextP (idx-1) (num-1)
return arr)
main :: IO()
main = print $ lexPerm 1000000 9
我们可以0.02秒内完成任务。
然而，在问题中暗指的聪明算法在更少的时间内用更少的代码解决了任务。
你用'-O2'编译？至于标准库，您是否知道Hoogle？ –
剖析你的代码并看到瓶颈 – Satvik
高效的Haskell编程不是关于技巧。这是关于对Haskell（和GHC）评估模型的理解。不同方法的表现特征通常很清楚。 –