Sorting efficiency

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Sorting efficiency

David Feuer
I'm writing a toy program (for a SPOJ problem--see
https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my
performance problem is that I'm spending too much time sorting. I'm
using Data.List.sort on [Int32] (it's a 32-bit architecture). Others,
using other languages, have managed to solve the problem within the
time limit using the same approach I've 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sorting efficiency

Clark Gaebel-2
It's 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 <[hidden email]> wrote:
I'm writing a toy program (for a SPOJ problem--see
https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my
performance problem is that I'm spending too much time sorting. I'm
using Data.List.sort on [Int32] (it's a 32-bit architecture). Others,
using other languages, have managed to solve the problem within the
time limit using the same approach I've 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sorting efficiency

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" <[hidden email]> wrote:
It's 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 <[hidden email]> wrote:
I'm writing a toy program (for a SPOJ problem--see
https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my
performance problem is that I'm spending too much time sorting. I'm
using Data.List.sort on [Int32] (it's a 32-bit architecture). Others,
using other languages, have managed to solve the problem within the
time limit using the same approach I've 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: 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" <[hidden email] [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 <[hidden email]
>> [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
>>> [hidden email] [2]
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe [3]
>
>
> Links:
> ------
> [1] https://www.spoj.pl/problems/ABCDEF/
> [2] mailto:[hidden email]
> [3] http://www.haskell.org/mailman/listinfo/haskell-cafe
> [4] http://hackage.haskell.org/package/vector
> [5] mailto:[hidden email]
> [6] mailto:[hidden email]


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Sorting efficiency

David Feuer
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
<[hidden email]> 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" <[hidden email] [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 <[hidden email]
>>> [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
>>>> [hidden email] [2]
>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe [3]
>>
>>
>>
>> Links:
>> ------
>> [1] https://www.spoj.pl/problems/ABCDEF/
>> [2] mailto:[hidden email]
>> [3] http://www.haskell.org/mailman/listinfo/haskell-cafe
>> [4] http://hackage.haskell.org/package/vector
>> [5] mailto:[hidden email]
>> [6] mailto:[hidden email]
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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
> <[hidden email]> 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" <[hidden email] [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 <[hidden email]
>>>> [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
>>>>> [hidden email] [2]
>>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe [3]
>>>
>>>
>>>
>>> Links:
>>> ------
>>> [1] https://www.spoj.pl/problems/ABCDEF/
>>> [2] mailto:[hidden email]
>>> [3] http://www.haskell.org/mailman/listinfo/haskell-cafe
>>> [4] http://hackage.haskell.org/package/vector
>>> [5] mailto:[hidden email]
>>> [6] mailto:[hidden email]
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe