Haskell函数nub效率低下

Question

我对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中效率并不是主要问题，但至少标准库可以尽力选择（渐进）最佳的数据结构来完成任务。

- jforberg

---

没有Ord或Hashable的限制，这是唯一可能的实现。 - Niklas B.

顺便提一下，在最坏情况下使用哈希表仍然是O(n^2)。 - newacct

@newacct 请解释你的推理。根据我的计算，由于哈希表的插入和查找是O(1)，我们有n(O(1) + O(1)) = O(n)。 - jforberg

@jforberg：散列表的插入和查找在最坏情况下都是O(n)。 - newacct

@WillNess：“为了防止退化（当所有键都碰撞并且我们最终得到无法使用的O(n)查找哈希表）, 我们能否在检测到退化时使用不同的哈希函数进行重新哈希（类似于几何扩展方案，对于加倍大小）？” 大多数库（包括hashable包）中实现哈希表的方式是，程序员为给定类型提供哈希函数，哈希表除了该哈希函数外没有其他可用的东西，因此如果程序员提供的哈希函数发生冲突，则库无能为力。 - newacct

Answer 1

效率在Haskell中相当重要，毕竟这种语言的性能与Java相当，并且在内存消耗方面击败了Java，但当然它不及C。

回答您的问题相当简单： Prelude中的 nub 只需要一个 Eq 约束条件，而基于 Map 或 Set 的任何实现也要求有 Ord 或 Hashable 约束条件。

- Nikita Volkov

---

如果你真的想要，你可以通过类型类和新类型或存在包装器来实现。然而，我更喜欢使用描述性名称，比如 nubOrd、nubHashable。 - Nikita Volkov

@jforberg，"universal hash operator"会如何工作？ - dfeuer

Java为所有对象提供了一个哈希方法，通常它只返回对象的内存地址，这确保了所有Java类型都可以放入散列表中。我相信在Haskell中也可以做类似的事情，但这可能涉及到污染语言的纯度，甚至可能达到不利的程度。 - jforberg

@jforberg，这个概念最大的问题在于Haskell的值没有身份(identity)。它们根本不是对象。运行时系统中两个相同的指针当然会指向同一个东西，但是绝对没有保证两个相等的东西会在同一地址上。例如，let {a=[1,2];b=[1,2]} in a==b 肯定会计算为True，但如果应用一个神话般的通用哈希函数，let {a=[1,2];b=[1,2]} in uHash a == uHash b 的结果将取决于编译器应用了什么优化! 它就是不起作用。 - dfeuer

一个简单/极端的例子：hash(2*2^100::Integer) 不太可能等于 hash(2^101::Integer)。 - dfeuer

Answer 2

您说得没错 - nub 是一个O(n^2)的算法。然而，仍有一些原因可以让您使用nub而不是使用哈希表：

• 对于小型列表，它仍然可能更快
• nub 只需要Eq约束；相比之下，Data.Map要求键具有Ord约束，Data.HashMap则要求键类型具有Hashable和Ord类型类
• 它是惰性的 - 您不必运行整个输入列表即可开始获得结果

编辑：第三点上稍作修正 - 您不必处理整个列表即可开始获得结果；但您仍需要检查输入列表的每个元素（因此，nub无法用于无限列表），但是只要找到一个唯一元素，就会开始返回结果。

- ErikR

---

同意。但是哈希表也可以是“懒”的，因为您可以在第一次看到它们时输出唯一值。但是，好吧。 - jforberg

Answer 3

https://groups.google.com/forum/m/#!msg/haskell-cafe/4UJBbwVEacg/ieMzlWHUT_IJ

根据我的经验，“初学者” Haskell（包括 Prelude 和糟糕的软件包）在许多情况下简单地忽略性能，而更注重简洁易懂。Haskell 性能是一个复杂的问题，所以如果您没有足够的经验去搜索 Platform 或 Hackage 中的 nub 简单替代方案（特别是如果您的输入仅因为您没有考虑其他结构而使用列表），那么 Data.List.nub 可能不是您唯一的主要性能问题，而且您可能正在编写一个性能并不重要的玩具项目的代码。您只需要相信，当您开始构建一个大型（在代码或数据方面）的项目时，您将会更有经验，并知道如何更有效地设置程序。换句话说，不要担心，假设任何来自 Prelude 或 base 的 Haskell 98 中的内容都不太可能是解决问题的最有效方法。

- misterbee