Scala弹出堆栈等效

yuvru6vn  于 2023-10-18  发布在  Scala
关注(0)|答案(2)|浏览(121)

我需要从大约20个列表的列表中按顺序对相似(按id)信息的行进行分组。在SQL中,它被称为join
为了达到这个目的,我想从一个基于id相等的排序列表的头部弹出元素,将它们添加到当前行,剩下的留待以后处理。
一个人为的例子,这样一个弹出一个单一的列表(或表,如果你愿意)将如下:

import scala.collection.mutable.Stack

val ss = Stack(1,1,2,3,4,5,6,7,8,9)

@annotation.tailrec
def retAll(ss: Stack[Int], x: Int, out: List[Int] = List()): List[Int] = {
    if (ss.head == x) {
        val h = ss.pop
        retAll(ss, x, h +: out)
    }
    else out
}

println(retAll(ss, 1))
println(ss)

// List(1, 1)
// Stack(2, 3, 4, 5, 6, 7, 8, 9)

这意味着下一次我将从栈头左侧检索2
我想知道是否存在一种更惯用或更有效的方法来获得相同的结果,更重要的是,如果这个结构可以在以后通过Futures(例如,假设ss是可变的)并行化?

cqoc49vn

cqoc49vn1#

你能不能只使用一个List,并使用效率list.head(在我的例子中隐藏在span中)作为你的pop操作?
为了在变更引用时确保线程安全,可以将其 Package 在java.util.concurrent.atomic.AtomicReference中。

import java.util.concurrent.atomic.AtomicReference

val ss = AtomicReference(List(1,1,2,3,4,5,6,7,8,9))

def retAll(stack: AtomicReference[List[Int]], x: Int): List[Int] = {
    val ( popped, remainder ) = stack.get.span(_ == x)     
    if (popped.nonEmpty) stack.set(remainder)
    popped
}

println(retAll(ss, 1))
println(ss)

// List(1, 1)
// List(2, 3, 4, 5, 6, 7, 8, 9)

@GaëlJ在评论中提出了一个很好的观点。即使引用是原子的,get和set也是不同的操作,并发线程可能会交叉使用它们,从而产生不良影响。
处理线程安全的最可靠的方法可能是使用老式的同步将对列表的所有访问和变化保持在锁后面。也就是说,如果retAll是唯一访问列表的操作,或者如果你对所有其他操作都做了类似的工作,一个更正确的版本可能是:

import java.util.concurrent.atomic.AtomicReference

val ss = AtomicReference(List(1,1,2,3,4,5,6,7,8,9))

def retAll(stack: AtomicReference[List[Int]], x: Int): List[Int] = {
    var out : List[Int] = null // var in a single-threaded local context is okay
    stack.updateAndGet { list =>
      val ( popped, remainder ) = list.span(_ == x)
      out = popped
      remainder
    }
    out
}

println(retAll(ss, 1))
println(ss)

// List(1, 1)
// List(2, 3, 4, 5, 6, 7, 8, 9)

它比原始的但不太线程安全的解决方案稍逊一筹。
这是一个老式的同步“艾德版本:

class QueueManager {
  // protected by this' lock
  private var ss = List(1,1,2,3,4,5,6,7,8,9)

  def current : List[Int] = this.synchronized(ss)

  def retAll(x: Int): List[Int] = this.synchronized {
    val ( popped, remainder ) = ss.span(_ == x)
    this.ss = remainder
    popped
  }
}

val qm = new QueueManager
qm.synchronized {
  println(qm.retAll(1))
  println(qm.current)
}

// List(1, 1)
// List(2, 3, 4, 5, 6, 7, 8, 9)
p5cysglq

p5cysglq2#

首先,我完全同意GaelJ在评论中提到的。但是mutable.Stack上的popWhile基本上做同样的事情:

val whatever = ss.popWhile(_ == x)
println(whatever)
println(ss)

// List(1, 1)
// Stack(2, 3, 4, 5, 6, 7, 8, 9)

根据你的问题中提供的例子,我还可以建议以下不会改变堆栈的方法:

val whatever = ss.dropWhile(_ < x).takeWhile(_ == x).toList
// ss wouldn't change

如果您只想执行group by操作:

println(ss.toList.groupBy(identity))
// Map[Int, List[Int]] = HashMap(
  5 -> List(5),
  1 -> List(1, 1),
  6 -> List(6),
  9 -> List(9),
  2 -> List(2),
  7 -> List(7),
  3 -> List(3),
  8 -> List(8),
  4 -> List(4)
)

相关问题