如何用O(n*log(n))的时间复杂度比较两个列表中的元素数量？

Question

我正在寻找一个能够高效地统计一个列表中每个元素在另一个列表中出现次数的函数。它应该返回一个按元素/计数元组排序的列表。以下是详细说明：

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中应该如何做呢？

- xzhu

---

这种“梯子爬升”方式与标准的merge函数非常相似。查看实现，并进行修改以适应您的需求。 - n. m.

包data-ordlist专门用于有序列表的操作，例如合并、减去、成员资格、插入等。 - ErikR

@trvoldermort：l2 是否可以包含重复项？因为——请查看我在 Sam 回答下面的评论——这可能会影响性能。如果它从不包含重复项，最好明确说明并使用 Set 类型或其他类型。 - Erik Kaplun

@ErikAllik：这是一个很好的问题。从技术上讲，它是可以的。 - xzhu

Answer 1

如果第二个列表没有重复项，并且第一个列表比较长，你可以使用 Data.Map 来避免对第一个列表进行排序。这将实现 n1 log n2 的复杂度：

import Data.Map (fromList, toList, adjust)

countList :: Ord a => [a] -> [a] -> [(a, Int)]
countList l r = toList $ foldr (adjust (+1)) (fromList . zip r $ repeat 0) l

- behzad.nouri

---

“adjust”是我多年来一直自己定义的函数。好知道。 - Emil

Answer 2

我认为这可以完成您的需求：

import Data.List (sort)

countList :: Ord a => [a] -> [a] -> [(a, Int)]
countList l1 l2 = countList' (sort l1) (sort l2)
  where countList' _     []  = []
        countList' xs (y:ys) = let xs'   = dropWhile (<  y) xs
                                   (a,b) = span      (== y) xs'
                                in (y, length a) : countList' b ys

main = print $ countList ['a', 'b', 'c', 'b', 'b'] ['a', 'b', 'x']

- Sam van Herwaarden

---

无论如何，+1，但OP没有指定l2不包含重复项；如果有，递归调用需要是countList' xs' ys而不是countList' b ys；然后可以用takeWhile替换span - 这样countList ['a'，'b'，'c'，'b'，'b'] ['a'，'b'，'b'，'x'，'x']将产生[('a'，1)，('b'，3)，('b'，0)，('x'，0)，('x'，0)]。否则，返回值将先是3，然后是0，这可能会导致错误。 - Erik Kaplun