我正在寻找一个能够高效地统计一个列表中每个元素在另一个列表中出现次数的函数。它应该返回一个按元素/计数元组排序的列表。以下是详细说明:
countList :: Ord a => [a] -> [a] -> [(a, Integer)]
countList ['a', 'b', 'c', 'b', 'b'] ['a', 'b', 'x']
== [('a', 1), ('b', 3), ('x', 0)]
length (countList xs ys) == length ys
一个天真的实现方式可能是:
countList xs = sort . map (id &&& length . (\ y -> filter (== y) xs))
这是O(n^2)
的。但是,由于我们有Ord a
,所以可以使用更好的策略使其更快速。我们可以先对两个列表进行排序,然后以“爬梯子”的方式进行比较。
例如,下面是两个已排序的列表。如果我用命令式方法来做,我会使用指向每个列表中第一个元素的两个指针:
i
|
xs = ['a', 'b', 'b', 'b', 'c']
ys = ['a', 'b', 'x']
|
j
当
xs !! i == ys !! j
时,增加i
,同时将计数器在位置j
加一。当i
遇到一个新元素时,通过增加j
在ys
中找到它,然后重复上一步骤。此算法的时间复杂度为O(n*log(n))
。但我找不到以纯函数方式实现相同复杂度的方法,也没有找到任何现有的函数可以实现我想要的功能。在Haskell中应该如何做呢?
l2
是否可以包含重复项?因为——请查看我在 Sam 回答下面的评论——这可能会影响性能。如果它从不包含重复项,最好明确说明并使用Set
类型或其他类型。 - Erik Kaplun