如何在 Scala 中有效地删除 var

Question

我正在尝试解决问题https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

解决方案

def minCost(arr: Array[Int]):Int = {

  val minHeap = scala.collection.mutable.PriorityQueue.empty[Int].reverse
    
  arr.foreach{ ele =>
    minHeap += ele
  }
    
  var sum =0
    
  while(minHeap.size >1){
    
    val first = minHeap.dequeue()
    val second = minHeap.dequeue()
    
    val length = second + first//3+3 =6+9
    sum = sum + (first +second)//3+6+9
    
    minHeap.enqueue(length)
  }
    
  sum
}

我想摆脱 while 循环和 var。谁能提出更好的解决方案？

试过以下

val res =minHeap.foldLeft(0){
  (x,y)=>
    val sum =x+y
    minHeap.enqueue(sum)
    sum
}

println(res)
res

Answer 1

如果您只想删除 var 和 while 但仍使用可变的 PriorityQueue （说实话很好的妥协，可能是在实际代码中最好的做法） 你可以只使用尾递归方法。

type Ropes = List[Int]

def connectRopes(ropes: Ropes): Int = {
  val queue = PriorityQueue.from(ropes).reverse
  
  @annotation.tailrec
  def loop(remaining: Int, acc: Int): Int = {
    if (remaining == 0) acc
    else if (remaining == 1) acc
    else {
      val rope1 = queue.dequeue()
      val rope2 = queue.dequeue()
      val newRope = rope1 + rope2
      queue.addOne(newRope)
      loop(remaining - 1, acc + newRope)
    }
  }
  
  loop(remaining = queue.size, acc = 0)
}

但是，如果您想编写一个完全不可变的解决方案只是为了习惯使用不可变的数据结构，您可以这样做：

def connectRopesFullImmutable(ropes: Ropes): Int = {
  @annotation.tailrec
  def loop(remaining: Ropes, acc: Int): Int =
    remaining match {
      case Nil =>
        acc
      
      case _ :: Nil =>
        acc
      
      case rope1 :: rope2 :: Nil =>
        rope1 + rope2 + acc
      
      case rope1 :: rope2 :: tail =>
        @annotation.tailrec
        def findTwoMin(remaining: Ropes, min1: Int, min2: Int, acc: Ropes): (Int, Int, Ropes) =
          remaining match {
            case rope :: tail =>
              if (rope < min1) findTwoMin(remaining = tail, min1 = rope, min2 = min1, min2:: acc)
              else if (rope < min2) findTwoMin(remaining = tail, min1, min2 = rope, min2 :: acc)
              else findTwoMin(remaining = tail, min1, min2, rope :: acc)
            
            case Nil =>
              (min1, min2, acc)
          }
      
        val (min1, min2, ropes) =
          if (rope1 < rope2) findTwoMin(remaining = tail, min1 = rope1, min2 = rope2, acc = List.empty)
          else findTwoMin(remaining = tail, min1 = rope2, min2 = rope1, acc = List.empty)
        val newRope = min1 + min2
        loop(remaining = newRope :: ropes, acc + newRope)
    }
  
  loop(remaining = ropes, acc = 0)
}

回答评论 space 问题的复杂度是 (AFAIK) O(1)，因为算法是一个尾递归函数，我们不消耗堆栈，我们只操作相同的列表，所以我们也不消耗堆。
时间复杂度是 O(N^2) 因为我们在外循环中有一个内循环，这意味着这个算法非常低效。

我们可能会尝试通过保持剩余绳索列表始终排序来对其进行一些优化；如下所示。哪个应该使用 O(N log(N))，但仍然需要大量样板和低效率，只是因为不使用可变优先级队列。

def connectRopesFullImmutableOptimized(ropes: Ropes): Int = {
  @annotation.tailrec
  def loop(remaining: Ropes, acc: Int): Int =
    remaining match {
      case rope1 :: rope2 :: tail =>
        val newRope = rope1 + rope2
      
        @annotation.tailrec
        def insertSorted(remaining: Ropes, acc: Ropes): Ropes =
          remaining match {
            case rope :: ropes =>
              if (newRope > rope) insertSorted(remaining = ropes, rope :: acc)
              else acc reverse_::: (newRope :: rope :: ropes)
            
            case Nil =>
              (newRope :: acc).reverse
          }
      
        loop(remaining = insertSorted(remaining = tail, acc = List.empty), acc + newRope)
      
      case _ =>
        acc
    }
  
  loop(remaining = ropes.sorted, acc = 0)
}

您可以在Scastie中看到代码运行。

Answer 2

我会选择 unfold()。 (Scala 2.13.x)

import scala.collection.mutable.PriorityQueue

def minCost(arr: Array[Int]): Int =
  List.unfold(PriorityQueue(arr:_*).reverse){ pq =>
    Option.when(pq.size > 1) {
      val link = pq.dequeue() + pq.dequeue()
      pq.enqueue(link)
      (link, pq)
    }
  }.sum

Answer 3

非常相似的@Luis 解决方案，如果您对可变性没问题，那么带有累加器的尾递归就足以摆脱 vars 和循环。

object ConnectRopes extends App {
  import scala.annotation.tailrec
  import scala.collection.mutable

  val arr = List(4, 3, 2, 6)

  val minHeap = mutable.PriorityQueue.from(arr)(Ordering[Int].reverse)

  @tailrec
  def minCost(acc: Int = 0): Int =
    if (minHeap.size > 1) {
      val connect = minHeap.dequeue + minHeap.dequeue
      minHeap.enqueue(connect)
  
      minCost(acc + connect)
    } else acc

  println(minCost())
}

但是我不认为仅使用列表就可以获得时间复杂度相当的不可变解决方案。对于不可变的优先级队列，您将需要像 this one from ScalaZ.

这样的手指树

如何在 Scala 中有效地删除 var

How to efficiently remove var in Scala

scala

functional-programming

priority-queue

var