[Haskell-cafe] Sorting efficiency
hoerdegen at funktional.info
Sun Aug 5 09:59:25 CEST 2012
can this help you?
Am 04.08.2012 20:47, schrieb 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
> 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 >
>> Its 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:
>>> Im writing a toy program (for a SPOJ problem--see
>>> https://www.spoj.pl/problems/ABCDEF/  ) and the profiler says
>>> performance problem is that Im spending too much time sorting. Im
>>> using Data.List.sort on [Int32] (its a 32-bit architecture).
>>> using other languages, have managed to solve the problem within
>>> time limit using the same approach Ive taken (I believe), but
>>> mine is
>>> taking too long. Any suggestions? Do I need to do something
>>> like sorting in an STUArray?
>>> David Feuer
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org 
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe 
>  https://www.spoj.pl/problems/ABCDEF/
>  mailto:Haskell-Cafe at haskell.org
>  http://www.haskell.org/mailman/listinfo/haskell-cafe
>  http://hackage.haskell.org/package/vector
>  mailto:david.feuer at gmail.com
>  mailto:cgaebel at uwaterloo.ca
More information about the Haskell-Cafe