Re: [accelerate-haskell] Grouping arrays with different shapes

[Trevor McDonell]

Hi Danyil!

Sorry for the late reply, this one got lost...

In general we see the second of your suggestions: an array of the elements and an array specifying how many elements there are in each group, which is often called the segment descriptor. The some problem happens with filter for example:

filter :: (Shape sh, Elt e)

       => (Exp e -> Exp Bool)

       -> Acc (Array (sh :. Int) e)

       -> Acc (Vector e, Array sh Int)

The library contains a few versions of such segmented operations, foldSeg, scanlSeg, for example.

For your specific use case maybe padding the arrays with some default value to keep them regular would be faster (as there is some overhead to deal with the segment descriptor of course).

Kind regards,

-Trevor

On Tue, 20 Apr 2021 at 19:04, Даниил Дворянов <daniil.d...@gmail.com> wrote:

Hi!

I am trying to implement APL's key operator in Haskell using Accelerate.

My first attempt to type key operator looks like this:

key :: (Shape sh, Shape sh', Elt k, Elt v, Elt r)

    => (Acc (Array sh k) -> Acc (Array sh v) -> Acc (Array sh' r))

    -> Acc (Array (sh :. Int) k)

    -> Acc (Array (sh :. Int) v)

    -> Acc (Array (sh :. Int) k, Array (sh' :. Int) r)

The return type contains two arrays, that are supposed to have the same outer dimension. The first array contains unique keys, while the second array is supposed to contain a list of values corresponding to every key from the first array. However, since key operator assumes grouping the array of values by the respective keys, the number of values for each group will always be different. But since Accelerate allows only flat arrays, all of the groups have to be the same size.

I have been thinking of several possible workarounds for this, such as use the maximum length of a group for shape, and fill the unused space in other groups with default values (works in my case, might not work in general and might not be efficient); or add a new output vector which specifies the size of each group (in that case, the return type would be Acc (Vector Int, Array (sh :. Int) k, Array sh' r). 

Since I am new to array programming, it might be that I am missing something. Perhaps there is already an implementation of the key operator that I am not aware of? Or maybe there is a better way to represent "arrays of lists of arrays" in Accelerate?

Thank you in advance,

Danyil Dvorianov

--
You received this message because you are subscribed to the Google Groups "Accelerate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to accelerate-hask...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/accelerate-haskell/d695f6bb-d837-4b6f-9a59-f130086f5c52n%40googlegroups.com.

[Даниил Дворянов]

Hi Trevor!

Thank you for the reply! It is my first time using a Google Group, so I got confused and accidentally sent two identical letters. Sorry for that.

The segment descriptor option indeed seems like a logical choice. Will try to proceed with that. 

Kind regards, 

Danyil Dvorianov