9

次のようなリストがあるとします。

List(0,5,34,0,9,0,0,0)

私が終わらせたいのは：

List(0,5,34,0,9)

末尾のゼロをすべて削除しています。次のような方法がありますか？

list.trimRight(_ == 0)

それはそれを達成しますか？ゼロから書くこともできますが、標準コレクションに付属しているように思えますか?

私が思いついた：

list.take(list.lastIndexWhere(_ != 0) + 1)

より良いアプローチはありますか？

4

5 に答える 5

15

どれが最もエレガントか知りたい場合は、

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)
  }
}

tl;dr

reverse dropWhile reverse正当な理由がない限り使用してください。驚くほど速く、驚くほどクリアです。

于 2012-05-23T00:11:03.097 に答える
6

私の答えはlist.take(list.lastIndexWhere(_ != 0)+1)それを行う方法だと思います。

于 2012-05-22T22:31:27.000 に答える
3 
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)

編集：

dropWhileRightこれは、暗黙のメソッドを追加するワンパス（O（n））の方法です。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)
于 2012-05-22T22:17:04.820 に答える
3

Scalaにはそのような方法はなく、List「終了」を変更する場合は非常に非効率的です。優先しVectorます。

これはかなりうまく機能しますList（私の他の提案はエラーでいっぱいでした、そして私はそれを削除しました）：

list.reverse.dropWhile(_ == 0).reverse
于 2012-05-22T22:32:53.677 に答える
1

リストをトラバースして、0以外の値が見つかるまで0をバッファリングできます。0以外が見つかった場合は、これまでの結果にバッファーを追加して先に進みます。ただし、リストが0で終わる場合は、最後のバッファーを破棄します。

しかし-結局のところ、areverseはまだ必要です。

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だけを削除するのでしょうか。

基準： ベンチマーク図

さらにサイズを大きくしましたが、パターンが繰り返されました。

更新：かなりパフォーマンスの高いdhgのアルゴリズムが含まれています。

于 2012-05-22T23:12:32.330 に答える