Как я могу сохранить как совпадающие, так и несовпадающие части, используя неизменный сбор за O (n) раз - PullRequest
Новая
       6

Как я могу сохранить как совпадающие, так и несовпадающие части, используя неизменный сбор за O (n) раз

0 голосов
/ 16 февраля 2020

Я должен оперировать списком 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, я пытался найти подход, который решает проблему с использованием неизменяемого коллекции.

Ответы [ 2 ]

1 голос
/ 16 февраля 2020

Это рекурсивная функция разбиения с использованием неизменяемых данных 

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)

1 голос
/ 16 февраля 2020

Я придумал два решения. Я не нахожу и то, и другое полностью удовлетворительным, но, надеюсь, они могут помочь вам достичь вашей цели.

Первая - хвостовая рекурсивная, но обращает исходный ввод. Это может быть достаточно для вашего варианта использования, если вы не заботитесь о порядке, но если вам нужно, вы должны обратить вспять полученные списки, прежде чем возвращать их, что включает в себя второй проход по списку (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))
}

Вы можете поиграться с этим кодом здесь, в Scast ie.

Редактировать

Третье решение, которое сохраняет недостатки первого, но, вероятно, более читабельно, разбивает проблему на две части и использует состав функции: 

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)

Это решение доступно и в Scast ie.

...