algorithm - 如何在 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 !!我 == 是的! j，同时将 j 位置的计数器加一。当i遇到新元素时，通过增加j在ys中找到它，然后重复上一步。这个算法是O(n*log(n))。

但我找不到以纯函数方式实现相同复杂性的方法，也没有找到任何现有函数可以实现我想要的。我应该如何在 Haskell 中执行此操作？

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