如何在 O(n) 时间内使用不可变集合保留匹配和非匹配部分

Question

我必须根据某些条件对 tmp 列表进行操作。 false 执行批量数据库 insert 并且 true 执行 update

val tmp = List(1,2,3, 15)
val bool = List(true, true, true, false)

我正在使用以下方法创建 2 个列表，一个匹配，一个不匹配。

val result = tmp.zip(bool).partition {
case tuple if tuple._2 => true
case tuple if !tuple._2 => false
}

我得到 2 个列表，所以我可以运行 insertAll(result._2) 和 updateAll(result._1)

由于 partition 使用 scala.collection.mutable.Builder，我试图找到一种使用不可变集合解决问题的方法。

Answer 1

我想到了两个解决方案。我觉得两者都不完全令人满意，但希望它们可以帮助您实现目标。

第一个是尾递归但反转原始输入。如果您不关心顺序，这对您的用例来说可能就足够了，但如果您需要，则必须在返回结果列表之前反转结果列表，这涉及第二次遍历列表 (O(n)):

def zipAndPartition[A, B](as: List[A], bs: List[B])(p: ((A, B)) => Boolean): (List[(A, B)], List[(A, B)]) = {
  @annotation.tailrec
  def loop(left: List[A], right: List[B], acc: (List[(A, B)], List[(A, B)])): (List[(A, B)], List[(A, B)]) =
    (left, right) match {
      case (Nil, _) | (_, Nil) => acc
      case (lhead :: ltail, rhead :: rtail) if p((lhead, rhead)) => loop(ltail, rtail, ((lhead, rhead) :: acc._1, acc._2))
      case (lhead :: ltail, rhead :: rtail) => loop(ltail, rtail, (acc._1, (lhead, rhead) :: acc._2))
    }

  val (left, right) = loop(as, bs, (Nil, Nil))
  (left.reverse, right.reverse)
}

第二个不需要在返回之前反转输出但依赖于相互递归函数，因此不能用 @annotation.tailrec:

注释

def zap[A, B](as: List[A], bs: List[B])(p: ((A, B)) => Boolean): (List[(A, B)], List[(A, B)]) = {
  def loop(left: List[A], right: List[B], acc: (List[(A, B)], List[(A, B)])): (List[(A, B)], List[(A, B)]) =
    (left, right) match {
      case (Nil, _) | (_, Nil) => acc
      case (lhead :: ltail, rhead :: rtail) if p((lhead, rhead)) =>
        val tail = zap(ltail, rtail)(p)
        ((lhead, rhead) :: tail._1, tail._2)
      case (lhead :: ltail, rhead :: rtail) =>
        val tail = zap(ltail, rtail)(p)
        (tail._1, (lhead, rhead) :: tail._2)
    }

  loop(as, bs, (Nil, Nil))
}

您可以尝试使用此代码 here on Scastie。

编辑

第三个解决方案保留了第一个的缺点但可能更具可读性，将问题一分为二并使用函数组合：

val tmp = List(1, 2, 3, 15)
val bool = List(true, true, true, false)

def zip[A, B](as: List[A], bs: List[B]): List[(A, B)] = {
  @annotation.tailrec
  def loop(left: List[A], right: List[B], acc: List[(A, B)]): List[(A, B)] =
    (left, right) match {
      case (Nil, _) | (_, Nil) => acc
      case (lhead :: ltail, rhead :: rtail) => loop(ltail, rtail, (lhead, rhead) :: acc)
    }
  loop(as, bs, Nil)
}

def partition[A](as: List[A])(p: A => Boolean): (List[A], List[A]) = {
  @annotation.tailrec
  def loop(list: List[A], acc: (List[A], List[A])): (List[A], List[A]) =
    list match {
      case Nil => acc
      case head :: tail if p(head) => loop(tail, (head :: acc._1, acc._2))
      case head :: tail => loop(tail, (acc._1, head:: acc._2))
    }
  loop(as, (Nil, Nil))
}

def zap[A, B] = (zip[A, B] _).tupled.andThen(partition[(A, B)] _)

zap(tmp, bool)(_._2)

这个解决方案也是available on Scastie。

Answer 2

这是一个使用不可变数据的递归分区函数

def part[T](list: List[T])(f: T => Boolean): (List[T], List[T]) = {
  @annotation.tailrec
  def loop(rem: List[T], res1: List[T], res2: List[T]): (List[T], List[T]) =
    rem match {
      case Nil =>
        (res1.reverse, res2.reverse)
      case hd :: tail =>
        if (f(hd)) {
          loop(tail, hd +: res1, res2)
        } else {
          loop(tail, res1, hd +: res2)
        }
    }

  loop(list, Nil, Nil)
}

这个解决方案是反向构建的，以保持算法O(n)

如何在 O(n) 时间内使用不可变集合保留匹配和非匹配部分

How can I preserve both matching and non-matching parts using immutable collection in O(n) time

scala

scala-collections

编辑