Haskell：用于生成组合的技术比较 [英] Haskell: comparison of techniques for generating combinations
问题描述
我之前正在做一些 99 Haskell问题，我认为练习27（写一个函数来枚举可能的组合）很有趣，因为它是一个简单的概念，它适用于多种实现。
我对相对效率感到好奇，所以我决定运行一些不同的实现 - 结果在下表中。 （仅供参考：在VirtualBox上运行的LXDE（Ubuntu 14.04）中的Emacs bash ansi-term; Thinkpad X220; 8GB内存，i5 64bit 2.4ghz。）
TL; DR：
$ b $（i）为什么组合生成技术＃7和＃8 （ii）同样，
字节列中的数字是什么实际上是代表什么？ （i）这很奇怪，因为函数＃7通过过滤powerset（它比组合列表）;我怀疑这是懒惰的工作，也就是说，这是最有效地利用我们只要求列表长度而不是列表本身的事实的功能。 （另外，它的'内存使用率'比其他函数低，但是，我不确定显示的是与内存相关的统计数据。）
关于函数＃8：对Bergi的那个可笑的快速实现的感谢，并且感谢user5402建议添加。 （ii）字节的数字仍然会绕过这个速度的差异。列运行：set + s 命令后由GHCi报告;他们显然不代表最大内存使用量，因为我只有25GB内存+免费HD空间。）？
代码：
import Data.List
- 生成组合的算法
- 计算以下所需的时间：长度$ 13abcdefghijklmnopqrstuvwxyz
- （90.14秒，33598933424字节）
combDC1 ::（等式a ）=> Int - > [a] - > [[a]]
combDC1 n xs = filter（/ = []）$ combHelper n n xs []
combHelper :: Int - > Int - > [a] - > [a] - > [[a]]
combHelper n _ []选择=如果选择了长度== n
然后[选择]
else [[]]
combHelper ni保持选中状态
|长度选择== n = [选择]
| n - 长度选择>剩余长度= [[]]
|否则= combHelper n（i-1）（尾部剩余）（（头部剩余）：选择）++
combHelper ni（尾部剩余）选择
- （167.63秒，62756587760字节）
combSoln1 :: Int - > [a] - > [（[a]，[a]）]
combSoln1 0 xs = [（[]，xs）]
combSoln1 n [] = []
combSoln1 n（x：xs）= ts ++ ds
其中
ts = [（x：ys，zs）| （ys，zs）< - combSoln1（n-1）xs]
ds = [（ys，x：zs）| （ys，zs）< - combSoln1 n xs]
- （71.40 secs，30480652480字节）
combSoln2 :: Int - > [a] - > [[a]]
combSoln2 0 _ = [[]]
combSoln2 n xs = [y：ys | y：xs'< - tails xs
，ys < - combSoln2（n-1）xs']
- （83.75秒，46168207528字节）
combSoln3： ：Int - > [a] - > [[a]]
combSoln3 0 _ = return []
combSoln3 n xs = do
y：xs'< - tails xs
ys < - combSoln3（n-1 ）xs'
return（y：ys）
- （92.34 secs，40541644232 bytes）
combSoln4 :: Int - > [a] - > [[a]]
combSoln4 0 _ = [[]]
combSoln4 n xs = [xs !!我：x | i < - [0 ...（length xs）-1]
，x < - combSoln4（n-1）（drop（i + 1）xs）]
- （90.63秒，33058536696字节）
combSoln5 :: Int - > [a] - > [[a]]
combSoln5 _ [] = [[]]
combSoln5 0 _ = [[]]
combSoln5 k（x：xs）= x_start ++其他
其中x_start = [x：rest |如果k <=长度xs则combSoln5 k xs else []
- （61.74秒，其余为< - combSoln5（k-1） 33053297832字节）
combSoln6 :: Int - > [a] - > [[a]]
combSoln6 0 _ = [[]]
combSoln6 _ [] = []
combSoln6 n（x：xs）=（map（x :)（combSoln6（n -1）xs））++（combSoln6 n xs）
- （8.41秒，10785499208字节）
combSoln7 k ns = filter（（k ==）。长度）（子序列ns）
- （3.15秒，2889815872字节）
subsequencesOfSize :: Int - > [a] - > [[a]]
subsequencesOfSize n xs = let l = length xs
in if n> l then [] else subsequencesBySize xs !! （ln）
其中
zipWith（++）（[b]）中的子序列大小（x：xs）= let next = subsequencesBySize xs
子序列比例[] = [[[]]]
]：next）（map（map（x :)）next ++ [[]]）
您还应该测试在此SO中找到的算法答案：
$ b $ p> subsequencesOfSize :: Int - > [a] - > [[a]]
subsequencesOfSize n xs = let l = length xs
in if n> l then [] else subsequencesBySize xs !! （ln）
其中
zipWith（++）（[b]）中的子序列大小（x：xs）= let next = subsequencesBySize xs
子序列比例[] = [[[]]]
]：next）（map（map（x :)）next ++ [[]]）
在我的机器上，我从ghci获得以下时间和内存使用情况：
ghci>长度$ combSoln7 13abcdefghijklmnopqrstuvwxyz
10400600
（13.42秒，10783921008字节）
ghci>长度$ subsequencesOfSize 13abcdefghijklmnopqrstuvwxyz
10400600
（6.52秒，2889807480字节）
I was doing a few of the 99 Haskell Problems earlier and I thought that exercise 27 ("write a function to enumerate the possible combinations") was interesting as it's a simple concept and it lends itself to multiple implementations.
I was curious about relative efficiency so I decided to run a couple of different implementations - results are in the table below. (For reference: Emacs bash ansi-term in LXDE (Ubuntu 14.04) running on VirtualBox; Thinkpad X220; 8gb RAM, i5 64bit 2.4ghz.)
TL;DR:
(i) Why are combination-generating techniques #7 and #8 (from the table below; code included at bottom of post) so much faster than the rest?
(ii) Also, what do the figures in the Bytes column actually represent?
(i) It's odd because function #7 works by filtering the powerset (which is waaaay larger than the combinations list); I suspect this is laziness at work, i.e., that this is the function which is most effectively exploiting the fact that we've only asked for the length of the list and not the list itself. (Also, its 'memory usage' is lower than that of the other functions, but, then again, I'm not sure exactly what memory-related stat is being shown.)
Regarding function #8: kudos to Bergi for that ridiculously fast implementation and thanks to user5402 for suggesting the addition. Still trying to wrap my ahead around the speed difference of this one.
(ii) The figures in the Bytes column are reported by GHCi after running the :set +s command; they clearly don't represent max memory usage as I only have ~25gb of RAM + free HD space.)?
Code:
import Data.List
--algorithms to generate combinations
--time required to compute the following: length $ 13 "abcdefghijklmnopqrstuvwxyz"
--(90.14 secs, 33598933424 bytes)
combDC1 :: (Eq a) => Int -> [a] -> [[a]]
combDC1 n xs = filter (/= []) $ combHelper n n xs []
combHelper :: Int -> Int -> [a] -> [a] -> [[a]]
combHelper n _ [] chosen = if length chosen == n
then [chosen]
else [[]]
combHelper n i remaining chosen
| length chosen == n = [chosen]
| n - length chosen > length remaining = [[]]
| otherwise = combHelper n (i-1) (tail remaining) ((head remaining):chosen) ++
combHelper n i (tail remaining) chosen
--(167.63 secs, 62756587760 bytes)
combSoln1 :: Int -> [a] -> [([a],[a])]
combSoln1 0 xs = [([],xs)]
combSoln1 n [] = []
combSoln1 n (x:xs) = ts ++ ds
where
ts = [ (x:ys,zs) | (ys,zs) <- combSoln1 (n-1) xs ]
ds = [ (ys,x:zs) | (ys,zs) <- combSoln1 n xs ]
--(71.40 secs, 30480652480 bytes)
combSoln2 :: Int -> [a] -> [[a]]
combSoln2 0 _ = [ [] ]
combSoln2 n xs = [ y:ys | y:xs' <- tails xs
, ys <- combSoln2 (n-1) xs']
--(83.75 secs, 46168207528 bytes)
combSoln3 :: Int -> [a] -> [[a]]
combSoln3 0 _ = return []
combSoln3 n xs = do
y:xs' <- tails xs
ys <- combSoln3 (n-1) xs'
return (y:ys)
--(92.34 secs, 40541644232 bytes)
combSoln4 :: Int -> [a] -> [[a]]
combSoln4 0 _ = [[]]
combSoln4 n xs = [ xs !! i : x | i <- [0..(length xs)-1]
, x <- combSoln4 (n-1) (drop (i+1) xs) ]
--(90.63 secs, 33058536696 bytes)
combSoln5 :: Int -> [a] -> [[a]]
combSoln5 _ [] = [[]]
combSoln5 0 _ = [[]]
combSoln5 k (x:xs) = x_start ++ others
where x_start = [ x : rest | rest <- combSoln5 (k-1) xs ]
others = if k <= length xs then combSoln5 k xs else []
--(61.74 secs, 33053297832 bytes)
combSoln6 :: Int -> [a] -> [[a]]
combSoln6 0 _ = [[]]
combSoln6 _ [] = []
combSoln6 n (x:xs) = (map (x:) (combSoln6 (n-1) xs)) ++ (combSoln6 n xs)
--(8.41 secs, 10785499208 bytes)
combSoln7 k ns = filter ((k==).length) (subsequences ns)
--(3.15 secs, 2889815872 bytes)
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
in if n>l then [] else subsequencesBySize xs !! (l-n)
where
subsequencesBySize [] = [[[]]]
subsequencesBySize (x:xs) = let next = subsequencesBySize xs
in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])
You should also test the algorithm found in this SO answer:
subsequences of length n from list performance
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
in if n>l then [] else subsequencesBySize xs !! (l-n)
where
subsequencesBySize [] = [[[]]]
subsequencesBySize (x:xs) = let next = subsequencesBySize xs
in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])
On my machine I get the following timing and memory usage from ghci:
ghci> length $ combSoln7 13 "abcdefghijklmnopqrstuvwxyz"
10400600
(13.42 secs, 10783921008 bytes)
ghci> length $ subsequencesOfSize 13 "abcdefghijklmnopqrstuvwxyz"
10400600
(6.52 secs, 2889807480 bytes)
这篇关于Haskell：用于生成组合的技术比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
