Scala 根据条件减少列表

Question

我有一个特定类型的列表，我想根据条件减少。我有一种类型，其中 Interval 是具有开始和结束的 DateTime 间隔：

case class MyType(a: Interval, value: Double)

我有一个 List[MyType] 条目，我想将其缩减为基于包含相同 DateTime 和值的 MyType 的 List[MyType]。我不想重复我已经做过的清单。

假设我有：

val a = MyType(interval1, 2)
val b = MyType(interval2, 2)
val c = MyType(interval3, 1)
val d = MyType(interval4, 6)
val e = MyType(interval5, 2)

val original = List(a, b, c, d, e)

我现在必须根据以下条件减少原始列表：

1. interval should be continuous, then take the start of the first entry and the end of the second entry
2. the double value should be the same

所以假设 interval1, interval2 是连续的，结果应该是这样的：

val result = Seq(MyType(new Interval(a.interval.start, b.interval.end),2), c, d, e)

是否有更优雅的解决方案或想法？

Answer 1

在 reduce 函数中，检查条件是否为真，如果为真，return 当前累加器而不是您计算的累加器。

以下是仅对偶数求和的方法：

Seq(1,4,6,3).foldLeft(0)( (acc, a) =>
    if (a % 2 == 0) acc + a else acc
)
res5: Int = 10

对已编辑问题的回复： 看来您有一些必须满足连续元素的条件。然后你可以应用函数 .sliding.

Seq(a,b,c,d,e).sliding(2).foldLeft(0)(
    case (acc, Seq(MyType(ai, a), MyType(bi, b))) =>
        if (ai.max == bi.min) acc + a else acc
)

Buuut... 您可能已经猜到它不会像您希望的那样高效。我希望你没有做任何过早的优化，因为你知道，那是万恶之源。但是，如果您确实需要性能，请根据 while 循环重写代码（退回到 Java）。

Answer 2

这应该有效：

def reduce(xs: List[MyType]) = {
  xs match {
    case a :: b :: tail =>
      if(a.interval.end == b.interval.start && a.value == b.value)
        reduce(MyType(new Interval(a.interval.start, b.interval.end) a.value) :: tail)
      else
        a :: reduce(b :: tail)
    case _ => xs
  }
}

if 条件可能需要根据您的具体需要进行微调，但该算法应该有效。

给定一个列表xs
1. 如果前两项a和b可以合并为c，则将它们合并并返回步骤1 xs = c :: tail
2. 如果 a 和 b 无法合并，请尝试减少除第一个以外的所有元素，并将结果附加到 a
3. 否则（列表有 1 个元素或为空），return xs

Answer 3

请注意，您的任务可能会产生多个不同的解决方案，这些解决方案无法进一步减少。因此，您将得到一组解决方案：Set[Set[MyType]]

我使用 Set[MyType] 而不是建议的 List[MyType] 和 Seq[MyType] 因为顺序并不重要，我的答案需要比较不同解决方案的可能性（以避免重复）。

我的回答没有对项目的顺序做出假设，任何顺序都可以。

此外，为了简化代码，我将 Interval 替换为两个字段 from 和 to，可以轻松转换。

这里是减少的代码：

case class MyType(from: Long, to: Long, value: Double)

object MyType {
  //Returns all possible varians of reduced source.
  //If reduction is not possible, returns empty set.
  private def strictReduce(source: Set[MyType]): Set[Set[MyType]] = {
    if (source.size <= 1) {Set.empty} else {
      val active = source.head //get some item
      val otherItems = source.tail //all other items
      val reducedWithActive: Set[Set[MyType]] = otherItems.flatMap {
          case after if active.to == after.from =>
            //we have already found a reduction (active->after),
            //  so further reductions are not strictly required
            reduce(otherItems - after + MyType(active.from, after.to, active.value))
          case before if before.to == active.from =>
            //we have already found a reduction (before->active),
            // so further reductions are not strictly required
            reduce(otherItems - before + MyType(before.from, active.to, active.value))
          case notContinuos => Set.empty[Set[MyType]]
        }
      //check if we can reduce items without active
      val reducedIgnoringActive = strictReduce(otherItems).
        //if so, re-insert active and try to reduce it further, but not strictly anymore
        flatMap (reducedOther => reduce(reducedOther + active))
      reducedWithActive ++ reducedIgnoringActive
    }
  }
  //Returns all possible varians of reduced source.
  //If reduction is not possible, returns source as single result.
  private def reduce(source: Set[MyType]): Set[Set[MyType]] = strictReduce(source) match {
    case empty if empty.isEmpty => Set(source)
    case reduced => reduced
  }
  //Reduces source, which contains items with different values
  def reduceAll(source: Set[MyType]): Set[Set[MyType]] = source.
    groupBy(_.value). //divide by values, because they are not merge-able
    mapValues(reduce). //reduce for every group
    values.reduceLeft((solutionSetForValueA, solutionSetForValueB) =>
    //merge solutions for different groups
    for(subSolutionForValueA <- solutionSetForValueA;
      subSolutionForValueB <- solutionSetForValueB)
      yield (subSolutionForValueA ++ subSolutionForValueB) //merge subSolutions
    )
}

这是使用它的示例：

object Example extends App {
  val source = Set(
    MyType(0L, 1L, 1.0),
    MyType(1L, 2L, 2.0), //different value
    MyType(1L, 3L, 1.0), //competing with next
    MyType(1L, 4L, 1.0), //competing with prev
    MyType(3L, 5L, 1.0), //joinable with pre-prev
    MyType(2L, 4L, 2.0), //joinable with second
    MyType(0L, 4L, 3.0) //lonely
  )

  val solutions: Set[Set[MyType]] = MyType.reduceAll(source)
  //here you could choose the best solution (for example by size)
  //printing out
  solutions.foreach(solution => println(solution.toList.sortBy(_.from).sortBy(_.value).
      map(item => s"${item.from}->${item.to}(${item.value})").mkString(", ")))
}

我的结果是：

0->5(1.0), 1->4(1.0), 1->4(2.0), 0->4(3.0)
0->4(1.0), 1->5(1.0), 1->4(2.0), 0->4(3.0)

Answer 4

这是我想出的：

  def reduce(accumulator: Seq[MyType], original: Seq[MyType]): Seq[MyType] = original match {

    case Nil => accumulator
    case head :: xs => {
      val found = xs.find(_.timeSpan.getStart().equals(head.timeSpan.getEnd))
      if (found.isDefined && found.get.value == head.value) {
        reduce(
          accumulator :+ (MyType(new Interval(head.timeSpan.getStart, found.get.timeSpan.getEnd), head.value)),
          original.diff(Seq(found.get, head))
        )
      }
      else
        reduce(
          accumulator :+ head,
          xs
        )
    }
  }

Scala 根据条件减少列表

Scala reduce a List based on a condition

reduce

scala

list