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/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

正如@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 回答
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 回答