Подтвердить что ты не робот

Scala: поиск хорошего способа разделить массив

Я искал метод, похожий на String.split в массиве Scala, но я не смог его найти.

Привет всем, что я хочу сделать, это разделить массив на разделитель.

Например, разделив следующий массив:

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

используя разделитель '\n', должно получиться:

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

Я знаю, что я могу преобразовать Array в String и применить split там:

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

но я бы предпочел пропустить преобразование.

Решение, которое я до сих пор использует, рекурсивно использует span и немного слишком шаблонный:

  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
  }

Я уверен, что что-то в Scala мне не хватает. Любая идея?

спасибо, Рубен

4b9b3361

ОТВЕТЫ

Ответ 1

Это не самая краткая реализация, но она должна выполняться и сохранять тип массива, не прибегая к отражению. Конечно, цикл можно заменить рекурсией.

Поскольку ваш вопрос не содержит явного указания о том, что должно быть сделано с разделителем, я предполагаю, что они не должны вызывать какую-либо запись в выходном списке (см. ниже примеры тестов).

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
}

Некоторые тесты:

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

println(res1)
  // List([[email protected], [[email protected], [[email protected])
res1.foreach(ar => {ar foreach print; print(" ")})
  // ab cde g


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


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

Ответ 2

Вы можете использовать метод span для разделения массива на две части и затем рекурсивно вызывать метод split во второй части.

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

Это не очень эффективно, поскольку имеет квадратичную производительность. Если вы хотите что-то быстро, возможно, оптимальным будет решение с хвостовым рекурсивным решением.

С списками вместо массивов вы получите линейную производительность и не нуждаетесь в отражении.

Ответ 3

Заимствованные аргументы из решения sschaef:

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

Ответ 4

Я не знаю никакого встроенного метода, но я придумал более простой, чем ваш:

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

Ответ 5

Как насчет этого? Отсутствие отражения, а не рекурсивное, но пытается использовать как можно больше библиотеки scala.

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

Наверное, медленно, но просто для удовольствия.:-)

indices filter дает вам индексы (is) того, где был найден ваш разделитель. В вашем примере это 2,6,8. Я думаю, что это O(n).

Следующая строка преобразует это в (0,2), (3,6), (7,8), (9, 10). Поэтому сепараторы k дают диапазоны k+1. Они передаются slice, что делает остальную часть работы. Преобразование также O(n), где n - количество найденных разделителей. (Это означает, что вход Array[Char]() даст Array(Array()), а не более интуитивный Array(), но это не слишком интересно).

Добавление/добавление массива (:+, +:) бесполезно с использованием массивов, но ничего, что невозможно решить, с помощью соответствующей коллекции, которая позволяет вам иметь O(1) appends/prepends.

Ответ 6

Это краткая формулировка, которая должна выполнять эту работу:

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

Если мы используем List вместо Array, мы можем немного обобщить код:

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

Если это решение считается изящным или нечитаемым, оно остается читателю и предпочитает функциональное программирование:)

Ответ 7

Вы также можете выполнить это, используя fold:

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

о котором уже упоминалось lambda.xy.x, но по какой-то причине он был немного менее читабельным, чем необходимо;)

Ответ 8

Pimped версия общей последовательности/массива 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)
  }