Hans Georg Schaathun | 23 Jan 17:24 2014
Picon

Sorting a Repa Array

Hi,

I am trying to parallellise genetic algorithms using haskell,
but I get stuck at the stage where I need to sort the array of
chromosomes based on their fitness.

Using Repa, I am neither able to find a nice library implementation
to sort an array, nor can I figure out how to generate a new array
modifying only a few entries.

I am not at a stage where I need to optimise execution time.  It
is still at the stage of learning exercise, wrt both to genetic
algorithms, haskell, and splittable pseudo-random number generators.
Thus, I would be grateful for both naïve and clever suggestions :-)

Except for the sorting stage, the problem seems to well suited for
Repa, with a chain of operations which can be mapped on the array.
I am also planning to explore accelerate later for GPU work, and
Repa seems to be a better step on the way than most other alternatives.

My arrays are 1-D boxed arrays BTW.  The entries are tuples including
an Unboxed Vector (and a Double on which the sort order is defined).
Doing it as a 2-D Unboxed Array is further down on the agenda; I need
more practice before I get my head around using slices correctly.

So, any advice?  Whether it involves conversion to a data type where
a library sort routine is available, a library sort routine I have 
missed, or how to create new deferred arrays by updating selected
entries in the input array so that I can implement sorting myself.

(Continue reading)

Chaddaï Fouché | 23 Jan 17:59 2014
Picon

Re: Sorting a Repa Array

Convert to a vector (that should be efficient since I understand that it is the underlying representation anyway), then use the sort algorithms available in the vector-algorithms package then convert back. You'll need to use modify to apply the sort (since it works on MVector).

I don't think there's a simpler or better solution right now.
-- 
Jedaï

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Carter Schonwald | 23 Jan 18:08 2014
Picon

Re: Sorting a Repa Array

Indeed!  Repa and accelerate are really designed as a showcase for pushing the cutting edge of fusion based optimization.  Sorting algorithms, fast matrix multiply, and other locality sensitive algorithms are precisely their weakest spot.  To the point where you really shouldn't try to use them for such!


I second the vector-algorithms recommendation. Be prepared for some large compile times, those sorting algs do a lot of Inlining to give you good perf. 

On Thursday, January 23, 2014, Chaddaï Fouché <chaddai.fouche <at> gmail.com> wrote:
Convert to a vector (that should be efficient since I understand that it is the underlying representation anyway), then use the sort algorithms available in the vector-algorithms package then convert back. You'll need to use modify to apply the sort (since it works on MVector).

I don't think there's a simpler or better solution right now.
-- 
Jedaï

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Hans Georg Schaathun | 23 Jan 19:40 2014
Picon

Re: Sorting a Repa Array

On Thu, Jan 23, 2014 at 05:59:55PM +0100, Chaddaï Fouché wrote:
> Convert to a vector (that should be efficient since I understand that it is
> the underlying representation anyway), then use the sort algorithms
> available in the vector-algorithms package then convert back. You'll need
> to use modify to apply the sort (since it works on MVector).

Thanks a lot; I think I am starting to comprehend.
I suppose this is the modify you mean:

  modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a

forall is a chapter of Haskell which I have not made it through,
but with a concrete example which I need, I should manage tomorrow.

Thanks again, to both responders.

--

-- 
:-- Hans Georg

Gmane