有效地检查（大）列表中的所有元素是否相同 [英] efficiently checking that all the elements of a (big) list are the same

查看：103
本文介绍了有效地检查（大）列表中的所有元素是否相同的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

问题



让我们假设我们有一个列表 xs （可能是一个很大的列表），并且我们想检查它的所有元素是否相同。



我提出了各种想法：

解决方案0



检查 tail xs 中的所有元素等于 head xs ： 

  allTheSame ::（Eq a）=> [a]  - > Bool 
 allTheSame xs = and $ map（== head xs）（tail xs）



解决方案1检查长度xs 是否等于通过从<$ c获取元素获得的列表长度

$ c> xs ，而它们等于头部xs 

  allTheSame'::（等式a）=> [a]  - > Bool 
 allTheSame'xs =（length xs）==（length $ takeWhile（== head xs）xs）



解决方案2



递归解决方案： allTheSame 返回 code>如果 xs 的前两个元素相等并且 allTheSame 返回 True xs 

  allTheSame ''::（等式a）=> [a]  - > Bool 
 allTheSame''xs 
 | n == 0 = False 
 | n == 1 = True 
 | n == 2 = xs !! 0 == xs !! 1 
 |否则=（xs !! 0 == xs !! 1）&& （allTheSame''$ snd $ splitAt 2 xs）
其中n =长度xs



解决方案3



分而治之： 

  allTheSame''':: （等式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 
 |否则= allTheSame'''（fst split）&& allTheSame'''（snd split）
其中n =长度xs 
 split = splitAt（n`div` 2）xs



解决方案4



我在写这个问题时想到了这个问题： 

  allTheSame''''::（方程a）=> [a]  - > Bool 
 allTheSame''''xs = all（== head xs）（tail xs）



< h2>问题




  1. 我认为解决方案0效率不高，至少在内存方面，因为 map 会在将和应用到其元素之前构造另一个列表。我对吗？

  2. 解决方案1仍然效率不高，至少在内存方面，因为 takeWhile 会再次建立一个额外的列表。解决方案2是尾递归（right？），它应该非常高效，因为它会返回 False 尽快（xs !! 0 == xs !! 1）为False。我对吗？

  3. 解决方案3应该是最好的，因为它的复杂性应该是O（log n）


  4. 解决方案4对我来说看起来相当Haskellish（是吗？），但它可能与解决方案0相同，因为所有p =和。 map p （来自Prelude.hs）。对吗？

  5. 还有其他更好的书写方式吗？ allTheSame ？现在，我希望有人会回答这个问题，告诉我这里有一个内置函数：我用hoogle进行搜索，但我没有找到它。无论如何，因为我正在学习Haskell，所以我认为这对我来说是一个很好的练习：）


    其他欢迎发表评论。谢谢！

    解决方案

    gatoatigrado的答案为衡量各种解决方案的性能提供了一些不错的建议。这是一个更具象征意义的答案。



    我认为解决方案0（或者，完全等同于解决方案4）将是最快的。请记住，Haskell是 lazy ，所以 map 不需要在和应用。建立直觉的一个好方法就是玩无限。举例来说： 

      ghci>和$ map（< 1000）[1 ..] 
     False

    所有数字都小于1,000。如果 map 在应用和之前构造了整个列表，那么这个问题就永远无法回答。即使给列表一个非常大的右端点（即Haskell没有做任何魔术，这取决于列表是否无限），表达式仍然会很快回应。


    $ b 

     和[] = True 
    和（x： xs）= x&&和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] 。会有额外的分享，这太难记了。我还会评估头部表达式比它的简洁性要好（它本来会被评估的，所以它几乎没有区别）。

      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：[]））
    和$ map（== 7）（tail（7：7：7：7：8：7：7：7：[]））
    和$ map（== 7）（7：7：7：8：7：7：7：[]）
    和$（== 7）7：map（== 7）（7： 7：8：7：7：7：[]）
    （== 7）7&&和（map（== 7）（7：7：8：7：7：7：[]））
     True&&和（map（== 7）（7：7：8：7：7：7：[]））
    和（map（== 7）（7：7：8：7：7：7： []））
    （== 7）7&&和（map（== 7）（7：8：7：7：7：[]））
     True&&和（map（== 7）（7：8：7：7：7：[]））
    和（map（== 7）（7：8：7：7：7：[]）） 
    （== 7）7&&和（map（== 7）（8：7：7：7：[]））
     True&&和（map（== 7）（8：7：7：7：[]））
    和（map（== 7）（8：7：7：7：[]））
     （== 7）8&&和（map（== 7）（7：7：7：[]））
     False&&和（map（== 7）（7：7：7：[]））
     False



    看看我们甚至不需要检查最后3个7的？这是一个懒惰的评估，使得列表更像一个循环。所有其他解决方案都使用昂贵的函数，如 length （它们必须一直走到列表的最后才能给出答案），所以它们的效率会更低，他们将无法在无限列表上工作。在无限的列表上工作并且经常在Haskell中一起工作。


    Problem

    Let us suppose that we have a list xs (possibly a very big one), and we want to check that all its elements are the same.

    I came up with various ideas:

    Solution 0

    checking that all elements in tail xs are equal to head xs:

    allTheSame :: (Eq a) => [a] -> Bool
allTheSame xs = and $ map (== head xs) (tail xs)

    Solution 1

    checking that length xs is equal to the length of the list obtained by taking elements from xs while they're equal to head xs

    allTheSame' :: (Eq a) => [a] -> Bool
allTheSame' xs = (length xs) == (length $ takeWhile (== head xs) xs)

    Solution 2

    recursive solution: allTheSame returns True if the first two elements of xs are equal and allTheSame returns True on the rest of 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

    Solution 3

    divide and conquer:

    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

    Solution 4

    I just thought about this while writing this question:

    allTheSame'''' :: (Eq a) => [a] -> Bool
allTheSame'''' xs = all (== head xs) (tail xs)

    Questions

    1. I think Solution 0 is not very efficient, at least in terms of memory, because map will construct another list before applying and to its elements. Am I right?

    2. Solution 1 is still not very efficient, at least in terms of memory, because takeWhile will again build an additional list. Am I right?

    3. Solution 2 is tail recursive (right?), and it should be pretty efficient, because it will return False as soon as (xs !! 0 == xs !! 1) is False. Am I right?

    4. Solution 3 should be the best one, because it complexity should be O(log n)

    5. Solution 4 looks quite Haskellish to me (is it?), but it's probably the same as Solution 0, because all p = and . map p (from Prelude.hs). Am I right?

    6. Are there other better ways of writing allTheSame? Now, I expect someone will answer this question telling me that there's a build-in function that does this: I've searched with hoogle and I haven't found it. Anyway, since I'm learning Haskell, I believe that this was a good exercise for me :)

    Any other comment is welcome. Thank you!

    解决方案

    gatoatigrado's answer gives some nice advice for measuring the performance of various solutions. Here is a more symbolic answer.

    I think solution 0 (or, exactly equivalently, solution 4) will be the fastest. Remember that Haskell is lazy, so map will not have to construct the whole list before and is applied. A good way to build intuition about this is to play with infinity. So for example:

    ghci> and $ map (< 1000) [1..]
False

    This asks whether all numbers are less than 1,000. If map constructed the entire list before and were applied, then this question could never be answered. The expression will still answer quickly even if you give the list a very large right endpoint (that is, Haskell is not doing any "magic" depending on whether a list is infinite).

    To start my example, let's use these definitions:

    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

    Here is the evaluation order for allTheSame [7,7,7,7,8,7,7,7]. There will be extra sharing that is too much of a pain to write down. I will also evaluate the head expression earlier than it would be for conciseness (it would have been evaluated anyway, so it's hardly different).

    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

    See how we didn't even have to check the last 3 7's? This is lazy evaluation making a list work more like a loop. All your other solutions use expensive functions like length (which have to walk all the way to the end of the list to give an answer), so they will be less efficient and also they will not work on infinite lists. Working on infinite lists and being efficient often go together in Haskell.

    这篇关于有效地检查（大）列表中的所有元素是否相同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