Scala按自定义规则过滤对象集合 移除属性B乱序元素实现问题

现有代码问题 #

• 采用sliding(2)仅对比原始序列的相邻元素，没有基于已过滤的结果做判断
• 永远无法保留序列最后一个元素，因为滑动窗口只会取每个窗口的第一个元素做判断
• 中间元素被移除后，后续元素的对比基准错误，导致结果不符合预期

采用单次遍历+状态维护的O(n)复杂度方案，遍历过程中仅保留ri不小于上一个保留元素ri的元素，完全满足性能要求，同时适配Seq和Array类型。

核心实现代码 #

import org.springframework.stereotype.Component
import scala.collection.mutable.ListBuffer

case class Target(rt: Double, ri: Double)

trait OutOfOrderRemover {
  def filter(targets: Seq[Target]): Seq[Target]
}

@Component
class RecursiveOOO extends OutOfOrderRemover {
  override def filter(targets: Seq[Target]): Seq[Target] = {
    if (targets.isEmpty) return Seq.empty
    
    val result = new ListBuffer[Target]()
    var lastRi = Double.NegativeInfinity
    
    targets.foreach { target =>
      if (target.ri >= lastRi) {
        result += target
        lastRi = target.ri
      }
    }
    
    result.toSeq
  }
}

如果要严格用尾递归实现匹配类名定义，可使用如下版本：

@Component
class RecursiveOOO extends OutOfOrderRemover {
  override def filter(targets: Seq[Target]): Seq[Target] = {
    @scala.annotation.tailrec
    def loop(remaining: Seq[Target], lastRi: Double, acc: ListBuffer[Target]): Seq[Target] = {
      if (remaining.isEmpty) acc.toSeq
      else {
        val current = remaining.head
        if (current.ri >= lastRi) {
          loop(remaining.tail, current.ri, acc += current)
        } else {
          loop(remaining.tail, lastRi, acc)
        }
      }
    }
    
    loop(targets, Double.NegativeInfinity, new ListBuffer[Target])
  }
}

测试代码修正 #

将原有滑动窗口逻辑替换为新实现即可通过所有测试用例：

@RunWith(classOf[SpringRunner])
class OutOfOrderTest extends AnyWordSpec with Matchers with Debuggable {
  private val oooRemover = new RecursiveOOO()

  "OutOfOrderTest" should {
    "filter out of order simple" in {
      val bad = Seq(Target(10, 10), Target(20, 20), Target(30, 36), Target(40, 30), Target(50, 40), Target(60, 50))
      val filtered = oooRemover.filter(bad)
      filtered shouldEqual Seq(Target(10, 10), Target(20, 20), Target(30, 36), Target(50, 40), Target(60, 50))
    }

    "filter out of order complex" in {
      val bad2 = Seq(Target(10, 10), Target(20, 20), Target(30, 36), Target(40, 40), Target(50, 30), Target(60, 50))
      val filtered2 = oooRemover.filter(bad2)
      filtered2 shouldEqual Seq(Target(10, 10), Target(20, 20), Target(30, 36), Target(40, 40), Target(60, 50))
    }
  }
}

• 单次遍历，时间复杂度O(n)，空间复杂度O(k)，k为过滤后的元素数量，效率远高于原有滑动窗口+多次过滤的实现
• 采用ListBuffer做累加，避免Seq拼接的性能损耗，后续切换为Array时仅需修改返回值转换逻辑即可，核心判断逻辑无需调整

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