实现两个SparseVector的元素级乘法（Hadamard积）时避免使用ListBuffer的优化方案

你提的这个问题非常典型——既要保留Scala的函数式风格，又要保证高效的单遍历时间复杂度，避免可变集合和重复查找。我来给你分享两个符合要求的实现思路：

1. 尾递归双指针方案（推荐：高效且函数式） #

这个方案和你原来的单遍历逻辑一致，但用尾递归+不可变List累加替代了可变的ListBuffer，完全符合函数式编程的要求，同时保持O(K+N)的时间复杂度（K、N分别是两个向量的非零元素数量）。

Scala的尾递归会被编译器优化成循环，不用担心栈溢出问题，而且不可变List的::操作是O(1)的，最后只需要一次reverse转成数组即可。

import org.apache.spark.ml.linalg._
import org.apache.spark.sql.functions.udf
import scala.annotation.tailrec

// 纯函数式的Hadamard积实现
def hadamardProduct(v1: SparseVector, v2: SparseVector): SparseVector = {
  // 尾递归函数，维护双指针和不可变累加器
  @tailrec
  def loop(i1: Int, i2: Int, accIndices: List[Int], accValues: List[Double]): (Array[Int], Array[Double]) = {
    // 终止条件：任意一个向量遍历完成
    if (i1 >= v1.indices.length || i2 >= v2.indices.length) {
      // 因为用了prepend，最后需要反转列表再转数组
      (accIndices.reverse.toArray, accValues.reverse.toArray)
    } else {
      val idx1 = v1.indices(i1)
      val idx2 = v2.indices(i2)

      idx1.compareTo(idx2) match {
        case 0 => 
          // 索引匹配，计算乘积并加入累加器，同时推进两个指针
          loop(i1 + 1, i2 + 1, idx1 :: accIndices, (v1.values(i1) * v2.values(i2)) :: accValues)
        case -1 => 
          // v1的当前索引更小，只推进v1的指针
          loop(i1 + 1, i2, accIndices, accValues)
        case 1 => 
          // v2的当前索引更小，只推进v2的指针
          loop(i1, i2 + 1, accIndices, accValues)
      }
    }
  }

  val (resultIndices, resultValues) = loop(0, 0, Nil, Nil)
  new SparseVector(v1.size, resultIndices, resultValues)
}

// 注册UDF
val multSparseVectors = udf(hadamardProduct _)
spark.udf.register("multSparseVectors", multSparseVectors)

为什么这个方案更好？ #

• 完全没有可变状态，符合Scala函数式编程的理念
• 和原代码一样是单遍历，时间复杂度O(K+N)，内存消耗仅为共同非零元素的数量
• 尾递归优化后性能和原循环版本几乎一致

2. Map映射方案（简洁优先） #

如果你的稀疏向量非零元素数量不大，追求代码的极致简洁，可以先把其中一个向量的索引-值对转成Map，然后遍历另一个向量过滤出共同索引并计算乘积。这个方案代码更短，但内存消耗会略高（因为要存储整个Map）。

import org.apache.spark.ml.linalg._
import org.apache.spark.sql.functions.udf

def hadamardProduct(v1: SparseVector, v2: SparseVector): SparseVector = {
  // 将v2的索引和值转成Map，O(N)时间
  val v2IndexToValue = v2.indices.zip(v2.values).toMap
  
  // 遍历v1的非零元素，仅保留在v2中存在的索引，计算乘积
  val (resultIndices, resultValues) = v1.indices.zip(v1.values)
    .collect { case (idx, value) if v2IndexToValue.contains(idx) => 
      (idx, value * v2IndexToValue(idx)) 
    }.unzip

  new SparseVector(v1.size, resultIndices.toArray, resultValues.toArray)
}

// 注册UDF
val multSparseVectors = udf(hadamardProduct _)
spark.udf.register("multSparseVectors", multSparseVectors)

适用场景 #

• 向量的非零元素数量较少，Map的内存占用可以忽略
• 优先代码可读性和简洁性，对极致内存效率要求不高

总结 #

• 如果你处理的是大规模稀疏向量，优先选择尾递归双指针方案，兼顾性能和函数式风格
• 如果向量规模不大，Map映射方案的代码更简洁易维护

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