Implement non-axis windows and chunks iterators

[Robbepop]

Already implemented features and todos:

• ExactChunks and ExactChunksMut aswell as their NdProducer impl
• RaggedChunks or simply Chunks aswell as their NdProducer impl
• Windows
• NdProducer impl for Windows

---

Implement n-dimensional windows and chunks iterators.

Windows-iterators are especially useful for convolutional neural networks while chunk iterations may prove useful for paralell algorithms.

N-Dimensionality for both iterators use N-dimensionally shaped items.

For example for a 1-dimensional Array the windows and chunks items are also 1-dimensional.
For a 2-dimensional Array the windows and chunks items are 2-dimensional, and so on.

For windows iterator it could be useful to support two different kinds of windows iterators.
One for "valid" windows only that iterate only over windows within a valid region.
For example in a valid-windows iterator over a 10x10 shaped 2d-array and window sizes of 4x4 the iterator would iterate totally over (10-4+1)x(10-4+1) items of size 4x4.
A full-windows iterator would also iterate over the windows with invalid elements (on the edges of the array) and would simulate missing elements with zero elements.

Semi-nice visualization of n-dimensional chunks and windows iterators.

A similar approach could be used for n-dimensional chunks that iterate beyond the array sizes and replace missing/invalid array elements with zero elements.

[bluss]

That sounds good, and I love a good illustration to go together with expressing an idea.

One concern I have here is that it's probably still not an efficient way to implement convolution, to go through this.

[Robbepop]

That sounds good, and I love a good illustration to go together with expressing an idea.

Thanks! :)

One concern I have here is that it's probably still not an efficient way to implement convolution, to go through this.

True! For performance the most promising implementation for convolution is to use a GPGPU approach. But what if one doesn't want to go that far? The main question for this issue for me is, if it is possible to provide such iterators with equal performance as extern definitions. But as far as I can imagine such iterators would perform much better if implemented internally in this crate with hidden data of ArrayBase.

Also: What implementation would fit best? We could implement such iterator for example by using an item-sized local Array within the iterator to reuse the memory for copying the data out of the nd-array.

Or we could also use iterators over iterators over the nd-array and thus avoid copying of elements completely but I don't know if this approach is faster since I do not know ndarray internals too well. As far as I can think the strike-throughed idea is not feasable if we want ArrayView as items for the new iterators.

[bluss]

Between as_ptr, as_mut_ptr, and the .axes() iterator (each axis' length and stride), all the information of the raw representation is available, except for issues related to ownership, and they don't matter here. So I think it's possible to do it outside of the crate, but not so natural.

[Robbepop]

Between as_ptr, as_mut_ptr, and the .axes() iterator (each axis' length and stride), all the information of the raw representation is available, except for issues related to ownership, and they don't matter here. So I think it's possible to do it outside of the crate, but not so natural.

Okay, good to know about the currently possible "hack", but yeah it wouldn't be a very natural way to encode this behavious and would require unsafe rust to deref the pointers which is unnecessary.

For me both proposed iterators would be great and would be of great use for my projects!

[bluss]

Sure, the window iterator is a good idea. If I understand correctly, chunks has a chunk size in each dimension? .axis_chunks_iter() currently covers it if you just want to chunk it along one dimension, (using the full width of every other).

I also want to underline that using the unsafe methods or lower level code is not a hack but a feature, we need to allow it so that people can use it to improve their programs if needed.

[Robbepop]

For my proposed idea I cannot use the axis_chunks_iter since it has a different behaviour. The items of the chunks iterator I proposed has the same dimension as the underlying Array. It just acts like the 1-dimensional chunks iterator for slices but for n-dimensions.

For 2-dimensions I could really use this for the pooling function within the convolution.

And for a 3 dimensional array of size 10x10x10 I could for example chunk it with 5x5x5 cubes and would iterate over (10³ / 5³) chunks in total.

For both iterators it should be decided whether we also are in need of full-iterator that (as described) above iterate over the full area, instead of only the valid area. This is possible since in ndarray elements are all NDFloat which is Copy and has a default value 0.0 which we could simply use for invalid elements.

[bluss]

axis_chunks_iter gives views that have the same dimensionality (1d → 1d, 2d → 2d) though.

[Robbepop]

axis_chunks_iter gives views that have the same dimensionality (1d → 1d, 2d → 2d) though.

Okay I will have to take another look into the docs. Maybe I have overseen things and it could really be used to simulate the chunks iterator that I proposed here.

[Robbepop]

I have found a semi-nice visualization of the proposed chunks iterator for 2 dimensions here.

[bluss]

Right, the current axis_chunks_iter cuts stripes, not squares. So they are different in that way.

[Robbepop]

How do you feel about the importance of a chunks iterator facility for ndarray?

[bluss]

Not important, but we can try to do it

[Robbepop]

How do you feel about me trying to do it via PR? (This would probably take a while since I have to wrap my head around the libraries internals.)

[bluss]

Go ahead.

1. Remember how windows for slice has no mutable variant? That needs to be true for us too.

2. Maybe I should tell about the trick that we usually use for iterators: We reuse the basic element iterator (Baseiter) . How to construct a chunks iterator? Make an iterator that visits exactly the top right corner of each chunk (This can be done using slicing with a stride, which we can also emulate manually). For each element, you map it to an ArrayView that starts in that element (its pointer is the arrayview's pointer!)

[Robbepop]

Okay I will try! :)