Borrow checker help in manipulating a 2D vector

[h_a]

Hi I am iterating through a vector of vector and I can't seem to get past the BC.

The original code:

	for (int i = 1; i < a.length + 1; ++i)
		for (int j = 1; j < b.length + 1; ++j) {
			const ulong substitutionCost = a[i - 1] == b[j - 1] ? 0 : 1;
			matrix[i][j] = min(matrix[i - 1][j - 1] + substitutionCost,
							   matrix[i][j - 1] + 1, 
							   matrix[i - 1][j] + 1
							);
		}

    let mut cache = vec![vec![0; b.len() + 1]; a.len() + 1];
    // ...
    for (row_number, row) in cache.iter_mut().enumerate() {
        for (column_number, val) in row.iter_mut().enumerate() {
            if row_number > 0 && column_number > 0 {
                let substitution_cost =
                    if a.as_bytes()[row_number - 1] == b.as_bytes()[column_number - 1] {
                        0
                    } else {
                        1
                    };
                *val = (cache[row_number - 1][column_number - 1] + substitution_cost)
                    .min(cache[row_number - 1][column_number] + 1)
                    .min(cache[row_number][column_number - 1] + 1); // BC failure
            }
        }
    }

cannot borrow cache as immutable because it is also borrowed as mutable

Any help?

[droundy]

Just avoid using iterators and you'll be fine. If you're worried about the cost of bounds checking then you probably need to rethink your algorithm, but will probably benefit from a change of data structures. Vectors of vectors are terrible for the cache and tend to perform poorly relative to a dense array.

Edit: by dense array, I mean a data structure where all the data is stored continuously, like a Fortran 2d array, or a bumpy array, or an ndarray in rust. Or just use a single Vec and use arithmetic to index it.

[h_a]

Does Rust have runtime determined non-growable arrays?

For example auto matrix = uninitializedArray!(ulong[][])(a.length + 1, b.length + 1); will yield me an unitialized 2D array of a.length + 1 rows and b.length + 1 columns. Of course, the lengths of a and b aren't known in compile time.

[alice]

Yes, non-growable runtime determined arrays are known as Box<[T]>. You can't have 2d arrays without an allocation per sub-array that way directly, but you can do that yourself.

[ZiCog]

Unfortunately making 2D arrays like that results in arrays that are very slow to operate on compared to proper fixed sized 2D arrays. Like 50% slower.

That may or may not mater depending on size and what you are doing with them.

[alice]

I assume that is due to the multiplication inside the indexing operation, which has to multiply with a variable number instead of a compile-time constant? There isn't really much you can do about that if you want the size to be runtime determined.