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

问题描述 #

有一个表示分类对象类别的字符串列表，例如：

["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%的运行时间）。

现有方案的性能瓶颈分析 #

• 第一个函数：nub 本身是O(n²)的遍历去重，之后每个唯一类别又要遍历整个列表做filter，总时间复杂度为O(n²)，数据量越大，性能下降越明显。
• 第二个函数：sort 是O(n log n)的时间复杂度，后续group是O(n)，总复杂度为O(n log n)，比第一个方案好，但仍达不到线性时间。

线性时间优化方案 #

使用哈希表（平均O(1)的插入/查询操作）遍历一次列表完成计数，是典型的线性时间O(n)实现。Haskell中可以用Data.HashMap.Strict（哈希表）或Data.Map.Strict（有序字典，基于红黑树，O(log n)操作但实际性能也很好），其中哈希表的平均性能更优。

方案1：使用Data.HashMap.Strict的fromListWith #

fromListWith可以直接将列表转换为键值对，同时合并重复键的计数：

import qualified Data.HashMap.Strict as HM

uniqueClassesCounts :: [String] -> [Int]
uniqueClassesCounts = HM.elems . HM.fromListWith (+) . map (\s -> (s, 1))

解释：

1. map (\s -> (s, 1)) 将每个字符串转换为(类别, 1)的键值对；
2. HM.fromListWith (+) 遍历所有键值对，遇到重复键时将值相加，得到每个类别的总计数；
3. HM.elems 提取所有计数值，得到最终结果。

方案2：使用严格折叠foldl'手动构建计数表 #

如果需要更底层的控制，可以用foldl'（严格折叠，避免惰性求值的内存开销）：

import qualified Data.HashMap.Strict as HM
import Data.Foldable (foldl')

uniqueClassesCounts :: [String] -> [Int]
uniqueClassesCounts = HM.elems . foldl' count HM.empty
  where
    count hm s = HM.insertWith (+) s 1 hm

解释：

• foldl' 从空哈希表开始，逐个处理每个字符串；
• HM.insertWith (+) s 1 hm：如果s已在哈希表中，就将对应值加1；否则插入s并设值为1；
• 最后提取所有计数值。

性能优势 #

哈希表方案的平均时间复杂度为O(n)，每个元素仅被处理一次，插入和查询操作平均为O(1)，相比之前的方案，在数据量较大时性能提升非常显著，能有效解决70%运行时间的瓶颈问题。

内容的提问来源于stack exchange，提问作者ampersander