algorithm - 更好的方法(功能性/不可变，但性能良好)编写一种算法，该算法在整个过程中从集合中消除项目

Question

我是 Scala 和函数式编程的初学者，我有一些算法代码可能有一些味道，因为它使用了可变性，但也有一个错误，部分原因是它是可变的。我有两组二维点。第 1 组中的每个点都与第 2 组中最近的点相关联(给定第 1 组相对于第 2 组的比例和偏移量)。我们想要一对一的相关性，而不是一对多的相关性。我认为这意味着当我们找到集合 2 中最接近集合 1 中的点时，我们应该从集合 2(的副本)中删除前者，因为我们不希望再次匹配它。然而，也许有一种不可变/功能性的方式......

下面的代码有一个错误，如果所有点都从 set2NotYetMatched 中删除，那么我们将调用 empty.minBy；这可以通过重新编写代码以使其功能更少来解决，也许使用 for 或 while 构造。但在我这样做之前，有没有更好的编码方式？这是当前代码:

  protected def calcDistanceCostBetweenSets(
        set1: Seq[Point], set1StartX: Double, set1XScale: Double, set2Window: PointWindow, xImportance: Double
        ): CloudMatch = {

    require (!set1.isEmpty)

    var set2NotYetMatched = scala.collection.mutable.Set.empty ++= set2Window.subsetWithMargins

    val correlations = set1 map(set1Point => {
      val minDistPointAndDist = set2NotYetMatched.map(set2Point =>
        (
          set2Point,
          DistanceCostCalculator.calcPointToPointDistanceSquared(
            set1Point, set2Point, set1StartX, set2Window.marginStartX, set1XScale, xImportance)))
        .minBy(_._2)

      set2NotYetMatched -= ( minDistPointAndDist._1)
      new PointCorrelation(set1Point, Collections.singletonList(minDistPointAndDist._1), minDistPointAndDist._2)
    })
    val distanceCost = correlations.map(_.getCost).foldLeft(0.0)(_ + _)
    return new CloudMatch(
      set2Window.firstPointAlongX,
      set2Window.startIndexInOriginalSubset,
      distanceCost,
      Lists.newArrayList(JavaConversions.asJavaIterable(correlations)))
  }

Answer 1

我认为一个好的方法是使用 foldLeft 来跟踪当前的相关性和 set2 中剩余的元素。

请参阅下面的 findCorrelations 方法。它类似于您的递归解决方案。一个显着的区别是您不必维护 remainingSet。你怎么看？

private def findCorrelations(
  set1: Set[Point], 
  set1StartX: Double, 
  set1XScale: Double, 
  set2Points: Set[Point], 
  set2StartX: Double, 
  xImportance: Double
): List[EventCorrelation] = {

  def calculateCost(p1: Point, p2: Point): Double = {
    DistanceCostCalculator.calcPointToPointDistanceSquared(
      p1, p2,
      set1StartX, set2StartX, set1XScale, xImportance)
  }

  set1.foldLeft((List.empty[EventCorrelation], set2Points)) { 
    case ((correlationsAcc, set2PointsRemaining), set1PointToFind) =>
      if (set2PointsRemaining.isEmpty) {
        correlationsAcc
      } else {
        val (set2MinPoint, minDist) = set2PointsRemaining.map(scorePoint =>
          (scorePoint, calculateCost(set1PointToFind, scorePoint))
        ).minBy(_._2)

        val correlation = new EventCorrelation(
          set1PointToFind, 
          Collections.singletonList(set2MinPoint),
          minDist)

        (correlationsAcc + correlation, set2PointsRemaining - set2MinPoint)
      }
  }