Scala: für eine schöne Art und Weise der Suche um ein Array zu spalten

Question

Ich habe für ein ähnliches Verfahren wie String.split in Scala Array suchen, aber ich habe nicht in der Lage gewesen, es zu finden.

Hallo alle, was ich tun möchte, ist ein Array durch ein Trennzeichen zu teilen.

beispielsweise die folgende Anordnung trennt:

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

unter Verwendung des '\ n' Separators sollte ergeben:

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

Ich weiß, dass ich das Array String umwandeln kann, und Anwenden teilen dort:

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

aber ich würde es vorziehen, die Konvertierung zu überspringen.

Die Lösung, die ich bisher habe beinhaltet Spanne mit rekursiv und ist ein bisschen zu vorformulierten:

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 
    } 

Ich bin sicher, dass es etwas in Scala sein muss ich fehle. Irgendeine Idee?

Dank, Ruben

Answer 1

Ich weiß nicht, von jedem Build-In-Verfahren, aber ich kam mit einem einfacheren als Sie up:

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

Sie können die span Methode aufzuspalten das Array in zwei Teile und rufen Sie dann Ihre Split-Methode rekursiv auf den zweiten Teil.

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

Dies ist jedoch nicht sehr effizient, da es quadratische Leistung hat. Wenn Sie etwas schnell wollen, ist eine einfache tail rekursive Lösung wahrscheinlich der beste Ansatz.

Mit Listen anstelle von Arrays würden Sie lineare Leistung erhalten und würden keine Reflexion benötigen.

Answer 3

Dies ist nicht die kompakteste Implementierung, aber es sollte ziemlich durchgeführt werden und erhält den Array-Typ ohne Rückgriff auf Reflexion. Die Schleife kann natürlich durch eine Rekursion ersetzt werden.

Da Ihre Frage nicht explizit angibt, was mit dem Trennzeichen gemacht werden soll, gehe ich davon aus, dass sie keinen Eintrag in der Ausgabeliste verursachen sollte (siehe Testfälle unten).

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 
} 

Einige Tests:

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

Wie wäre das? Keine Reflektion und auch nicht rekursiv, sondern versucht so viel wie möglich von der Scala-Bibliothek zu verwenden.

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

Wahrscheinlich langsam, aber nur zum Spaß.:-)

Die indices filter gibt Ihnen die Indizes (is) von, wo Ihr Trennzeichen gefunden wurde. In Ihrem Beispiel ist das 2,6,8. Ich denke, das ist O(n).

Die nächste Zeile wandelt das in (0,2), (3,6), (7,8), (9, 10) um. So k Separatoren Ausbeute k+1 reicht. Diese werden an slice übergeben, die den Rest der Arbeit erledigt. Die Transformation ist auch O(n), wobei n die Anzahl der gefundenen Separatoren ist. (Dies bedeutet ein Eingang von Array[Char]() wird Array(Array()) ergeben und nicht die intuitivere Array(), aber das ist nicht zu interessant).

Das Array anhängt/Voranstellen (:+, +:) ist verschwenderisch mit Arrays, aber nichts, was nicht durch die Verwendung einer geeigneten Sammelstelle gelöst werden können, die Sie O(1) haben können anhängt/wird vorangestellt.

Answer 5

Ein geliehener die Argumente aus sschaef Lösung:

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

Dies ist eine kurze Formulierung, die die Arbeit tun sollten:

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()) 
*/ 

Wenn wir Liste anstelle von Array, können wir den Code verallgemeinern ein bisschen:

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

Wenn diese Lösung als elegant oder unlesbar gilt, bleibt dem Leser ein nd ihre Vorliebe für die funktionale Programmierung :)

Answer 7

Sie können auch erreichen dies mit fach:

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 

, die bereits von lambda.xy.x erwähnt wurde, aber aus irgendeinem Grund war es ein bisschen weniger lesbar dann notwendig ;)

Answer 8

kuppelte Version der generischen Sequenz/array 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) 
    }