Ketil Z. Malde wrote: >I have what I think is a really strange problem. I have a fair sized >problem, which involves sorting a data set, first on labels (which are >Strings) and then on scores (which are Ints). > >The strange thing is that string sorting is *vastly* faster than int >scoring! Now, I've tried modifying the sorting routinges, moving them >into the same module, and so on, to no avail. Is there any likely >explanation? The pipeline is basically > > sortBy int_cmp . compound_equal . sortBy string_cmp > >I hesitate to post the code, since it's part of a rather large >program, and in the hope that somebody will pop up and say that oh, >yes, it's a well know feature of 'sortBy'. Or that it's an artifact >of profiling. Or something like that. > >Any, and I mean any, suggestions really, really welcome. > >-kzm > Could it be that the string-comparison sort simply has less sorting to do than the int-comparison sort? The default definition of sortBy uses insertion sort, so if the string-sort input happens to be already sorted it takes linear time and if the int-sort input happens to be in reverse order it takes quadratic time.
Colin R _______________________________________________ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
