让我们假设我们有一个列表xs(可能是一个非常大的列表),我们想要检查它的所有元素是否相同.
我想出了各种各样的想法:
检查所有元素tail xs是否等于head xs:
allTheSame :: (Eq a) => [a] -> Bool
allTheSame xs = and $ map (== head xs) (tail xs)
检查length xs是否等于通过从xs它们等于时获取元素而获得的列表的长度head xs
allTheSame' :: (Eq a) => [a] -> Bool
allTheSame' xs = (length xs) == (length $ takeWhile (== head xs) xs)
递归溶液:allTheSame返回True如果前两个元素xs是相等的,并allTheSame返回True上的其余部分xs
allTheSame'' :: (Eq a) => [a] -> Bool
allTheSame'' xs
| n == 0 = False
| n == 1 = True
| n == 2 = xs !! 0 == xs !! 1
| otherwise = (xs !! 0 == xs !! 1) && (allTheSame'' $ snd $ splitAt 2 xs)
where n = length xs
分而治之:
allTheSame''' :: (Eq a) => [a] -> Bool
allTheSame''' xs
| n == 0 = False
| n == 1 = True
| n == 2 = xs !! 0 == xs !! 1
| n == 3 = xs !! 0 == xs !! 1 && xs !! 1 == xs !! 2
| otherwise = allTheSame''' (fst split) && allTheSame''' (snd split)
where n = length xs
split = splitAt (n `div` 2) xs
我在写这个问题的时候就想到了这个:
allTheSame'''' :: (Eq a) => [a] -> Bool
allTheSame'''' xs = all (== head xs) (tail xs)
我认为解决方案0不是非常有效,至少在内存方面,因为map在应用and其元素之前将构造另一个列表.我对吗？
解决方案1仍然不是非常有效,至少在内存方面,因为takeWhile将再次构建一个额外的列表.我对吗？
解决方案2是尾递归(对吗？),它应该非常有效,因为它会在False时False立即返回(xs !! 0 == xs !! 1).我对吗？
解决方案3应该是最好的,因为它的复杂性应该是O(log n)
解决方案4对我来说看起来很Haskellish(是吗？),但它可能与解决方案0相同,因为all p = and . map p(来自Prelude.hs).我对吗？
还有其他更好的写作方式allTheSame吗？现在,我希望有人会回答这个问题,告诉我有一个内置函数可以做到这一点:我用hoogle搜索过,但我还没有找到它.无论如何,既然我正在学习Haskell,我相信这对我来说是一个很好的练习:)
欢迎任何其他评论.谢谢!
luq*_*qui 28
gatoatigrado的回答为衡量各种解决方案的性能提供了一些很好的建议.这是一个更具象征性的答案.
我认为解决方案0(或者,完全相同,解决方案4)将是最快的.请记住,Haskell是惰性的,因此map在and应用之前不必构造整个列表.建立直觉的好方法是玩无限.例如:
ghci> and $ map (< 1000) [1..]
False
这会询问是否所有数字都小于1,000.如果map构建了之前的整个列表and,那么这个问题永远无法回答.即使你给列表一个非常大的右端点(即Haskell没有做任何"魔术",取决于列表是否是无限的),表达式仍然会快速回答.
为了开始我的例子,让我们使用这些定义:
and [] = True
and (x:xs) = x && and xs
map f [] = []
map f (x:xs) = f x : map f xs
True && x = x
False && x = False
这是评估顺序allTheSame [7,7,7,7,8,7,7,7].写下来会有额外的分享,这太痛苦了.我还会head比简洁性更早地评估表达式(无论如何它都会被评估,所以它几乎没有不同).
allTheSame [7,7,7,7,8,7,7,7]
allTheSame (7:7:7:7:8:7:7:7:[])
and $ map (== head (7:7:7:7:8:7:7:7:[])) (tail (7:7:7:7:8:7:7:7:[]))
and $ map (== 7) (tail (7:7:7:7:8:7:7:7:[]))
and $ map (== 7) (7:7:7:8:7:7:7:[])
and $ (== 7) 7 : map (== 7) (7:7:8:7:7:7:[])
(== 7) 7 && and (map (== 7) (7:7:8:7:7:7:[]))
True && and (map (== 7) (7:7:8:7:7:7:[]))
and (map (== 7) (7:7:8:7:7:7:[]))
(== 7) 7 && and (map (== 7) (7:8:7:7:7:[]))
True && and (map (== 7) (7:8:7:7:7:[]))
and (map (== 7) (7:8:7:7:7:[]))
(== 7) 7 && and (map (== 7) (8:7:7:7:[]))
True && and (map (== 7) (8:7:7:7:[]))
and (map (== 7) (8:7:7:7:[]))
(== 7) 8 && and (map (== 7) (7:7:7:[]))
False && and (map (== 7) (7:7:7:[]))
False
看看我们甚至不必查看过去的3 7？这是一个懒惰的评估,使列表更像循环.所有其他解决方案都使用昂贵的功能length(必须一直走到列表末尾才能给出答案),因此它们的效率会降低,而且它们也无法在无限列表上运行.在无限列表上工作并且有效率通常在Haskell中一起使用.
Joh*_*n L 21
首先,我认为您不想使用列表.很多算法依赖于计算长度,这很糟糕.您可能需要考虑向量包,与列表的O(n)相比,它将为您提供O(1)长度.向量也具有更高的内存效率,特别是如果您可以使用Unboxed或Storable变体.
话虽这么说,您确实需要考虑代码中的遍历和使用模式.Haskell的列表非常有效,如果它们可以按需生成并消耗一次.这意味着您不应该继续引用列表.像这样的东西:
average xs = sum xs / length xs
要求整个列表保留在内存中(通过其中一个sum或length两个),直到两个遍历都完成.如果您可以一步完成列表遍历,那么效率会更高.
当然,您可能还需要保留列表,例如检查所有元素是否相等,如果不相同,请对数据执行其他操作.在这种情况下,使用任何大小的列表,您可能会使用更紧凑的数据结构(例如矢量).
现在,这是他们的方式,这里看看这些功能.在我展示核心的地方,它是由生成的ghc-7.0.3 -O -ddump-simpl.此外,在使用-O0编译时,不要打扰判断Haskell代码性能.使用您实际用于生产代码的标志进行编译,通常至少为-O,也可能是其他选项.
解决方案0
allTheSame :: (Eq a) => [a] -> Bool
allTheSame xs = and $ map (== head xs) (tail xs)
GHC产生这个核心:
Test.allTheSame
:: forall a_abG. GHC.Classes.Eq a_abG => [a_abG] -> GHC.Bool.Bool
[GblId,
Arity=2,
Str=DmdType LS,
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
ConLike=True, Cheap=True, Expandable=True,
Guidance=IF_ARGS [3 3] 16 0}]
Test.allTheSame =
\ (@ a_awM)
($dEq_awN :: GHC.Classes.Eq a_awM)
(xs_abH :: [a_awM]) ->
case xs_abH of _ {
[] ->
GHC.List.tail1
`cast` (CoUnsafe (forall a1_axH. [a1_axH]) GHC.Bool.Bool
:: (forall a1_axH. [a1_axH]) ~ GHC.Bool.Bool);
: ds1_axJ xs1_axK ->
letrec {
go_sDv [Occ=LoopBreaker] :: [a_awM] -> GHC.Bool.Bool
[LclId, Arity=1, Str=DmdType S]
go_sDv =
\ (ds_azk :: [a_awM]) ->
case ds_azk of _ {
[] -> GHC.Bool.True;
: y_azp ys_azq ->
case GHC.Classes.== @ a_awM $dEq_awN y_azp ds1_axJ of _ {
GHC.Bool.False -> GHC.Bool.False; GHC.Bool.True -> go_sDv ys_azq
}
}; } in
go_sDv xs1_axK
}
实际上,这看起来很不错.它会产生一个带有空列表的错误,但这很容易修复.这是case xs_abH of _ { [] ->.在GHC执行worker/wrapper转换之后,递归worker函数就是letrec { go_sDv绑定.工人检查其论点.如果[],它已到达列表的末尾并返回True.否则,它会将剩余的头部与第一个元素进行比较,并返回False或检查列表的其余部分.
其他三个功能.
map被完全融合的路程,不分配的临时列表.Cheap=True声明.这意味着GHC认为功能"便宜",因此是内联的候选者.在调用站点,如果可以确定具体的参数类型,GHC可能会内联allTheSame并产生一个非常紧密的内循环,完全绕过Eq字典查找.判决:非常有力的竞争者.
解决方案1
allTheSame' :: (Eq a) => [a] -> Bool
allTheSame' xs = (length xs) == (length $ takeWhile (== head xs) xs)
即使不看核心我也知道这不会那么好.该名单是由经过一次以上,先length xs再经length $ takeWhile.您不仅有多次遍历的额外开销,这意味着列表必须在第一次遍历后保留在内存中,并且不能进行GC.对于一个大清单,这是一个严重的问题.
Test.allTheSame'
:: forall a_abF. GHC.Classes.Eq a_abF => [a_abF] -> GHC.Bool.Bool
[GblId,
Arity=2,
Str=DmdType LS,
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
ConLike=True, Cheap=True, Expandable=True,
Guidance=IF_ARGS [3 3] 20 0}]
Test.allTheSame' =
\ (@ a_awF)
($dEq_awG :: GHC.Classes.Eq a_awF)
(xs_abI :: [a_awF]) ->
case GHC.List.$wlen @ a_awF xs_abI 0 of ww_aC6 { __DEFAULT ->
case GHC.List.$wlen
@ a_awF
(GHC.List.takeWhile
@ a_awF
(let {
ds_sDq :: a_awF
[LclId, Str=DmdType]
ds_sDq =
case xs_abI of _ {
[] -> GHC.List.badHead @ a_awF; : x_axk ds1_axl -> x_axk
} } in
\ (ds1_dxa :: a_awF) ->
GHC.Classes.== @ a_awF $dEq_awG ds1_dxa ds_sDq)
xs_abI)
0
of ww1_XCn { __DEFAULT ->
GHC.Prim.==# ww_aC6 ww1_XCn
}
}
看看核心并没有说明这一点.但请注意以下几行:
case GHC.List.$wlen @ a_awF xs_abI 0 of ww_aC6 { __DEFAULT ->
case GHC.List.$wlen
这是列表遍历发生的地方.第一个获取外部列表的长度并将其绑定到ww_aC6.第二个获取内部列表的长度,但绑定不会发生,直到接近底部,at
of ww1_XCn { __DEFAULT ->
GHC.Prim.==# ww_aC6 ww1_XCn
长度(均为Ints)可以拆箱并通过primop进行比较,但这是在引入的开销之后的一个小安慰.
判决结果:不好.
解决方案2
allTheSame'' :: (Eq a) => [a] -> Bool
allTheSame'' xs
| n == 0 = False
| n == 1 = True
| n == 2 = xs !! 0 == xs !! 1
| otherwise = (xs !! 0 == xs !! 1) && (allTheSame'' $ snd $ splitAt 2 xs)
where n = length xs
这与解决方案1具有相同的问题.列表被遍历多次,并且不能进行GC.但这里更糟糕,因为现在计算每个子列表的长度.我希望这在任何重要大小的列表上都具有最差的性能.另外,当你期望列表很大时,为什么你特别为1和2元素的套管列表呢？
判决:甚至不要考虑它.
解决方案3
allTheSame''' :: (Eq a) => [a] -> Bool
allTheSame''' xs
| n == 0 = False
| n == 1 = True
| n == 2 = xs !! 0 == xs !! 1
| n == 3 = xs !! 0 == xs !! 1 && xs !! 1 == xs !! 2
| otherwise = allTheSame''' (fst split) && allTheSame''' (snd split)
where n = length xs
split = splitAt (n `div` 2) xs
这与解决方案2具有相同的问题.即,列表被遍历多次length.我不确定分而治之的方法对于这个问题是一个很好的选择,它可能比简单的扫描花费更长的时间.这取决于数据,值得测试.
判决:可能,如果你使用了不同的数据结构.
解决方案4
allTheSame'''' :: (Eq a) => [a] -> Bool
allTheSame'''' xs = all (== head xs) (tail xs)
这基本上是我的第一个念头.让我们再次检查核心.
Test.allTheSame''''
:: forall a_abC. GHC.Classes.Eq a_abC => [a_abC] -> GHC.Bool.Bool
[GblId,
Arity=2,
Str=DmdType LS,
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
ConLike=True, Cheap=True, Expandable=True,
Guidance=IF_ARGS [3 3] 10 0}]
Test.allTheSame'''' =
\ (@ a_am5)
($dEq_am6 :: GHC.Classes.Eq a_am5)
(xs_alK :: [a_am5]) ->
case xs_alK of _ {
[] ->
GHC.List.tail1
`cast` (CoUnsafe (forall a1_axH. [a1_axH]) GHC.Bool.Bool
:: (forall a1_axH. [a1_axH]) ~ GHC.Bool.Bool);
: ds1_axJ xs1_axK ->
GHC.List.all
@ a_am5
(\ (ds_dwU :: a_am5) ->
GHC.Classes.== @ a_am5 $dEq_am6 ds_dwU ds1_axJ)
xs1_axK
}
好的,还不错.与解决方案1一样,这将在空列表上出错.列表遍历隐藏在其中GHC.List.all,但它可能会在呼叫站点扩展为良好的代码.
判决:另一个强有力的竞争者.
因此,在所有这些与列表之间,我希望解决方案0和4是唯一值得使用的,并且它们几乎相同.在某些情况下我可能会考虑选项3.
编辑:在这两种情况下,空列表中的错误可以简单地修复,如@ augustss的答案.
下一步是用标准进行一些时间分析.
tok*_*and 12
使用连续对的解决方案:
allTheSame xs = and $ zipWith (==) xs (tail xs)
Q1 - 是的,我认为你的简单解决方案很好,没有内存泄漏.Q4 - 解决方案3不是log(n),通过非常简单的参数,您需要查看所有列表元素以确定它们是否相同,并且查看1个元素需要1个时间步.Q5 - 是的.Q6,见下文.
解决这个问题的方法是输入并运行它
main = do
print $ allTheSame (replicate 100000000 1)
然后运行ghc -O3 -optc-O3 --make Main.hs && time ./Main.我最喜欢上一个解决方案(你也可以使用模式匹配来清理它),
allTheSame (x:xs) = all (==x) xs
打开ghci并在这些东西上运行":step fcn".它将教你很多关于懒惰评估正在扩展的内容.通常,当您匹配构造函数时,例如"x:xs",这是常量时间.当你调用"length"时,Haskell需要计算列表中的所有元素(尽管它们的值仍然是"待计算"),因此解决方案1和2都很糟糕.
对不起,如果我之前的回答有点浅薄.似乎手动扩展的东西确实有点帮助(虽然与其他选项相比,这是一个微不足道的改进),
{-# LANGUAGE BangPatterns #-}
allTheSame [] = True
allTheSame ((!x):xs) = go x xs where
go !x [] = True
go !x (!y:ys) = (x == y) && (go x ys)
似乎ghc已经专门化了这个函数,但你也可以查看specialize pragma,以防它对你的代码[ link ] 不起作用.
这是另一个版本（不需要遍历整个列表，以防出现不匹配的情况）：
allTheSame [] = True
allTheSame (x:xs) = isNothing $ find (x /= ) xs
这在语法上可能不正确，但我希望你明白了。
| 归档时间： |
|
| 查看次数： |
21280 次 |
| 最近记录： |