tag:blogger.com,1999:blog-7094652.post7071959736035929654..comments2024-03-23T14:36:09.980+00:00Comments on Neil Mitchell's Blog (Haskell etc): Sorting At SpeedNeil Mitchellhttp://www.blogger.com/profile/13084722756124486154noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-7094652.post-67479333615335464302008-03-31T11:58:00.000+01:002008-03-31T11:58:00.000+01:00The basic idea is rather well known. In the book ...The basic idea is rather well known. In the book ML for the Working Programmer, Paulson attributes it to Richard O'Keefe: A smooth applicative merge sort. Research paper 182, Department of AI, Edinburgh University, 1982.Anonymoushttps://www.blogger.com/profile/13094113896977200610noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-52699355978229692412008-03-28T11:45:00.000+00:002008-03-28T11:45:00.000+00:00Sammy: The original GHC version initially calls ma...Sammy: The original GHC version initially calls map (:[]), so they are both (a*n*log(n) + b*n + c). [Significant simplification, but that's the general idea]<BR/><BR/>In the case of a sorted list, for Yhc, a=0, b=1 c=1, i.e. very quick sort. GHC would be a=1 b=1 c=1<BR/><BR/>In the case of an unsorted list, Yhc a half of GHC's, but b about twice of GHC's. In that case, it probably comes down to the minor constant factors floating around. i.e. with Yhc's sort (or Lennart's sort, as would be a better name) you get faster performance for sorted and reverse sorted, and for unsorted you get roughly the same, perhaps slightly better. It's like a whole bottle of win :-)Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-81781306893954059602008-03-26T13:23:00.000+00:002008-03-26T13:23:00.000+00:00I guess then really Yhc is nlogn + n for unsorted ...I guess then really Yhc is nlogn + n for unsorted data? (with the understanding that the extra +n becomes less relevant for large enough data sets)<BR/><BR/>So the question is if the default sort should be a faster for the special case of sorting presorted lists at the expense of being a bit slower for most sorts.<BR/><BR/>I would choose the nlogn regardless, under the assumption most data will not be presorted. But, that assumption could be wrong of course, depending on your usage.<BR/><BR/>PS: No worries about the name. I knew what you meant. =)Sammy Larbihttps://www.blogger.com/profile/00528348159110680766noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-67857895754209061102008-03-11T07:59:00.000+00:002008-03-11T07:59:00.000+00:00An additional note - I use risers - more or less a...An additional note - I use risers - more or less as defined here - for algebraic topology. :)michiexilehttps://www.blogger.com/profile/00008302080954798496noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-53588235455495123562008-03-10T21:40:00.000+00:002008-03-10T21:40:00.000+00:00Consider using microbench (http://hackage.haskell....Consider using microbench (http://hackage.haskell.org/cgi-bin/hackage-scripts/package/microbench-0.1) for doing this sort of test in the future -- it's exactly the sort of thing I wrote it for!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7094652.post-17661279097734249972008-03-10T21:15:00.000+00:002008-03-10T21:15:00.000+00:00Sammy: apologies for misspelling your name - I gue...Sammy: apologies for misspelling your name - I guess I got the trailing i out of Larbi! Having the comment box at the top of the page, and your comment at the bottom certainly didn't help (bad UI in blogger).Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-89460780451311783472008-03-10T21:13:00.000+00:002008-03-10T21:13:00.000+00:00Sami: Yhc is O(n) for ordered lists, and O(n log n...Sami: Yhc is O(n) for ordered lists, and O(n log n) otherwise. For lists with various ordered chunks, Yhc is somewhere in between. GHC is O(n log n) always.<BR/><BR/>The Yhc sort is nearly identical to GHC in the merge sort bit, its just the splitting up bit where Yhc wins. You could certainly add the splitting up bit to GHC, which is what I suggest is done. Effectively, this is "use the Yhc algorithm".<BR/><BR/>It is a general sort, and it is faster in the general case as well, by a constant factor. In real world sorting, it turns out that often the input is either sorted or reverse sorted - hence it is worth considering these cases. They don't deserve to be given equal weight to sorting a random list (as my test does), but then my test was just an indicator, not a result.Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-72306044238148779112008-03-10T21:07:00.000+00:002008-03-10T21:07:00.000+00:00What is the computational complexity of Yhc? Coul...What is the computational complexity of Yhc? Could you just add the presorted list tests to GHC?<BR/><BR/>Is this a general sort? If so, why put so much weight on the special cases of presorted lists?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7094652.post-66031587027698708962008-03-10T18:08:00.000+00:002008-03-10T18:08:00.000+00:00Anon: Don't think competition, think exploration o...Anon: Don't think competition, think exploration of the design space with interesting ideas. It isn't Yhc vs GHC, it's a big group hug where everyone benefits.<BR/><BR/>My benchmark was a simple one, as a first-cut basic indicator. It wasn't designed to show Yhc being faster, it was designed to convince me (and only me) that I could drop the Yhc sorting routine. The fact that Yhc has a special case for sorted lists is <I>very</I> surprising!<BR/><BR/>My initial indicators for performance on a non-sorted input is that its ~20% faster, but those numbers are so vague as to be an indicator only, not a result.Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-36981622455857478332008-03-10T17:59:00.000+00:002008-03-10T17:59:00.000+00:00In summary:* Out of 3 sorts in your test, 2 use so...In summary:<BR/><BR/>* Out of 3 sorts in your test, 2 use sorted inputs;<BR/>* Yhc version has a special case for sorted lists;<BR/>* Yhc version is faster for that test.<BR/><BR/>No so surprising, is it?<BR/>What about performance for non-sorted inputs?Anonymousnoreply@blogger.com