替换我的算法中的命令式 PriorityQueue

发布于 2024-11-25 01:26:25 字数 488 浏览 2 评论 0原文

我目前有一个方法，使用 scala.collection.mutable.PriorityQueue 按特定顺序组合元素。例如，代码看起来有点像这样：

 def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
   val queue = new scala.collection.mutable.PriorityQueue[A]() ++ as
   while (queue.size > 1) {
     val a1 = queue.dequeue
     val a2 = queue.dequeue
     queue.enqueue(f(a1, a2))
   }
   queue.dequeue
 }

代码按编写的方式工作，但必然是非常命令式的。我想过使用 SortedSet 而不是 PriorityQueue，但我的尝试使该过程看起来更加混乱。什么是更明确、更简洁的方式来做我想做的事情？

原文

I currently have a method that uses a scala.collection.mutable.PriorityQueue to combine elements in a certain order. For instance the code looks a bit like this:

 def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
   val queue = new scala.collection.mutable.PriorityQueue[A]() ++ as
   while (queue.size > 1) {
     val a1 = queue.dequeue
     val a2 = queue.dequeue
     queue.enqueue(f(a1, a2))
   }
   queue.dequeue
 }

The code works as written, but is necessarily pretty imperative. I thought of using a SortedSet instead of the PriorityQueue, but my attempts make the process look a lot messier. What is a more declarative, succinct way of doing what I want to do?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

飞烟轻若梦 2024-12-02 01:26:25

如果 f 不产生 Set 中已有的元素，那么您确实可以使用 SortedSet。（如果是这样，您需要一个不可变的优先级队列。）执行此操作的声明性方法是：

def process[A:Ordering](s:SortedSet[A], f:(A,A)=>A):A = {
  if (s.size == 1) s.head else {
    val fst::snd::Nil = s.take(2).toList
    val newSet = s - fst - snd + f(fst, snd)
    process(newSet, f)
  }
}

If f doesn't produce elements that are already in the Set, you can indeed use a SortedSet. (If it does, you need an immutable priority queue.) A declarative wayto do this would be:

def process[A:Ordering](s:SortedSet[A], f:(A,A)=>A):A = {
  if (s.size == 1) s.head else {
    val fst::snd::Nil = s.take(2).toList
    val newSet = s - fst - snd + f(fst, snd)
    process(newSet, f)
  }
}

回复收藏 0 原文

勿忘初心 2024-12-02 01:26:25

试图改进@Kim Stebel的答案，但我认为命令式变体仍然更清晰。

def process[A:Ordering](s: Set[A], f: (A, A) => A): A = {
  val ord = implicitly[Ordering[A]]
  @tailrec
  def loop(lst: List[A]): A = lst match {
    case result :: Nil => result
    case fst :: snd :: rest =>
      val insert = f(fst, snd)
      val (more, less) = rest.span(ord.gt(_, insert))
      loop(more ::: insert :: less)    
  }
  loop(s.toList.sorted(ord.reverse))
}

Tried to improve @Kim Stebel's answer, but I think imperative variant is still more clear.

def process[A:Ordering](s: Set[A], f: (A, A) => A): A = {
  val ord = implicitly[Ordering[A]]
  @tailrec
  def loop(lst: List[A]): A = lst match {
    case result :: Nil => result
    case fst :: snd :: rest =>
      val insert = f(fst, snd)
      val (more, less) = rest.span(ord.gt(_, insert))
      loop(more ::: insert :: less)    
  }
  loop(s.toList.sorted(ord.reverse))
}

回复收藏 0 原文

归途 2024-12-02 01:26:25

这是使用 SortedSet 和 Stream 的解决方案：

def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
    Stream.iterate(SortedSet.empty ++ as)(  ss => 
        ss.drop(2) + f(ss.head, ss.tail.head))
    .takeWhile(_.size > 1).last.head
}

Here's a solution with SortedSet and Stream:

def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
    Stream.iterate(SortedSet.empty ++ as)(  ss => 
        ss.drop(2) + f(ss.head, ss.tail.head))
    .takeWhile(_.size > 1).last.head
}

回复收藏 0 原文

~没有更多了~