What is the canonical crate for Dynamic size 2D Arrays? (non-numeric)


#1

What do you think is the canonical crate for dynamically sized 2D Arrays?

I say non-numerical as in I’m not thinking of matrix libraries, even if they are eligible if they have the features that make them usable with generic types. Think a 2D map, tile grid, or whatever kind of generic value per point.

2D slices / views are good to have.


#2

I do not think there is one yet, and I rolled my own when I needed it. It do not have 2D slices, but I can put it in a separated crate if needed.

Other implementation I am aware of are:

But both of them are oriented toward linear algebra, and not storage only.


#3

rblas looks very cool for the numerical part, but doesn’t have the features for generic storage. It also looks like it is unsound due to exposing unintialized data easily with Mat::new().

ndarray is mine own experiment, and while it was fun to write, it is naive and not efficient for numerics. It should support general elements well, though. I don’t believe it can be the best maintained dynamic size multidimensional array out there.


#4

- multiarray looks interesting


#5

I’m curious about what you mean, both in terms of “resizable” and “slices”. In particular:

Do you want edges that are:

  1. Smooth? (widening a row widens all rows)
  2. Ragged? (widening a row widens only that row)
  3. Sparse? (cells may be absent anywhere)

By your use of “vector”, I suspect “smooth”, as the rest likely require an indirection. But then, what kind of resizing?

  1. Fixed in one direction, growable by any amount in another, origin is a corner?
    In that case, “image scanout order” would likely work well (LTR, top to bottom)

  2. Growable equally in two directions, origin is in a corner?
    For that, perhaps progressively-larger “L” shapes, possibly alternating direction depending on how you want iteration to behave.

  3. Growable equally in all directions, origin is centered?
    Maybe a spiral would work best.

  4. Growable in order to hold more detail, origin is on a corner?
    A Hilbert curve is likely to work well.

  5. Same, but centered origin?
    Perhaps an H-tree

Do you plan on lots of iteration, in which case 1, 2, or 3 would likely be efficient? Exploiting locality, which makes 4 a possibility? Slicing on arbitrary boundaries, where 1 is probably more efficient than anything else?

I honestly suspect that there’s no sensible option for a “canonical resizable 2d vector”, because “resizable” has so many different options (with disjoint performance and behavioral limitations) that “canonical” seems to become impossible.

And that’s ignoring other things that, say, a map or tile grid would want - for example, a tile grid would likely want more than one of these, maybe using fixed-size scanout tiles at the finest detail for fast distance calculations from indexes (and lookups with those), while using a sparse Hilbert curve at a zoomed-out level to keep stuff likely to be accessed together nearby.

That’s not getting into more exotic stuff, like uniformly increasing the detail in one dimension (0 and 1 subdivide the field into two rows, 01 and 11 then double the vertical resolution by sitting after 0 and 1 respectively, etc).


#6

Oh I didn’t mean resizable. Dynamic size means size is fixed at construction, not by the type’s definition. nalgebra::DMat is a good example of a dynamically sized 2D array.