Where by "nearly double", of course, I really mean "nearly triple". I'm a little tired.
David On Sun, Aug 5, 2012 at 5:37 AM, David Feuer <david.fe...@gmail.com> wrote: > Unfortunately, I doubt it can. That algorithm reduces the number of > comparisons a good bit, but the asymptotic complexity of its other > operations remains the same, with apparently bad constant factors > (according to the article). Also, that article describes the algorithm > in terms of sorting [a+b| a<-A, b<-A], whereas I'm actually dealing > (in the more substantial phase) with [a+b | a<-A, b<-B], where B is > much larger than A. Using the merging approach I described in my last > email, I can reduce the complexity from mn log(mn) in the naive > algorithm to mn log (min {m,n}). Since m=100 and n~=10,000, I should > be able to get nearly double the speed of the naive approach, as long > as my multi-merge is fast enough. > > On Sun, Aug 5, 2012 at 3:59 AM, Heinrich Hördegen > <hoerde...@funktional.info> wrote: >> >> 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" <cgae...@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.fe...@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@haskell.org [2] >>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe [3] >>> >>> >>> >>> Links: >>> ------ >>> [1] https://www.spoj.pl/problems/ABCDEF/ >>> [2] mailto:Haskell-Cafe@haskell.org >>> [3] http://www.haskell.org/mailman/listinfo/haskell-cafe >>> [4] http://hackage.haskell.org/package/vector >>> [5] mailto:david.fe...@gmail.com >>> [6] mailto:cgae...@uwaterloo.ca >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe@haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe