Scala: Tìm kiếm một cách tốt đẹp để tách mảng

Question

Tôi đã tìm kiếm một phương pháp tương tự như String.split trong Scala Array, nhưng tôi không thể tìm thấy nó.

Xin chào tất cả, điều tôi muốn làm là chia mảng bằng dấu phân cách.

Ví dụ, tách các mảng sau:

val array = Array('a', 'b', '\n', 'c', 'd', 'e', '\n', 'g', '\n') 

bằng cách sử dụng '\ n' tách, nên kết quả trong:

List(Array(a, b), Array(c, d, e), Array(g)) 

tôi biết rằng tôi có thể chuyển đổi các Array String, và áp dụng chia ở đó:

array.mkString.split('\n').map(_.toArray) 

nhưng tôi muốn bỏ qua chuyển đổi.

Các giải pháp tôi có cho đến nay liên quan đến việc sử dụng khoảng đệ quy và là một chút quá soạn sẵn:

def splitArray[T](array: Array[T], separator: T): List[Array[T]] = { 
    def spanRec(array: Array[T], aggResult: List[Array[T]]): List[Array[T]] = { 
     val (firstElement, restOfArray) = array.span(_ != separator) 
     if (firstElement.isEmpty) aggResult 
     else spanRec(restOfArray.dropWhile(_ == separator), firstElement :: aggResult) 
    } 
    spanRec(array, List()).reverse 
    } 

Tôi chắc chắn phải có một cái gì đó trong Scala tôi đang thiếu. Bất kỳ ý tưởng?

cảm ơn, Ruben

Answer 1

Tôi không biết về bất kỳ xây dựng trong phương pháp, nhưng tôi đã đưa ra một đơn giản hơn của bạn:

def splitOn[A](xs: List[A])(p: A => Boolean): List[List[A]] = xs match { 
    case Nil => Nil 
    case x :: xs => 
    val (ys, zs) = xs span (!p(_)) 
    (x :: ys) :: splitOn(zs.tail)(p) 
} 

// for Array 
def splitOn[A : reflect.ClassTag](xs: Array[A])(p: A => Boolean): List[Array[A]] = 
    if (xs.isEmpty) List() 
    else { 
    val (ys, zs) = xs.tail span (!p(_)) 
    (xs.head +: ys) :: splitOn(zs.tail)(p) 
    } 

scala> val xs = List('a', 'b', '\n', 'c', 'd', 'e', '\n', 'g', '\n') 
xs: List[Char] = 
List(a, b, 
, c, d, e, 
, g, 
) 

scala> splitOn(xs)(_ == '\n') 
res7: List[List[Char]] = List(List(a, b), List(c, d, e), List(g)) 

Answer 2

Bạn có thể sử dụng phương pháp span chia mảng thành hai phần và sau đó gọi phương thức tách của bạn đệ quy trên phần thứ hai.

import scala.reflect.ClassTag 

def split[A](l:Array[A], a:A)(implicit act:ClassTag[Array[A]]):Array[Array[A]] = { 
    val (p,s) = l.span(a !=) 
    p +: (if (s.isEmpty) Array[Array[A]]() else split(s.tail,a)) 
} 

Điều này không hiệu quả lắm vì nó có hiệu suất bậc hai. Nếu bạn muốn một cái gì đó nhanh chóng, một giải pháp đệ quy đuôi đơn giản có lẽ sẽ là cách tiếp cận tốt nhất.

Với danh sách thay vì mảng, bạn sẽ nhận được hiệu suất tuyến tính và không cần phản ánh.

Answer 3

Đây không phải là triển khai ngắn gọn nhất, nhưng nó phải được thực hiện một cách công bằng và bảo toàn loại mảng mà không cần phải phản ánh. Tất nhiên, vòng lặp có thể được thay thế bằng một đệ quy.

Vì câu hỏi của bạn không tuyên bố rõ ràng những gì nên được thực hiện với dấu phân cách mà tôi cho rằng chúng không được gây ra bất kỳ mục nhập nào trong danh sách đầu ra (xem các trường hợp kiểm tra bên dưới).

def splitArray[T](xs: Array[T], sep: T): List[Array[T]] = { 
    var (res, i) = (List[Array[T]](), 0) 

    while (i < xs.length) {  
    var j = xs.indexOf(sep, i) 
    if (j == -1) j = xs.length 
    if (j != i) res ::= xs.slice(i, j) 
    i = j + 1 
    } 

    res.reverse 
} 

Một số xét nghiệm:

val res1 = 
    // Notice the two consecutive '\n' 
    splitArray(Array('a', 'b', '\n', 'c', 'd', 'e', '\n', '\n', 'g', '\n'), '\n') 

println(res1) 
    // List([C@12189646, [C@c31d6f2, [C@1c16b01f) 
res1.foreach(ar => {ar foreach print; print(" ")}) 
    // ab cde g 


// No separator 
val res2 = splitArray(Array('a', 'b'), '\n') 
println(res2) 
    // List([C@3a2128d0) 
res2.foreach(ar => {ar foreach print; print(" ")}) 
    // ab 


// Only separators 
val res3 = splitArray(Array('\n', '\n'), '\n') 
println(res3) 
    // List() 

Answer 4

