Re: [Haskell-cafe] Sorting efficiency

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" 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 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