Bir 2B dizinin çapraz elemanlarını belirli bir noktadan listelemenin en hızlı yolu

2B dizide, belirli bir nokta için köşegen elemanları Scala'da elde etmenin en hızlı yolu nedir? Öğeleri belirli bir noktadan geçirmek için for döngüsünü basitçe kullanabileceğimi anlıyorum, ancak çok java gibi geliyor. Karşılaştığım yollardan biri, bir sonraki hücreyi hesaplayan argüman olarak bir işlevi kabul eden özyinelemeli bir işlev kullanmaktır. Ancak böyle bir yöntemin çok verimsiz olduğunu hissediyorum. Scala'da diyagonal geçmenin en aptalca yolu nedir?

2

6 cevap

Scala'daki hızlı işlevsel kod genellikle özyinelemeli işlevleri içerir ve hızlı dizi erişimi genellikle dizin oluşturmayı içerir. Yani seçeneklerin sınırlıdır.

Bu durumda,

def diag(xss: Array[Array[Double]]): Array[Double] = {
  val ans = new Array[Double](xss.length)
  @annotation.tailrec def inner(i: Int) {
    if (i < xss.length) {
      ans(i) = xss(i)(i)
      inner(i+1)
    }
  }
  inner(0)
  ans
}

Şahsen, bunu dönüşte karşılık gelenlerden daha az net buluyorum.

def diag(xss: Array[Array[Double]]): Array[Double] = {
  val ans = new Array[Double](xss.length)
  var i = 0
  while (i < xss.length) {
    ans(i) = xss(i)(i)
    i += 1
  }
  ans
}

ancak tercihleriniz değişebilir.

There are optimization frameworks that will take higher-order index traversal (e.g. for (i <- xss.indices) ans(i) = xss(i)(i)) and change it into the while loop. (ScalaBlitz is one.)

4
katma

Scala'daki hızlı işlevsel kod genellikle özyinelemeli işlevleri içerir ve hızlı dizi erişimi genellikle dizin oluşturmayı içerir. Yani seçeneklerin sınırlıdır.

Bu durumda,

def diag(xss: Array[Array[Double]]): Array[Double] = {
  val ans = new Array[Double](xss.length)
  @annotation.tailrec def inner(i: Int) {
    if (i < xss.length) {
      ans(i) = xss(i)(i)
      inner(i+1)
    }
  }
  inner(0)
  ans
}

Şahsen, bunu dönüşte karşılık gelenlerden daha az net buluyorum.

def diag(xss: Array[Array[Double]]): Array[Double] = {
  val ans = new Array[Double](xss.length)
  var i = 0
  while (i < xss.length) {
    ans(i) = xss(i)(i)
    i += 1
  }
  ans
}

ancak tercihleriniz değişebilir.

There are optimization frameworks that will take higher-order index traversal (e.g. for (i <- xss.indices) ans(i) = xss(i)(i)) and change it into the while loop. (ScalaBlitz is one.)

4
katma

İşlevsel programlama ve değişmezlik sadece çok iyi ilerlemek için Kuyruk özyineleme ve Liste gibi değişken veri yapılarını da kullanabilirsiniz. sabit bir zaman alan iki işlem başı ve kuyruğu sunar ve her iki işlemin zaman karmaşıklığı O'dur (1).

 @annotation.tailrec
  def f(arr: List[List[Int]], res: List[Int] = Nil): List[Int] = {
    if (arr.isEmpty) res
    else 
      f(arr.tail.map(_.tail), res :+ arr.head.head)
  }

  val x = List(List(1, 2, 3, 4), List(5, 6, 7, 8), List(9, 10, 11, 12), List(13, 14, 15, 16))

scala> f(x)
res0: List[Int] = List(1, 6, 11, 16)
1
katma

İşlevsel programlama ve değişmezlik sadece çok iyi ilerlemek için Kuyruk özyineleme ve Liste gibi değişken veri yapılarını da kullanabilirsiniz. sabit bir zaman alan iki işlem başı ve kuyruğu sunar ve her iki işlemin zaman karmaşıklığı O'dur (1).

 @annotation.tailrec
  def f(arr: List[List[Int]], res: List[Int] = Nil): List[Int] = {
    if (arr.isEmpty) res
    else 
      f(arr.tail.map(_.tail), res :+ arr.head.head)
  }

  val x = List(List(1, 2, 3, 4), List(5, 6, 7, 8), List(9, 10, 11, 12), List(13, 14, 15, 16))

scala> f(x)
res0: List[Int] = List(1, 6, 11, 16)
1
katma

Sadece eğlence için, bazı (tartışmalı) daha fazla konuşma yapan Scala, köşegen elemanların satırların bir dönmesinden kaynaklandığına dikkat ederek, aşağıdaki gibi kodu kullanabilirsiniz. Olsa da for döngüsü için daha az verimli olacaktır.

def diag(m: Array[Array[Int]]) = {
  val (m1, m2) = m.zipWithIndex.
    map{case (l, i) => val (l1, l2) = splitAt(l.size-i); l1 ++ l2}.
    transpose.zipWithIndex.
    map{case (l, i) => l.splitAt(i+1)}.
    unzip
  m1 ++ m2.init
}
0
katma

Sadece eğlence için, bazı (tartışmalı) daha fazla konuşma yapan Scala, köşegen elemanların satırların bir dönmesinden kaynaklandığına dikkat ederek, aşağıdaki gibi kodu kullanabilirsiniz. Olsa da for döngüsü için daha az verimli olacaktır.

def diag(m: Array[Array[Int]]) = {
  val (m1, m2) = m.zipWithIndex.
    map{case (l, i) => val (l1, l2) = splitAt(l.size-i); l1 ++ l2}.
    transpose.zipWithIndex.
    map{case (l, i) => l.splitAt(i+1)}.
    unzip
  m1 ++ m2.init
}
0
katma