<p>I realized my algorithm is insane. The correct way to sort [a*b|a&lt;-A, b&lt;-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.</p>

<div class="gmail_quote">On Aug 4, 2012 1:55 PM, &quot;Clark Gaebel&quot; &lt;<a href="mailto:cgaebel@uwaterloo.ca">cgaebel@uwaterloo.ca</a>&gt; wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<font face="verdana,sans-serif">It&#39;s generally not advisable to use Data.List for performance-sensitive parts of an application.<br><br><font face="verdana,sans-serif">Try using Dat<font face="verdana,sans-serif">a.Vector instead: <a href="http://hackage.haskell.org/package/vector" target="_blank">http://hackage.haskell.org/package/vector</a><br>


</font></font></font><br><div class="gmail_quote">On Sat, Aug 4, 2012 at 11:23 AM, David Feuer <span dir="ltr">&lt;<a href="mailto:david.feuer@gmail.com" target="_blank">david.feuer@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


I&#39;m writing a toy program (for a SPOJ problem--see<br>
<a href="https://www.spoj.pl/problems/ABCDEF/" target="_blank">https://www.spoj.pl/problems/ABCDEF/</a> ) and the profiler says my<br>
performance problem is that I&#39;m spending too much time sorting. I&#39;m<br>
using Data.List.sort on [Int32] (it&#39;s a 32-bit architecture). Others,<br>
using other languages, have managed to solve the problem within the<br>
time limit using the same approach I&#39;ve taken (I believe), but mine is<br>
taking too long. Any suggestions? Do I need to do something insane<br>
like sorting in an STUArray?<br>
<br>
David Feuer<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br>
</blockquote></div><br>
</blockquote></div>