Haskell函数nub效率低下

Question

Haskell函数nub效率低下

jfo*_*erg 7 algorithm performance haskell

我对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)

Run Code Online (Sandbox Code Playgroud)

据我所知,这有一个最坏情况下的时间复杂度为O(n ^ 2),因为对于一个唯一值列表,它必须比较它们一次才能看到它们实际上是唯一的.

如果使用哈希表,则复杂性可以减少到O(n)以构建表+ O(1)以检查每个值与哈希表中的先前值.当然,这不会产生有序列表,但如果有必要,也可以在O(n log n)中使用GHC自己的有序Data.Map.

为什么为重要的库函数选择这种低效的实现？我知道效率不是Haskell的主要关注点,但至少标准库可以努力为工作选择(渐近)最佳数据结构.

Answer 1

Eri*_*ikR 10

你绝对正确 - nub是一个O(n ^ 2)算法.但是,仍然有理由要使用它而不是使用hashmap:

对于小型列表,它仍然可能更快
nub只需要Eq约束; 相比之下,Data.Map需要Ord对键进行约束,并且Data.HashMap需要具有both Hashable和Ordtype类的键类型
它是懒惰的 - 你不必遍历整个输入列表就可以开始获得结果

编辑:对第三点进行轻微修正 - 您无需处理整个列表即可开始获取结果; 你仍然需要检查输入列表的每个元素(因此nub不能在无限列表上工作),但是一旦找到一个唯一的元素,你就会开始返回结果.

Answer 2

Nik*_*kov 9

在Haskell中,效率是一个非常值得关注的问题,毕竟语言与Java相当,并且在内存消耗方面胜过它,但当然不是C语言.

你的问题的答案很简单:Prelude nub只需要一个Eq约束,而任何实现基于Map或者Set也需要一个Ord或Hashable.

@jforberg,"通用哈希运算符"将如何正常工作？ (2认同)
@jforberg,这个概念的最大问题是Haskell值没有标识.它们根本不是物体.运行时系统中的两个相同的指针当然总是指向同一个东西,但绝对不能保证两个相同的东西将在同一个地址.例如,a == b`中的`let {a = [1,2]; b = [1,2]}肯定会求值为True,但如果你应用神话般的通用散列函数,`let {a = [1,2]; b = [1,2]}在uHash中a == uHash b`将给出一个结果,该结果取决于编译器应用的优化!它只是不起作用. (2认同)

归档时间：	11 年，7 月前
查看次数：	1572 次
最近记录：	9 年，1 月前