如何用Scala标准库优化环形查找Vector元素邻居的实现？

问题描述 #

我有一个Vector，想要查找指定元素的环形邻居（首尾相连）。例如对于Vector(1, 2, 3, 4, 5)：

• 元素2的邻居结果为Some((1, 3))
• 元素5的邻居结果为Some((4, 1))
• 元素1的邻居结果为Some((5, 2))
• 元素6的邻居结果为None

我没在标准库找到现成方案（如果有的话请指出），自己实现了如下代码：

implicit class VectorOps[T](seq: Vector[T]) {
  def findNeighbors(elem: T): Option[(T, T)] = {
    val currentIdx = seq.indexOf(elem)
    val firstIdx = 0
    val lastIdx = seq.size - 1
    seq match {
      case _ if currentIdx == -1 || seq.size < 2 => None
      case _ if seq.size == 2 => seq.find(_ != elem).map(elem => (elem, elem))
      case _ if currentIdx == firstIdx => Some((seq(lastIdx), seq(currentIdx + 1)))
      case _ if currentIdx == lastIdx => Some((seq(currentIdx - 1), seq(firstIdx)))
      case _ => Some((seq(currentIdx - 1), seq(currentIdx + 1)))
    }
  }
}

请问如何借助Scala标准库简化或优化这个实现？

优化方案 #

1. 模运算统一索引逻辑 #

用模运算%可以消除首尾分支的特殊判断，同时借助标准库的基础方法简化代码：

implicit class VectorOps[T](seq: Vector[T]) {
  def findNeighbors(elem: T): Option[(T, T)] = {
    val size = seq.size
    if (size < 2) None
    else seq.indexOf(elem) match {
      case -1 => None
      case idx =>
        val prevIdx = (idx - 1 + size) % size
        val nextIdx = (idx + 1) % size
        Some((seq(prevIdx), seq(nextIdx)))
    }
  }
}

• (idx - 1 + size) % size解决了首元素前索引的环形跳转（比如idx=0时，计算后得到最后一个元素的索引）
• (idx + 1) % size处理尾元素后索引的环形跳转（比如idx=size-1时，计算后得到第一个元素的索引）
• 当size=2时，prevIdx和nextIdx会指向同一个元素，自动满足原逻辑中(elem, elem)的要求，无需单独分支

2. 函数式风格的序列配对 #

通过构造环形序列并利用zip方法，以更函数式的方式实现：

implicit class VectorOps[T](seq: Vector[T]) {
  def findNeighbors(elem: T): Option[(T, T)] = {
    val size = seq.size
    if (size < 2) None
    else {
      // 构造环形的前序-当前-后序三元组序列
      val triples = (seq.last +: seq) zip seq zip (seq.tail :+ seq.head)
      triples.collectFirst { case ((prev, curr), next) if curr == elem => (prev, next) }
    }
  }
}

• seq.last +: seq将最后一个元素前置，作为每个元素的前序序列
• seq.tail :+ seq.head将第一个元素后置，作为每个元素的后序序列
• 三次zip操作生成包含前、当前、后元素的三元组，最后用collectFirst筛选出目标元素对应的邻居对

关于标准库 #

Scala标准库确实没有直接提供环形邻居查找的方法，但上述优化均基于标准库核心方法（indexOf、%、zip、collectFirst等）实现，无需额外依赖。

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