Có cách nào an toàn trong Scala để chuyển đổi một Danh sách các danh sách dài bất bình đẳng không?

Question

Với Danh sách sau đây:

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

Nếu tôi cố gắng transpose nó, Scala sẽ ném các lỗi sau:

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

Điều này là do List.transpose giả danh sách bằng độ dài và do đó sử dụng phương pháp 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 
} 

Tôi muốn nhận các thông tin sau:

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

Đang viết phiên bản riêng của mình là transpose cách tốt nhất để làm điều này? Đây là những gì tôi đã đưa ra:

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 
} 

Cập nhật: tôi đã quan tâm đến việc so sánh tốc độ của các giải pháp khác nhau được cung cấp ở đây, vì vậy tôi đặt lại với nhau ít điểm chuẩn sau:

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

My lệnh là:

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

kết quả của tôi là:

PRTranspose$   10    0    1    1    0 
ACTranspose$   9    2    0    0    0 
ETranspose$    9    3    2    3    1 

Answer 1

Làm thế nào về điều này:

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

Answer 2

Tôi không biết (và không thể tưởng tượng - điều này có hơi lạ không ?! [Xem thảo luận trong ý kiến]) là một chức năng thư viện, nhưng tôi có thể đánh bóng mã một chút:

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

Answer 3

tôi nghi ngờ lý do chuyển vị không được xác định trên cơ sở "phi - Hình chữ nhật "danh sách các danh sách là bởi vì toán học hoạt động transpose được xác định rõ chỉ trên" cấu trúc hình chữ nhật ". Một thuộc tính mong muốn của một thao tác chuyển vị là transpose (transpose (x)) == x. Đây không phải là trường hợp tổng quát hóa hoạt động chuyển đổi của bạn trên danh sách các danh sách không phải hình chữ nhật.

Ngoài ra, hãy xem bài đăng của tôi trên Transposing arbitrary collection-of-collections in Scala và suy nghĩ về cách làm cho bộ sưu tập không phải hình chữ nhật. Bạn sẽ kết thúc với định nghĩa toán học không nhất quán, để lại các triển khai một mình.

Tôi đồng ý rằng các hoạt động "chuyển vị" riêng biệt thường hữu ích, nhưng tôi cũng nghĩ rằng chúng không được cung cấp trong thư viện chuẩn vì có khả năng nhầm lẫn về định nghĩa chính xác của chúng.

Answer 4

Đây có lẽ là sạch nhất:

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

hoặc một phiên bản sửa đổi mà thậm chí còn hiệu quả hơn:

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

Answer 5

Làm thế nào về vấn đề này một lót bằng Api tiêu chuẩn của Scala:

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

Việc này được thực hiện và là O(N*M), trong đó N là độ dài của danh sách trình bao bọc và M là độ dài của danh sách dài nhất trong danh sách trình bao bọc.