4

私は多次元配列を持っています:

val M = Array.ofDim[Int](V, N)

目標は、有界要素 0 < w0 <= W が存在する最大の V 次元インデックスを見つけ、インデックスと要素値の両方を返すことです。

現在、機能するこのコード スニペットがありますが、これを行うためのより適切で効率的な方法があるかどうか疑問に思っています。

M.zipWithIndex.reverse.collectFirst({
  case (arr, ind) if arr.exists(a => a <= W && a > 0) => {
    arr.zipWithIndex.find(a => a._1 <= W && a._1 > 0) match {
      case Some((weight, ind2)) => (ind, ind2, weight)
    }
  }
})
4

4 に答える 4

5

まあ、他のものとかなり似ていますが、ターゲットを見つけると停止します

def find(M: Array[Array[Int]], W: Int): Option[(Int, Int, Int)] = {
  for {
    x <- M.indices.reverse
    y <- M(x).indices
    a = M(x)(y)
    if 0 < a && a <= W
  } return Some(x, y, a)
  None
}
于 2011-12-07T21:19:56.253 に答える
1

ここでは、命令型または再帰的なソリューションを使用する方が本当に良いでしょう。再帰的なものを書きます：

def finder(arr: Array[Array[Int]], w: Int, i: Int = 0, j: Int = 0): Option[(Int,Int,Int)] = {
  val ri = arr.length-i-1
  if (i >= arr.length) None
  else if (arr(ri)(j) > 0 && arr(ri)(j) < w) Some(ri,j,arr(ri)(j))
  else if (j+1 < arr(i).length) finder(arr,w,i,j+1)
  else finder(arr,w,i+1)
}

次にfinder(M,W)、あなたが望むことをする必要があります。これも効率的であることに注意してください。戻り値以外のボックス化はありません。

編集 - パフォーマンスを気にする場合は、100x100 アレイ上の既存のソリューションのランタイムを次に示します。これには、ソリューションがまったくないか、最後までの 77% で 1 つのソリューションがあります (つまり、ランタイムは約 1/4 である必要があります)。

Original without answer:     65 μs / iteration
Original with answer at 1/4: 18 μs / iteration

元の方法と比較した結果テーブル、相対的な所要時間 (低いほど高速で、-optimise でコンパイルされますが、ほとんど違いはありません):

                  No Answer    1/4 Answer
Original            1.00          1.00
Rex                 0.55          0.72
4e6                 1.95          7.00
missingfaktor       2.41          1.91
Luigi               4.93          3.92

したがって、元の方法は、再帰的な方法を除いて、実際にはすべての提案よりも高速でした。

于 2011-12-07T20:48:30.227 に答える
0

イテレータを書きます。

scala> def itr[A](as: Array[Array[A]]) = new Iterator[(Int, Int, A)] {
     |   private var r = 0 
     |   private var c = -1
     |   def next = {
     |     if(c == as(r).length - 1) {
     |       c = 0
     |       r += 1
     |     } else {
     |       c += 1
     |     }
     |     (r, c, as(r)(c))
     |   }
     |   def hasNext = {
     |     !((r == as.length - 1) && (c == as(r).length - 1))
     |   }
     | }
itr: [A](as: Array[Array[A]])java.lang.Object with Iterator[(Int, Int, A)]

scala> val xs = Array.tabulate(5, 6)(_ + _)
xs: Array[Array[Int]] = Array(Array(0, 1, 2, 3, 4, 5), Array(1, 2, 3, 4, 5, 6), Array(2, 3, 4, 5, 6, 7), Array(3, 4, 5, 6, 7, 8), Array(4, 5, 6, 7, 8, 9))

scala> itr(xs).find { case (_, _, x) => 5 < x && x <= 7 }
res19: Option[(Int, Int, Int)] = Some((1,5,6))
于 2011-12-07T21:22:24.723 に答える
0

@Rexが言ったように、この場合の命令型アプローチはより単純に見えます

scala> val m = Array.tabulate(v,n)(_ + _)
m: Array[Array[Int]] = Array(Array(0, 1, 2, 3), Array(1, 2, 3, 4), Array(2, 3, 4, 5))

scala> for { 
     | i <- v-1 to 0 by -1
     | j <- n-1 to 0 by -1
     | if m(i)(j) > 0 && m(i)(j) < 2
     | } yield (i, j, m(i)(j))
res23: scala.collection.immutable.IndexedSeq[(Int, Int, Int)] = Vector((1,0,1), (0,1,1))

scala> res23.headOption
res24: Option[(Int, Int, Int)] = Some((1,0,1))
于 2011-12-07T20:56:04.650 に答える