[Haskell-cafe] Sorting efficiency

[Heinrich Hördegen]

Hi David,

can this help you?

http://www.scribd.com/doc/81029312/5/Sorting-pairwise-sums

Heinrich

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 
> 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 [6]>
> wrote:
>
>> 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 [4]
>>
>> On Sat, Aug 4, 2012 at 11:23 AM, David Feuer <david.feuer at gmail.com
>> [5]> wrote:
>>
>>> Im writing a toy program (for a SPOJ problem--see
>>> https://www.spoj.pl/problems/ABCDEF/ [1] ) and the profiler says
>>> my
>>> performance problem is that Im spending too much time sorting. Im
>>> using Data.List.sort on [Int32] (its a 32-bit architecture).
>>> Others,
>>> using other languages, have managed to solve the problem within
>>> the
>>> time limit using the same approach Ive 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 [2]
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe [3]
>
>
> Links:
> ------
> [1] https://www.spoj.pl/problems/ABCDEF/
> [2] mailto:Haskell-Cafe at haskell.org
> [3] http://www.haskell.org/mailman/listinfo/haskell-cafe
> [4] http://hackage.haskell.org/package/vector
> [5] mailto:david.feuer at gmail.com
> [6] mailto:cgaebel at uwaterloo.ca