Borrow checker help in manipulating a 2D vector

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] {
                    } else {
                *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?

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.

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.

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.

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.

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.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.