面试题：Rust闭包在矩阵乘法优化中的应用

1. 传统矩阵乘法算法及其时间复杂度

传统矩阵乘法算法，对于两个矩阵 $A_{m \times n}$ 和 $B_{n \times p}$，结果矩阵 $C_{m \times p}$ 的每个元素 $C_{ij}$ 是通过计算 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列的点积得到的。

fn traditional_matrix_multiply(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = a.len();
    let n = a[0].len();
    let p = b[0].len();
    let mut result = vec![vec![0; p]; m];
    for i in 0..m {
        for j in 0..p {
            for k in 0..n {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return result;
}

该算法的时间复杂度为 $O(m \times n \times p)$，因为有三层嵌套循环。

2. 使用闭包优化矩阵乘法

fn optimized_matrix_multiply(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = a.len();
    let n = a[0].len();
    let p = b[0].len();
    let mut result = vec![vec![0; p]; m];

    let dot_product = |row: &[i32], col: &[i32]| {
        row.iter().zip(col.iter()).map(|(a, b)| a * b).sum()
    };

    for i in 0..m {
        for j in 0..p {
            result[i][j] = dot_product(&a[i], &b.iter().map(|x| x[j]).collect::<Vec<_>>());
        }
    }
    result
}

3. 闭包优化分析

减少不必要计算：通过将点积计算封装在闭包 dot_product 中，使代码逻辑更清晰。并且闭包可以捕获环境变量，例如 row 和 col，这样在每次计算点积时，不需要重复传递整个矩阵相关的上下文，减少了不必要的数据传递和潜在的计算。
提高并行计算潜力：闭包的独立性使得它更容易并行化。例如，可以将不同行或列的点积计算并行执行。假设使用 rayon 库进行并行化：

use rayon::prelude::*;
fn parallel_matrix_multiply(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = a.len();
    let n = a[0].len();
    let p = b[0].len();
    let mut result = vec![vec![0; p]; m];

    let dot_product = |row: &[i32], col: &[i32]| {
        row.iter().zip(col.iter()).map(|(a, b)| a * b).sum()
    };

    result.par_iter_mut().enumerate().for_each(|(i, row)| {
        row.iter_mut().enumerate().for_each(|(j, cell)| {
            *cell = dot_product(&a[i], &b.iter().map(|x| x[j]).collect::<Vec<_>>());
        });
    });
    result
}

在这个并行版本中，闭包 dot_product 可以在多个线程中独立执行，充分利用多核处理器的优势，提高计算效率。

星途面试题库

面试题：Rust闭包在矩阵乘法优化中的应用

知识考点

面试题答案

1. 传统矩阵乘法算法及其时间复杂度

2. 使用闭包优化矩阵乘法

3. 闭包优化分析