#1218: Add sortNub and sortNubBy to Data.List
----------------------------+-----------------------------------------------
Reporter: neil | Owner:
Type: proposal | Status: closed
Priority: normal | Milestone: Not GHC
Component: libraries/base | Version: 6.8.2
Severity: normal | Resolution: wontfix
Keywords: | Difficulty: Unknown
Testcase: | Architecture: Unknown
Os: Linux |
----------------------------+-----------------------------------------------
Changes (by guest):
* cc: [EMAIL PROTECTED] (added)
* version: => 6.8.2
* os: Unknown => Linux
Comment:
This may be abandoned, but I'm curious. Is this actually an optimization?
I've been trying out some toy examples, and the 'map head . group . sort'
version seems to perform absolutely terribly compared to just 'sort .
nub', at least on my sample.
Example:
----
[EMAIL PROTECTED]:15969~>cat tmp2.hs
[ 9:58AM]
import Data.List
main = print $ uniq $ take 1000000000 $ cycle [1]
uniq = sort . nub%
[EMAIL PROTECTED]:15970~>time runhaskell tmp2.hs
[ 9:58AM]
[1]
runhaskell tmp2.hs 45.90s user 0.23s system 66% cpu 1:09.24 total
[EMAIL PROTECTED]:15971~>cat tmp4.hs
[ 9:59AM]
import Data.Set
main = print $ uniq $ take 1000000000 $ cycle [1]
uniq = toList . fromList
[EMAIL PROTECTED]:15974~>time runhaskell tmp4.hs
[10:00AM]
[1]
runhaskell tmp4.hs 38.14s user 0.14s system 96% cpu 39.743 total
[EMAIL PROTECTED]:15975~>cat tmp3.hs
[10:02AM]
import Data.List
main = print $ uniq $ take 1000000000 $ cycle [1]
uniq = map head . group . sort
[EMAIL PROTECTED]:15976~>
----
You'll understand if I don't provide timings for tmp3.hs (the map head
implementation) since it takes vastly longer than 30 seconds and eats so
much RAM and CPU time that it locks my system overnight.
Admittedly, perhaps a list of repeated items is not the best usecase, but
shouldn't optimizations - particularly optimizations in the base library
be a win in all cases? (and particularly not huge pessimizations in some
cases)?
--
gwern
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1218#comment:3>
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
