假设我有一个看起来像这样的列表:
List(0,5,34,0,9,0,0,0)
我最终想要的是:
List(0,5,34,0,9)
我正在删除所有尾随的零。有没有一种方法,比如:
list.trimRight(_ == 0)
这能实现吗?我可以从头开始编写它,但在我看来,它是 std 集合附带的东西?
我想出了:
list.take(list.lastIndexWhere(_ != 0) + 1)
有更好的方法吗?
如果你想知道哪个最优雅,那么我会说
list.reverse.dropWhile(_ == 0).reverse
因为它只需要引用一次输入,而且意图非常明确。
如果你想知道哪个是最高效,你需要做一些基准测试。 结果(针对您的简短测试列表)可能会让您感到惊讶!
// Slowest
191 ns dhg's EnhancedSeq
173 ns user unknown's custom dropRight
91 ns andyczerwonka's take/lastIndexWhere
85 ns Rex's :\ (foldRight) -- see below
60 ns dhg / Daniel's reverse/dropWhile/reverse
52 ns Rex's customDropTrailingZeros -- see below
// Fastest
机器与机器之间可能存在一些适度的差异,但基本上,在这种情况下,花哨的短列表对您没有帮助。 对于很长的列表,事情可能会发生很大的变化。
这是折叠版本(但堆栈在大列表上溢出):
(list :\ list.take(0)){ (x,ys) => if (x==0 && ys.isEmpty) ys else x :: ys }
这是自定义版本(完全非通用——仅适用于此特定任务!):
@annotation.tailrec def customDropZeros(
xs: List[Int],
buffer: Array[Int] = new Array[Int](16),
n: Int = 0
): List[Int] = {
if (xs.isEmpty) {
var ys = xs
var m = n
while (m>0 && buffer(m-1)==0) m -= 1
var i = m-1
while (i>=0) {
ys = buffer(i) :: ys
i -= 1
}
ys
}
else {
val b2 = (
if (n<buffer.length) buffer
else java.util.Arrays.copyOf(buffer, buffer.length*2)
)
b2(n) = xs.head
customDropZeros(xs.tail, b2, n+1)
}
}
使用
reverse dropWhile reverse
,除非您有充分的理由不这样做。 它出奇的快而且出奇的清晰。
我想我的答案
list.take(list.lastIndexWhere(_ != 0)+1)
就是这样做的方法。
scala> val xs = List(0,5,34,0,9,0,0,0)
xs: List[Int] = List(0, 5, 34, 0, 9, 0, 0, 0)
scala> xs.reverse.dropWhile(_ == 0).reverse
res1: List[Int] = List(0, 5, 34, 0, 9)
编辑:
这是一种一次性 (O(n)) 的方法,它将隐式
dropWhileRight
方法添加到 Seq
class EnhancedSeq[A, Repr <: Seq[A]](seq: SeqLike[A, Repr]) {
def dropRightWhile[That](p: A => Boolean)(implicit bf: CanBuildFrom[Repr, A, That]): That = {
val b = bf(seq.asInstanceOf[Repr])
val buffer = collection.mutable.Buffer[A]()
for (x <- seq) {
buffer += x
if (!p(x)) {
b ++= buffer
buffer.clear()
}
}
b.result
}
}
implicit def enhanceSeq[A, Repr <: Seq[A]](seq: SeqLike[A, Repr]) = new EnhancedSeq(seq)
你只需这样使用它:
scala> List(0,5,34,0,9,0,0,0).dropRightWhile(_ == 0)
res2: List[Int] = List(0, 5, 34, 0, 9)
Scala 中没有这样的方法,并且
List
在更改它的“end”时效率非常低。更喜欢Vector
。
这与
List
配合得相当好(我的其他建议充满了错误,我删除了它):
list.reverse.dropWhile(_ == 0).reverse
您可以遍历列表,并缓冲 0,直到找到一些非 0。如果发现非 0,则将缓冲区附加到到目前为止的结果中,然后继续。但如果你的 List 以 0 结尾,你就会扔掉最后一个缓冲区。
但是 - 最终还是需要一个
reverse
。
val xs = List(0,5,34,0,9,0,0,0)
import annotation._
@tailrec
def dropRight [T] (l: List[T], p: (T=>Boolean), carry: List[T]=List.empty, buf: List[T]=List.empty): List[T] = {
if (l.isEmpty) carry.reverse else
if (p (l.head)) dropRight (l.tail, p, l.head :: buf ::: carry, List.empty) else
dropRight (l.tail, p, carry, l.head :: buf) }
dropRight (xs, (x: Int) => x != 0)
res122: List[Int] = List(0, 5, 34, 0, 9)
如果您对最后的顺序不感兴趣,并且可以省略“反向”调用,那么这可能会很有趣,但为什么您只删除最后一个 T?
基准:
我进一步增加了尺寸,但图案重复了。
如果我们寻找优雅的一句台词,也许这就是。
List(0,1,2).reverse.tail.reverse