Làm thế nào về điều này? Không phản chiếu và không đệ quy hoặc cố gắng sử dụng càng nhiều thư viện scala càng tốt.

def split[T](a: Array[T], sep: T)(implicit m:ClassManifest[T]): Array[Array[T]] = { 
    val is = a.indices filter (a(_) == sep) 
    (0 +: (is map (1+))) zip (is :+ (a.size+1)) map { 
    case(from,till) => a.slice(from, till) 
    } 
} 

Có lẽ chậm, nhưng chỉ để giải trí.:-)

indices filter cung cấp cho bạn các chỉ mục (is) nơi tìm thấy dấu phân cách của bạn. Trong ví dụ của bạn, đó là 2,6,8. Tôi nghĩ rằng đây là O(n).

Dòng tiếp theo biến đổi thành (0,2), (3,6), (7,8), (9, 10). Vì vậy, k dải phân cách có phạm vi k+1. Đây là những bàn giao cho slice, mà phần còn lại của công việc. Chuyển đổi cũng là O(n) trong đó n là số lượng dấu phân cách được tìm thấy. (Điều này có nghĩa là đầu vào của Array[Char]() sẽ mang lại Array(Array()) và không trực quan hơn Array() nhưng điều đó không quá thú vị).

Việc chắp thêm/chuẩn bị mảng (:+, +:) là lãng phí khi sử dụng mảng, nhưng không thể giải quyết bằng cách sử dụng bộ sưu tập phù hợp cho phép bạn có thêm/bổ sung thêm O(1).

Answer 5

Một vay các đối số từ giải pháp sschaef của:

def split[T](array : Array[T])(where : T=>Boolean) : List[Array[T]] = { 
    if (array.isEmpty) Nil 
    else { 
     val (head, tail) = array span {!where(_)} 
     head :: split(tail drop 1)(where) 
    } 
}           //> split: [T](array: Array[T])(where: T => Boolean)List[Array[T]] 


val array = Array('a', 'b', '\n', 'c', 'd', 'e', '\n', 'g', '\n') 

split(array){_ =='\n'}     //> res2: List[Array[Char]] = List(Array(a, b), Array(c, d, e), Array(g)) 

def splitByNewLines(array : Array[Char]) = split(array){_ =='\n'} 
splitByNewLines(array)     //> res3: List[Array[Char]] = List(Array(a, b), Array(c, d, e), Array(g)) 

Answer 6

Đây là một công thức ngắn mà nên thực hiện công việc:

def split(array:Array[Char], sep:Char) : Array[Array[Char]] = { 
    /* iterate the list from right to left and recursively calculate a 
    pair (chars,list), where chars contains the elements encountered 
    since the last occurrence of sep. 
    */ 
    val (chars, list) = array.foldRight[(List[Char],List[Array[Char]])]((Nil,Nil))((x,y) => if (x == sep) (Nil, (y._1.toArray)::y._2) else (x::y._1, y._2) ); 

    /* if the last element was sep, do nothing; 
    otherwise prepend the last collected chars 
    */ 
    if (chars.isEmpty) 
    list.toArray 
    else 
    (chars.toArray::list).toArray 

} 

/* example: 
scala> split(array,'\n') 
res26: Array[Array[Char]] = Array(Array(a, b), Array(c, d, e), Array(g), Array()) 
*/ 

Nếu chúng ta sử dụng Danh sách thay vì mảng, chúng ta có thể khái quát mã một chút:

def split[T](array:List[T], char:T) : List[List[T]] = { 
    val (chars, list) = array.foldRight[(List[T],List[List[T]])]((Nil,Nil))((x,y) => if (x == char) (Nil, (y._1)::y._2) else (x::y._1, y._2) ) 
    if (chars.isEmpty) list else (chars::list) 
} 

/* example: 
scala> split(array.toList, '\n') 
res32: List[List[Char]] = List(List(a, b), List(c, d, e), List(g), List()) 

scala> split(((1 to 5) ++ (1 to 5)).toList, 3) 
res35: List[List[Int]] = List(List(1, 2), List(4, 5, 1, 2), List(4, 5)) 
*/ 

Nếu giải pháp này được coi là thanh lịch hoặc không thể đọc được để lại cho người đọc nd sở thích của mình để lập trình chức năng :)

Answer 7

Bạn cũng có thể thực hiện điều này bằng gấp:

def splitArray[T](array: Array[T], separator: T) = 
    array.foldRight(List(List.empty[T])) { (c, list) => 
     if (c == separator) Nil :: list 
     else (c :: list.head) :: list.tail 
    }.filter(!_.isEmpty).map(_.reverse).toArray 

mà đã được đề cập bởi lambda.xy.x, nhưng vì một lý do đó là một chút ít có thể đọc được thì cần thiết ;)

Answer 8

phiên bản pimped của chung dãy/mảng split -

implicit def toDivide[A, B <% TraversableLike[A, B]](a : B) = new { 
    private def divide(x : B, condition: (A) => Boolean) : Iterable[B] = { 

     if (x.size > 0) 
     x.span(condition) match { 
      case (e, f) => if (e.size > 0) Iterable(e) ++ divide(f.drop(1),condition) else Iterable(f) 
     } 
     else 
     Iterable() 
    } 
    def divide(condition: (A) => Boolean): Iterable[B] = divide(a, condition) 
    }