寻找一种好的方法来拆分一个数组

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

我知道可以将数组转换为字符串,然后在其中应用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中一定有我所不知道的东西。你有什么想法吗?

谢谢, Ruben


那些复杂的解决方案真的值得去避免创建字符串中间变量吗?例如,在数组上调用tail等函数会导致数组通过隐式转换被包装并创建一个新数组。每个传递给高阶函数的函数字面量都需要加载和实例化一个类。将两个序列压缩会为每对元素创建一个Tuple2。我倾向于怀疑任何其他技术都不会比漂亮优雅的array.mkString.split('\n').map(_.toArray)具有更少的开销。 - Randall Schulz
2
当然,如果数组总是一堆字符,那就没什么好说的了。但我认为大多数答案都假定需要一个通用的“split”。例如,Array[Int] 显然会在 mkString 中出现问题:Array(123, 0, 10, 456, 20).mkString.split('0'),而修复它肯定是很麻烦的。 - Faiz
非常感谢您的回答。在我看来,mkString.split选项是最好的选择,但正如Faiz所说,只要数组是字符串(或字符)之一。否则,这里发布的任何解决方案都很不错(除了我的解决方案,它表现得非常糟糕)。 - Ruben
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()

1
我提出了一个解决方案,旨在实现以下目标:
  • 通用性:您应该能够像拆分 Vector 一样拆分 Array,以及像拆分任意对象集合一样拆分 Char 集合。
  • 保留输入类型:一个 Array[A] 被拆分成一个 Array[Array[A]],一个 Vector[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()
  }

}

我使用谓词而不是值来更加灵活地拆分集合,特别是在拆分非标量值(如 Char)的集合时。
我使用集合类型上的隐式视图,以便将其应用于可以被视为 Seq 的所有种类的集合(如 VectorArray),并使用 CanBuildFrom 以便能够构建与输入相同类型的集合。 Iterator 的实现只需确保删除分隔符并将其余部分分块。
我们现在可以使用一个 implicit 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]

}

现在你可以自由地在Char的集合上使用你的方法。
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添加一些返回Iterator的方法,这样您就可以直接通过它公开懒惰的方法。

1
使用foldLeft的简单方法,保留html。
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

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

这种方法效率并不高,因为它具有二次性能。如果你想要快速的解决方案,一个简单的尾递归解决方案可能是最好的选择。

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


1

我借用了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))

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

这个解决方案是否被认为是优雅的或难以阅读的,取决于读者对函数式编程的偏好 :)


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

0
几乎只需要一行代码:
val it = array.iterator
List.range(0, array.count(_ == '\n')).map(_ => it.takeWhile(_ != '\n').toArray)

对于给定的数组,这利用了ArrayIterator版本,以便调用.takeWhile的次数与分隔符的出现次数相同。

另一种版本相对较短,尽管不太易读,使用 List.tabulate,它是对范围的映射:

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

通过使用以下代码对Array进行扩展,可以将其转换为array.mkString.split("\n", -1).map(_.toArray)的通用等效形式:

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

为了消除由于两次连续出现分隔符而导致的空子数组,可以使用管道将结果与 .filter(_.nonEmpty) 结合。


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

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]()将产生Array(Array())而不是更直观的Array(),但这并不太有趣)。

使用数组进行追加/预先设定(:++:)是浪费的,但可以通过使用合适的集合来解决,让您具有O(1)的追加/预先设定。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接