Repository navigation
Slice with list #22
Description
Desired functionality is something like the following in the 1d case
>>> dask_slice('y', 'x', (100,), [(20, 20, 20, 20, 20)], ([5, 1, 27],)) # x[[5, 1, 27]]
{('x', 0): (np.concatenate, [(getitem, ('x', 0), [5, 1]),
(getitem, ('x', 1), [7])])}Though I suspect that there are other complications.
One is if we index with a list with elements that don't access blocks consecutively as in [5, 27, 1]. In this case we'll maybe want to slice each block only once and then reshuffle the results. This could probably be done by sorting the input list [5, 27, 1] -> [1, 5, 27] then doing the concatenate and finally doing another getitem on top of that to reorder the indices (in this case. (getitem, ..., [2, 0, 1])).
I'm also uncertain if this will be much more complex in n-dimensions when we mix with integers and slices.
CCing @nevermindewe in case he has ideas here.
One motivation for this is to support nd-grouping applications as is done in xray (cc @shoyer)
Activity
shoyer commentedon Feb 1, 2015
I think the complexity for N-dimensions will be manageable as long as you do MATLAB style, "orthogonal" indexing rather than NumPy style broadcasting indexing. See here for more details; practically, the difference is that orthogonal indexing
x[[0, 1], [0, 1]]gives you a 2D array rather than a 1D array like in NumPy. This simplifies things considerably -- everything along independent dimensions commutes (which helps for compositions) and to identify reduced dimensions, you only need to look for integer indexers.nevermindewe commentedon Feb 2, 2015
One very simple way to address this is to generate a new dask task for every index in the list. So, x[[5,27,1]] would become:
(getitem, ('x',0), [5]), (getitem, ('x', 1), [27]), (getitem, ('x', 0), [1])
There are a couple of nice things about generating one result per index. We don't have to worry about reordering the results from different blocks. We don't have to worry about grouping the list per blocksize. It is straightforward and simple to generate a single getitem task per index.
One major downside is that it can balloon the number of tasks in the dask and potentially slow things down from the execution of many tasks that could be aggregated.
If that is a concern, it might be fairly easy to iterate through the list and make new tasks when a block boundary is crossed.
i.e. x[[5,1,13,27,2]] becomes
(getitem, ('x',0), [5,1,13]), (getitem, ('x', 1), [27]), (getitem, ('x', 0), [2])
My guess is that out-of-order list indexing is quite rare, so doing an in-order batching might be the way to go.
I have mixed emotions about departing from the numpy broadcasting indexing. I'm not sure which approach would be least-surprising to users.
shoyer commentedon Feb 2, 2015
An alternative to departing from numpy broadcasting indexing (or at least to defer that decision) would be to not support array indexing with dask at all, but rather to implement a
takemethod likenp.take.mrocklin commentedon Feb 2, 2015
Hrm, ok. We could also implement
takeand then use it in normal slicing.The slicing code is complex (as one might expect) and I've found it challenging to generalize to handle both slices and integers and
newaxisand lists all in a single framework. Splitting out list slicing might be good.This also might not be inefficient because we're able to
cullaway unused tasks before execution.Anyway, I think I have a plan for a solution now.
Also, for anyone wanting to know exactly how
takeworksRename ProjectIndex to Index (dask#22)