Scala两个Vector按ID和时间关联时是否遍历全部元素的验证问题

核心结论 #

• 你当前使用的filter方法会完整遍历整个vecBase22的所有元素，不会匹配到目标就停止遍历：filter的设计逻辑是收集集合中所有满足条件的元素，因此必须完成全量遍历才能得到最终结果。
• 要打印所有被校验的元素组合，只需要把打印逻辑移到filter的判断函数内即可，而非放在后续仅匹配成功才会执行的map中。

打印所有校验组合的实现代码 #

val vecBase30 = vecBase21.map(x => 
  vecBase22.filter { y =>
    // 每进入一次该函数代表校验了一对(x,y)组合，直接打印即可
    println(s"校验组合：x(ID=${x._1}, 时间=${x._2}) <-> y(ID=${y._1}, 时间=${y._2})")
    x._1 == y._1 && x._2 == y._2
  }.map(y => (x._1, x._2, x._3, y._3))
).flatten

运行上述代码即可输出所有参与校验的(x,y)对，你可以通过打印总条数确认：每个vecBase21的元素都会对应完整遍历一遍vecBase22的所有元素，总校验次数为vecBase21长度 * vecBase22长度。

性能优化方案 #

你当前的实现时间复杂度为O(n*m)，数据量较大时性能很差，结合两个集合已经按(ID+时间)排序、且键唯一的前提，推荐两种更高效的实现：

1. 预转Map查找：先把vecBase22转成以(ID,时间)为键的Map，后续查找复杂度降到O(1)，总复杂度O(n+m)

val base22Map = vecBase22.map(y => ((y._1, y._2), y._3)).toMap
val vecBase30 = vecBase21.flatMap(x => base22Map.get((x._1, x._2)).map(v => (x._1, x._2, x._3, v)))

2. 匹配到即停止遍历：如果不想额外存储Map，可以把filter替换为find方法，find找到第一个满足条件的元素就会终止遍历，大幅减少无效校验，结果和原逻辑完全一致

val vecBase30 = vecBase21.flatMap(x => 
  vecBase22.find(y => x._1 == y._1 && x._2 == y._2)
    .map(y => (x._1, x._2, x._3, y._3))
)

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