Changes between Initial Version and Version 2 of Ticket #4086


Ignore:
Timestamp:
Jun 25, 2010 10:18:53 PM (4 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