Julia中寻找可张成目标向量集的最小向量子集优化问询

原代码的性能瓶颈分析 #

你的代码主要有三个核心问题导致运行缓慢：

1. 重复的矩阵构造：每次调用spans都要多次执行hcat拼接向量，向量数量较多时会产生大量内存分配与拷贝开销。
2. 冗余的秩计算：rank函数本身是高开销操作，而你的逻辑需要对每个向量单独执行一次秩检查，当调用次数超1万次时，时间复杂度会呈线性爆炸。
3. 低效的子集筛选逻辑：逐个删除向量验证的方式，没有利用线性代数特性一次性定位必要向量，属于 brute-force 思路。

优化方案：利用线性代数特性一次性求解 #

因为spanning_vectors是线性无关的，我们可以将问题转化为找到spanning_vectors中对张成correct_vectors列空间必要的最小子集，通过以下步骤高效实现：

步骤1：预构造矩阵并计算系数矩阵 #

将两组向量分别拼接为矩阵A（spanning_vectors为列）和B（correct_vectors为列），然后求解A * X = B得到系数矩阵X——这一步利用Julia的高效线性代数库，仅需执行一次。

步骤2：提取X的行空间基 #

因为B = A * X，correct_vectors的列空间等价于A中对应X行空间基的列所张成的空间。提取这些行的索引，就能得到spanning_vectors的极小子集。

优化后的代码 #

using LinearAlgebra

function smallest_subset_opt(spanning_vectors::Vector{Vector{Int64}}, correct_vectors::Vector{Vector{Int64}}) :: Vector{Vector{Int64}}
    # 构造矩阵：A的每列是spanning_vectors的向量，B的每列是correct_vectors的向量
    A = hcat(spanning_vectors...)
    B = hcat(correct_vectors...)
    
    # 求解系数矩阵X：A*X = B，因A列满秩，解唯一
    X = A \ B
    
    # 计算X的行空间基，得到对应的行索引（即spanning_vectors的索引）
    _, r = qr(X')  # 转置后做QR，得到列空间基对应原X的行
    # 获取线性无关的行的索引
    pivot_indices = r.p[1:rank(r)]
    
    # 返回对应的spanning_vectors子集
    return spanning_vectors[pivot_indices]
end

另一种等价实现：利用列主元QR分解 #

也可以通过对[A B]做列主元QR分解，直接找到A中对张成整个空间必要的列：

using LinearAlgebra

function smallest_subset_qr(spanning_vectors::Vector{Vector{Int64}}, correct_vectors::Vector{Vector{Int64}}) :: Vector{Vector{Int64}}
    A = hcat(spanning_vectors...)
    B = hcat(correct_vectors...)
    C = hcat(A, B)
    
    # 列主元QR分解，获取列置换索引p和秩
    qr_obj = qr(C, ColumnNorm())
    pivot_cols = qr_obj.p[1:rank(qr_obj)]
    
    # 筛选出属于A的列索引（A的列在前size(A,2)列）
    a_pivots = filter(idx -> idx ≤ size(A,2), pivot_cols)
    
    return spanning_vectors[a_pivots]
end

性能提升说明 #

• 时间复杂度：原代码是O(k * m * n²)（k为spanning_vectors数量，m为向量维度），优化后的代码是O(m * n²)，仅需一次线性代数运算，当k=1万时，性能提升接近1万倍。
• 内存开销：避免了重复构造矩阵的内存分配，仅需存储几个核心矩阵，GC压力大幅降低。
• 准确性：利用线性代数的严格推导，确保得到的子集是真正的极小子集，且能正确张成所有correct_vectors。

内容的提问来源于stack exchange，提问作者Asher Labovich