[Haskell-cafe] Sorting efficiency

[David Feuer]

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.feuer at 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
> <hoerdegen at 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" <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
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe