3

我有 3 个类型列表::[Integer]，它们从最小到最大排序，所有长度都是任意和不同的，在所有 3 个列表中查找所有常见整数（如果存在）的最有效方法是什么。

4

4 回答 4

8

我不知道这是否是最快的，但应该很快。使用列表或排序的事实。

repeats :: [Integer] -> [Integer] -> [Integer] -> [Integer]
repeats [] _ _    = []
repeats _ [] _    = []
repeats _ _  []   = []
repeats a@(x:xs) b@(y:ys) c@(z:zs)
   | x == y && y == z     = x : repeats xs ys zs
   | x <= y && x <= z     = repeats xs b c
   | y <= x && y <= z     = repeats a ys c
   | otherwise            = repeats a b zs

如果所有列表的第一个元素相同，那么我们将其添加到重复列表中。否则，我们丢弃任何列表中的最小值，然后递归。如果你有 n 个列表，你可能需要一个二进制堆或其他东西。

编辑

尾递归版本

repeatsTail :: [Integer] -> [Integer] -> [Integer] -> [Integer]
repeatsTail f s t = go f s t []
   where go [] _ _  acc = reverse acc 
         go  _ [] _ acc = reverse acc 
         go  _ _ [] acc = reverse acc 
         go a@(x:xs) b@(y:ys) c@(z:zs) acc 
            | x == y && y == z     = go xs ys zs (x:acc)
            | x <= y && x <= z     = go xs b c acc 
            | y <= x && y <= z     = go a ys c acc 
            | otherwise            = go a b zs acc

编辑2：

用 as 模式

于 2013-07-05T22:20:39.747 回答
7

  • 最简洁的方法可能是使用函数 Data.List.intersect：

    import Data.List (intersect)

intersect [1, 2, 3] (intersect [1, 2] [2, 3])

    这个解决方案的问题是必须intersect多次遍历列表才能找到匹配的元素。

  • 如果要避免这种开销，则必须将元素存储在更有效的数据结构中，至少是暂时的。显而易见且可能相当有效的解决方案是转换为集合并使用 Data.Set.intersection：

    import Data.Set (fromList, toList, intersection)

toList (intersection (fromList [1, 2, 3]) (intersection (fromList [1, 2]) (fromList [2, 3])))

  • 如果列表的元素足够小以适合Int（而不是Integer），则可以使用Data.IntSet代替Data.Set来提高性能：

    import Data.IntSet (fromList, toList, intersection)

toList (intersection (fromList [1, 2, 3]) (intersection (fromList [1, 2]) (fromList [2, 3])))

  • 如果您需要更高的性能，则必须选择适合列表中数字的数据结构。也许位集适用于您的用例？或者您可以尝试以某种方式使用UArray Int Boolean该accumArray功能。

于 2013-07-05T22:34:58.630 回答
3

对于短名单，我会简单地使用elem. 您也许可以利用出现在所有三个列表中的任何数字都必须出现在最短列表中的洞察力：因此您只需要考虑最短列表中的所有数字。

对于更长的列表，我会将列表转换为IntSet然后使用intersection：

import Data.IntSet

intersection3 :: [Int] -> [Int] -> [Int] -> [Int]
intersection3 a b c = toList $ fromAscList a `intersection` fromAscList b `intersection` fromAscList c
于 2013-07-05T22:11:24.690 回答
2

这似乎也工作得很快：

import Data.List (sort,group)

f a b c = map head
        . filter (not . null . drop 2) 
        . group
        . sort 
        $ a ++ b ++ c
于 2013-07-06T11:12:18.390 回答