스칼라

Question

의 다차원 배열에서 경계 요소의 최대 인덱스를 가져 I는 다차원 배열을 가지고

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

Answer 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) 당신이 원하는 일을해야한다 : 나는 재귀를 쓸 것이다. 이것은 또한 효율적입니다 - 반환 값을 제외하고는 권투가 없습니다.

---

편집 - 성능에 대해 관심이 있다면, 여기에는 용액 또는 끝으로가는 길의 77 %에서 하나 개의 솔루션이없는 100 × 100 배열의 기존 솔루션의 런타임 (예 : 런타임에 대해해야됩니다 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 

당신의 원래 방법은 실제로 재귀 적 방법을 제외하고 모든 제안보다 빠릅니다. @Rex 말했듯이

Answer 2

,이 경우에 필수적 접근 방식은 다른 사람에게 매우 유사한 간단

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

Answer 3

시큰둥를 보이지만, 그것의 대상에게

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 
} 

Answer 4

내가 쓰기 것을 발견하면 그것을 정지 반복자.

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