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. TIA -- :-- Hans Georg
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ï
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é
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ï
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
participants (3)
-
Carter Schonwald -
Chaddaï Fouché -
Hans Georg Schaathun