#4086: Data.List 'nub' function is O(n^2)
-----------------------+----------------------------------------------------
Reporter: Pete | Owner:
Type: bug | Status: new
Priority: normal | Component: libraries/base
Version: 6.12.1 | Keywords:
Os: Linux | Testcase:
Architecture: x86 | Failure: Runtime performance bug
-----------------------+----------------------------------------------------
I recently discovered that some Haskell code was running much slower than
I would have expected. I eventually traced the problem to the 'nub'
function in the Data.List, which ghc implements as follows:
nub l = nub' l []
where
nub' [] _ = []
nub' (x:xs) ls
| x `elem` ls = nub' xs ls
| otherwise = x : nub' xs (x:ls)
This would seem to be O(n**2), because it accumulates the values it sees
in a list. If it used a different data structure like a Set, it could be
made O(n log n).
I'm not sure whether this should be considered a bug or not. The list nub
returns is correct. On the other hand, when I call a library function in
any programming language, I would normally expect it to use an algorithm
that provides the best achievable asymptotic performance.
If you decide that you don't consider this to be a bug, can I suggest
adding a note to the documentation, so people are aware that nub should
only be used with short lists?
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4086>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
