如何快速统计Haskell列表中每个元素的出现次数？

Question

我有代表分类对象类别的字符串列表。

["Class 1", "Class 2", "Class 1", "Class 2", "Class 3"] 

会产生

[2,2,1]

（它们的顺序并不重要）。

我尝试了两个函数来执行此操作，这两个函数对于大型列表（数千个项目）来说都太慢了。

这是第一个，比第二个稍好一些：

uniqueClassesCounts :: [String] -> [Int]
uniqueClassesCounts classNames=
  let uniqueClasses = nub classNames
  in [length (filter (== cls) classNames) | cls <- uniqueClasses]

还有较慢的：

uniqueClassesCounts :: [String] -> [Int]
uniqueClassesCounts classNames= map length (group (sort (classNames)))

我非常确定一定有一种方法可以在线性时间内做到这一点（我的简要研究表明上述函数都可以在二次时间或更糟的情况下工作）。

我怎样才能让这件事变得更快？这是我代码中意想不到的瓶颈，70%以上的时间都花在了上面。

Answer 1

最好使用

HashMap

或其他一些可以提高查找效率的集合。

您可以使用

fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

来做到这一点：

{-# LANGUAGE TupleSections #-}

import Data.HashMap.Strict(fromListWith)

uniqueClassesCounts :: (Eq a, Hashable a) => [a] -> HashMap a Int
uniqueClassesCounts = fromListWith (+) . map (,1)

如果您只对计数感兴趣，我们可以使用

elems :: HashMap k v -> [v]

:

{-# LANGUAGE TupleSections #-}

import Data.HashMap.Strict(elems, fromListWith)

uniqueClassesCounts :: (Eq a, Hashable a) => [a] -> [Int]
uniqueClassesCounts = elems . fromListWith (+) . map (,1)