我对Haskell标准库Data.List中的“nub”(选择唯一值)函数的实现感到困惑。 GHC的实现为
nub l = nub' l []
where
nub' [] _ = []
nub' (x:xs) ls
| x `elem` ls = nub' xs ls
| otherwise = x : nub' xs (x:ls)
据我所知,这个函数的最坏时间复杂度为O(n^2),因为对于一个包含唯一值的列表,必须至少比较一次才能确定它们确实是唯一的。
如果使用哈希表,则可以将复杂度降低到O(n),其中包括构建哈希表的O(n)和检查每个值与哈希表中之前的值是否重复的O(1)。当然,这不会产生有序列表,但如果需要,也可以在O(n log n)使用GHC自己的有序Data.Map来实现。
为什么在重要的库函数中选择这样一个效率低下的实现方式呢?我知道在Haskell中效率并不是主要问题,但至少标准库可以尽力选择(渐进)最佳的数据结构来完成任务。
Ord
或Hashable
的限制,这是唯一可能的实现。 - Niklas B.hashable
包)中实现哈希表的方式是,程序员为给定类型提供哈希函数,哈希表除了该哈希函数外没有其他可用的东西,因此如果程序员提供的哈希函数发生冲突,则库无能为力。 - newacct