I realized my algorithm is insane. The correct way to sort [a*b|a<-A, b<-B] is clearly to sort A and B, then for each a in A construct either map (a*) B or map (a*) (reverse B), depending on the sign of a, then merge all these results together with a merge that collapses duplicates. I was multiplying and then sorting, which is way worse. The same (modulo sign) goes for adding lists. On Aug 4, 2012 1:55 PM, "Clark Gaebel" <cgae...@uwaterloo.ca> wrote:
> It's generally not advisable to use Data.List for performance-sensitive > parts of an application. > > Try using Data.Vector instead: http://hackage.haskell.org/package/vector > > On Sat, Aug 4, 2012 at 11:23 AM, David Feuer <david.fe...@gmail.com>wrote: > >> I'm writing a toy program (for a SPOJ problem--see >> https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my >> performance problem is that I'm spending too much time sorting. I'm >> using Data.List.sort on [Int32] (it's a 32-bit architecture). Others, >> using other languages, have managed to solve the problem within the >> time limit using the same approach I've taken (I believe), but mine is >> taking too long. Any suggestions? Do I need to do something insane >> like sorting in an STUArray? >> >> David Feuer >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe@haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >> >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
