14

我一直在 Scala Array中寻找类似于String.split的方法,但一直没能找到。

我想要做的是用分隔符分割数组。

例如,分隔以下数组:

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

使用'\n'分隔符,应导致:

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

我知道我可以将数组转换为字符串,并在那里应用拆分:

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 中一定有我遗漏的东西。任何想法?

谢谢,鲁本

4

11 回答 11

3

这不是最简洁的实现,但它应该被公平地执行并保留数组类型而不求助于反射。循环当然可以用递归代替。

由于您的问题没有明确说明我假设的分隔符应该做什么,因此它们不应导致输出列表中的任何条目(请参阅下面的测试用例)。

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([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()
于 2013-01-11T13:39:52.813 回答
1

您可以使用该span方法将数组拆分为两部分,然后在第二部分递归调用您的拆分方法。

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

但是,这不是很有效,因为它具有二次性能。如果你想要快速的东西,一个简单的尾递归解决方案可能是最好的方法。

使用列表而不是数组,您将获得线性性能并且不需要反射。

于 2013-01-11T13:20:16.317 回答
1

这是一个简短的公式,应该可以完成这项工作:

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

如果这个解决方案被认为是优雅的或不可读的,留给读者和她对函数式编程的偏好:)

于 2013-01-11T17:54:13.373 回答
1

A 从 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))
于 2013-01-11T14:21:09.247 回答
1

我想出了一个针对以下目标的解决方案:

  • 是通用的:您应该能够Array像 a 一样拆分 aVectorChars 的集合,就像任意对象的集合一样
  • 保留输入的类型:anArray[A]在 an中拆分Array[Array[A]],aVector[A]在 a 中拆分Vector[Vector[A]]
  • 允许在需要时使用惰性方法(通过Iterator
  • 在大多数情况下公开一个紧凑的接口(只需split在您的集合上调用一个方法)

在开始解释之前,请注意您可以在 Scastie 上使用下面的代码。

第一步是实现一个分Iterator的集合:

import scala.language.higherKinds
import scala.collection.generic.CanBuildFrom

final class Split[A, CC[_]](delimiter: A => Boolean, as: CC[A])(
    implicit view: CC[A] => Seq[A], cbf: CanBuildFrom[Nothing, A, CC[A]])
    extends Iterator[CC[A]] {

  private[this] var it: Iterator[A] = view(as).iterator

  private def skipDelimiters() = {
    it = it.dropWhile(delimiter)
  }

  skipDelimiters()

  override def hasNext: Boolean = it.hasNext

  override def next(): CC[A] = {
    val builder = cbf()
    builder ++= it.takeWhile(!delimiter(_))
    skipDelimiters()
    builder.result()
  }

}

我使用谓词而不是值来更灵活地拆分集合的方式,尤其是在拆分非标量值(如Chars)的集合时。

我正在对集合类型使用隐式视图,以便能够将其应用于可以被视为Seq(如Vectors 和Arrays)的所有类型的集合,并且CanBuildFrom能够构建我收到的集合的确切类型作为输入。

的实现Iterator只是确保删除分隔符并将其余部分分块。

我们现在可以使用 animplicit class来提供一个友好的接口并将该split方法添加到所有集合中,都允许将谓词或值定义为分隔符:

final implicit class Splittable[A, CC[_]](val as: CC[A])(implicit ev1: CC[A] => Seq[A], ev2: CanBuildFrom[Nothing, A, CC[A]], ev3: CanBuildFrom[Nothing, CC[A], CC[CC[A]]]) {

  def split(delimiter: A => Boolean): CC[CC[A]] = new Split(as)(delimiter).to[CC]

  def split(delimiter: A): CC[CC[A]] = new Split(as)(_ == delimiter).to[CC]

}

现在您可以在收集Chars时自由使用您的方法

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

a.split('\n')
b.split('\n')
c.split('\n')
d.split('\n')
e.split('\n')

和任意对象:

final case class N(n: Int, isDelimiter: Boolean)

Vector(N(1, false), N(2, false), N(3, true), N(4, false), N(5, false)).split(_.isDelimiter)

请注意,通过直接使用迭代器,您使用的是惰性方法,因为您可以查看是否向next方法添加了调试打印并尝试执行以下操作:

new Split(Vector('\n', 'c', 'd', 'e', '\n', 'g', '\n'))(_ == '\n'}).take(1).foreach(println)

如果您愿意,您可以添加几个方法来Splittable返回 an Iterator,这样您也可以直接通过它公开惰性方法。

于 2018-08-09T08:21:47.990 回答
1

使用 foldLeft 的简单方法

val f =  array.foldLeft((Array[Char](),List[Array[Char]]()))(
  (acc, char: Char) => {
    char match {
      case '\n' => (Array(),acc._1 :: acc._2)
      case _ => (acc._1 :+ char,acc._2)
    }
  }
)._2.reverse
于 2018-05-23T11:21:59.657 回答
0

我不知道任何内置方法,但我想出了一个比你更简单的方法:

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))
于 2013-01-11T13:02:50.693 回答
0

这个怎么样?没有反射,也没有递归,但尝试尽可能多地使用 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]()will yieldArray(Array())而不是更直观Array(),但这不是太有趣)。

数组追加/前置(:+, +:)使用数组是浪费的,但没有什么不能通过使用允许您O(1)追加/前置的适当集合来解决。

于 2013-01-11T14:03:28.050 回答
0

您也可以使用折叠来完成此操作:

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 已经提到了这一点,但由于某种原因,它的可读性不如必要;)

于 2013-11-22T12:33:48.363 回答
0

几乎是单线:

val it = array.iterator
List.range(0, array.count(_ == '\n')).map(_ => it.takeWhile(_ != '\n').toArray)

对于给定的array,这使用了一个Iterator版本的Arrayorder 来调用.takeWhile与分隔符的出现次数一样多的次数。


另一个版本虽然更短但可读性更短,使用List.tabulate它是一个范围内的地图:

val it = array.iterator
List.tabulate(array.count(_ == '\n'))(_ => it.takeWhile(_ != '\n').toArray)

这可以array.mkString.split("\n", -1).map(_.toArray)通过拉皮条制成一个通用的等价物Array

implicit class ArrayExtensions[T: ClassTag](array: Array[T]) {

  def split(sep: T): List[Array[T]] = {
    val it = array.iterator
    List.range(0, array.count(_ == sep)).map(_ => it.takeWhile(_ != sep).toArray)
  }
}

并以这种方式使用:

Array('\n', '\n', 'a', 'b', '\n', 'c', 'd', 'e', '\n', 'g', '\n').split('\n')
// List(Array(), Array(), Array(a, b), Array(c, d, e), Array(g), Array())

为了摆脱由 2 次连续出现分隔符产生的空子数组,可以使用.filter(_.nonEmpty).

于 2018-07-23T22:30:59.307 回答
0

通用序列/数组拆分的拉皮条版本 -

  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)
  }
于 2015-12-19T05:02:12.577 回答