Changes between Initial Version and Version 2 of Ticket #4086


Ignore:
Timestamp:
Jun 25, 2010 10:18:53 PM (5 years ago)
Author:
igloo
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #4086

    • Property Type of failure changed from Runtime performance bug to Documentation bug
    • Property Difficulty changed from to Easy (less than 1 hour)
    • Property Architecture changed from x86 to Unknown/Multiple
    • Property Milestone changed from to 6.14.1
    • Property Operating System changed from Linux to Unknown/Multiple
  • Ticket #4086 – Description

    initial v2  
    11I 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:
    2 
     2{{{
    33nub l                   = nub' l []
    4 
    54  where
    6 
    75    nub' [] _           = []
    8 
    96    nub' (x:xs) ls
    10 
    117        | x `elem` ls   = nub' xs ls
    12 
    138        | otherwise     = x : nub' xs (x:ls)
    14 
     9}}}
    1510This 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).
    1611