스칼라에는 불평등 한 길이 목록 목록을 전환하는 안전한 방법이 있습니까?

StackOverflow https://stackoverflow.com/questions/1683312

  •  18-09-2019
  •  | 
  •  

문제

다음 목록이 주어지면 :

val l = List(List(1, 2, 3), List(4, 5), List(6, 7, 8))

전환하려고하면 Scala는 다음과 같은 오류를 던집니다.

scala> List.transpose(l)
java.util.NoSuchElementException: head of empty list
    at scala.Nil$.head(List.scala:1365)
    at scala.Nil$.head(List.scala:1362)
    at scala.List$$anonfun$transpose$1.apply(List.scala:417)
    at scala.List$$anonfun$transpose$1.apply(List.scala:417)
    at scala.List.map(List.scala:812)
    at scala.List$.transpose(List.scala:417)
    at .<init>(<console>:6)
    at .<clinit>(<console>)
    at RequestResult...

이 때문입니다 List.transpose 동일 길이 목록을 가정하고 사용합니다 head 방법:

def transpose[A](xss: List[List[A]]): List[List[A]] = {
  val buf = new ListBuffer[List[A]]
  var yss = xss
  while (!yss.head.isEmpty) {
    buf += (yss map (_.head))
    yss = (yss map (_.tail))
  }
  buf.toList
}

다음을 받고 싶습니다.

List(List(1, 4, 6), List(2, 5, 7), List(3, 8))

내 자신의 버전을 쓰고 있습니다 transpose 이것을하는 가장 좋은 방법은? 이것이 제가 생각해 낸 것입니다.

def myTranspose[A](xss: List[List[A]]): List[List[A]] = {
  val buf = new ListBuffer[List[A]]
  var yss = xss
  while (!yss.head.isEmpty) {
    buf += (yss filter (!_.isEmpty) map (_.head))
    yss = (yss filter (!_.isEmpty) map (_.tail))
  }
  buf.toList
}

업데이트: 여기에 제공되는 다양한 솔루션의 속도를 비교하는 데 관심이 있었으므로 다음과 같은 작은 벤치 마크를 구성했습니다.

import scala.testing.Benchmark
import scala.collection.mutable.ListBuffer

trait Transpose extends Benchmark {
  def transpose[Int](xss: List[List[Int]]): List[List[Int]] = Nil
  val list: List[List[Int]] = List(List(1,2,3), Nil, List(4,5,99,100), List(6,7,8))
  def run = {
    val l = transpose(list)
    println(l)
    l
  }
}

object PRTranspose extends Transpose {
  override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = {
    val buf = new ListBuffer[List[Int]]
    var yss = xss
    while (!yss.head.isEmpty) {
      buf += (yss filter (!_.isEmpty) map (_.head))
      yss = (yss filter (!_.isEmpty) map (_.tail))
    }
    buf.toList
  }
}

object ACTranspose extends Transpose {
  override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = {
    val b = new ListBuffer[List[Int]]
    var y = xss filter (!_.isEmpty)
    while (!y.isEmpty) {
      b += y map (_.head)
      y = y map (_.tail) filter (!_.isEmpty)
    }
    b.toList
  }
}

object ETranspose extends Transpose {
  override def transpose[Int](xss: List[List[Int]]): List[List[Int]] = xss.filter(!_.isEmpty) match {    
    case Nil => Nil
    case ys: List[List[Int]] => ys.map{ _.head }::transpose(ys.map{ _.tail })
  }
}

내 명령은 다음과 같습니다.

scala PFTranspose 5 out.log
scala ACTranspose 5 out.log
scala ETranspose 5 out.log

내 결과는 다음과 같습니다.

PRTranspose$            10              0               1               1               0
ACTranspose$            9               2               0               0               0
ETranspose$             9               3               2               3               1
도움이 되었습니까?

해결책

이건 어때:

    scala> def transpose[A](xs: List[List[A]]): List[List[A]] = xs.filter(_.nonEmpty) match {    
         |     case Nil    =>  Nil
         |     case ys: List[List[A]] => ys.map{ _.head }::transpose(ys.map{ _.tail })
         | }
    warning: there were unchecked warnings; re-run with -unchecked for details
    transpose: [A](xs: List[List[A]])List[List[A]]

    scala> val ls = List(List(1, 2, 3), List(4, 5), List(6, 7, 8))
    ls: List[List[Int]] = List(List(1, 2, 3), List(4, 5), List(6, 7, 8))

    scala> transpose(ls)
    res0: List[List[Int]] = List(List(1, 4, 6), List(2, 5, 7), List(3, 8))

    scala> val xs = List(List(1,2,3), List(4,5,99,100), List(6,7,8))
xs: List[List[Int]] = List(List(1, 2, 3), List(4, 5, 99, 100), List(6, 7, 8))

scala> transpose(xs)
res1: List[List[Int]] = List(List(1, 4, 6), List(2, 5, 7), List(3, 99, 8), List(100))

다른 팁

나는 Transpose가 "rectangular"목록에 정의되지 않은 이유가 수학적으로 전환 작업이 "직사각형 구조"에만 잘 정의되어 있기 때문입니다. 전환 작업의 바람직한 속성은 전치 (transpose (x)) == x입니다. 이는 비 의류 목록 목록에서 Transpose 작업을 일반화하는 경우가 아닙니다.

또한 내 게시물을 살펴보십시오 스칼라에서 임의의 수집 수집을 전달합니다 그리고 교회가 아닌 수집 수집을 위해 그것을하는 것에 대해 생각해보십시오. 수학적으로 일관성이없는 정의로 끝나고 혼자 구현을 남깁니다.

본인은 특유의 "Transpose"작업이 종종 유용하다는 데 동의하지만, 정확한 정의와 관련된 잠재적 혼란 때문에 표준 라이브러리에서 제공해서는 안된다고 생각합니다.

나는 모르겠다 (그리고 상상할 수 없다 - 이것은 조금 이상하지 않습니까?!

scala> def transpose(x: List[List[Int]]): List[List[Int]] = {
     |   val b = new ListBuffer[List[Int]]
     |   var y = x filter (!_.isEmpty)
     |   while (!y.isEmpty) {
     |     b += y map (_.head)
     |     y = y map (_.tail) filter (!_.isEmpty)
     |   }
     |   b.toList
     | }

이것은 아마도 가장 깨끗한 것일 것입니다.

def transpose[T](l: List[List[T]]): List[List[T]] =
     l.flatMap(_.headOption) match {
         case Nil => Nil
         case head => head :: transpose(l.map(_.drop(1)))
     }

또는 훨씬 더 효율적인 수정 된 버전 :

def transpose[T](l: List[List[T]]): List[List[T]] =
     l.flatMap(_.headOption) match {
         case Nil => Nil
         case head => head :: transpose(l.collect { case _ :: tail => tail })
     }

Scala의 표준 API를 사용하는이 1 라이너는 어떻습니까 :

((l map (_.toArray)) toArray).transpose map (_.toList) toList

이것은 일을 끝내고 있습니다 O(N*M), 어디 N 래퍼 목록의 길이입니다 M 래퍼 목록 내에서 가장 긴 목록의 길이입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top