[Haskell-cafe] Sorting efficiency

[David Feuer]

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" <cgaebel at 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.feuer at 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120804/964f9f58/attachment.htm>