如何在 Scala 中有效地删除 var
How to efficiently remove var in Scala
我正在尝试解决问题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
如果您只想删除 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中看到代码运行。
我会选择 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
非常相似的@Luis 解决方案,如果您对可变性没问题,那么带有累加器的尾递归就足以摆脱 var
s 和循环。
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.
这样的手指树
我正在尝试解决问题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
如果您只想删除 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中看到代码运行。
我会选择 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
非常相似的@Luis 解决方案,如果您对可变性没问题,那么带有累加器的尾递归就足以摆脱 var
s 和循环。
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.
这样的手指树