[ML][练习] 生成排列

MMMIX

原帖由 flw 于 2008-11-17 09:22 发表

不要太在意语法糖，那些都是浮云，关键是思想。

对研究算法来说也许是这样，但对于编程语言本身来说，提供好的(也即易学易用的)语法是非常重要的。

MMMIX

原帖由 win_hate 于 2008-11-17 13:29 发表
haskell 那个我是这样测的(帮忙看看是否用错了命令)：


let x = permutation [1..10000]
take 1 (drop 10000 x)

这个可以直接用 (permutation [1..10000]) !! 10000

我测试了一下，用 -O2 编译后，这个在我的机器(P4 2.2G, 1G 内存)上大概 6.8 左右的样子就可以跑出来。现在用的是 GHC 6.8，改天试试 6.10 的表现。

(permutation [1..10000]) !! 100000 需要的时间大概是 68 秒。

MMMIX 那个空间占得厉害。

是有这个问题。Boxed variable 和 lazy evolution 这两个都会消耗内存。

[ 本帖最后由 MMMIX 于 2008-11-17 17:32 编辑 ]

MMMIX

BTW，我把 win_hate 用 ML 实现的 nextperm 翻译为 Haskell 测试了一下，超级快

不过我觉得主要问题在于才用 nextperm 这种方式，程序的执行流程相对简单，好优化；而我原来的实现其执行流程就复杂很多（至少是从实现方面考虑)。

MMMIX

原帖由 win_hate 于 2008-11-17 20:05 发表
把你的 Haskell 代码贴出来给我学习一下吧，

这是我把你的 ML 代码翻译为 Haskell 后的结果，你可以参考下：

1. 
   
2. module Permutation (nextPerm, nthPerm, allPerm) where
   
3. 
   
4. import Data.List (genericTake, genericIndex, sort)
   
5. 
   
6. nextPerm :: Ord a => [a] -> [a]
   
7. nextPerm (x:xs) = next [x] xs
   
8.   where
   
9.     next rs [] = rs
   
10.     next (r:rs) (y:ys) = if r <= y then next (y:r:rs) ys else swap (r:rs)
    
11.       where
    
12.         swap [x] = y:x:ys
    
13.         swap (x1:x2:xs) = if y < x2 then x1 : swap (x2:xs) else (y:x2:xs) ++ (x1:ys)
    
14. 
    
15. nthPerm :: Ord a => Integer -> [a] -> [a]
    
16. nthPerm n xs = (iterate nextPerm xs) `genericIndex` n
    
17. 
    
18. allPerm :: Ord a => [a] -> [[a]]
    
19. allPerm xs = genericTake (factorial n) $ iterate nextPerm xs'
    
20.   where
    
21.     n = length xs
    
22.     factorial n = product [1..n]
    
23.     xs' = sort xs
    

复制代码

MMMIX

原帖由 starfuck 于 2008-12-2 00:06 发表
我倒奇怪了，占空间的方式能撑到n!多大还不死的

应该是 n 多大。n 和 n! 的数量级是不能同日而语的。

MMMIX

原帖由 win_hate 于 2008-12-3 10:43 发表


如果在华丽地跳出来之前，能先看一看大家的讨论，就不会提这样的问题了。

MMMIX

讨论问题就好好讨论，嘴里不干不净的算是怎么回事？