以有序的方式合并 Scala 中的两个序列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19444127/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Merging two sequences in scala in an orderly fashion
提问by Core_Dumped
I am trying to merge two sequences such that they remain sorted. The following is the code that I have written:
我试图合并两个序列，使它们保持排序。以下是我编写的代码：
val seq1 = Seq(1,3,5,7,9)
val seq2 = Seq(2,4,6,8)
var arr = Seq[Int]()
for(b <- seq2)
{
for(a <- seq1)
{
if(a < b)
arr = arr :+ a
else
{
arr = arr :+ b;break;
}
}
}
println(arr)
the output that I require needs to be :
我需要的输出需要是：
Seq(1,2,3,4,5,6,7,8,9)
But it seems break does not work in Scala. I am relatively new to the language. What would be the best way to carry out this operation?
但似乎 break 在 Scala 中不起作用。我对这门语言比较陌生。执行此操作的最佳方法是什么？
回答by Jean-Philippe Pellet
The simplest way would probably be this:
最简单的方法可能是这样的：
(seq1 ++ seq2).sorted
If seq1and seq2contain some other type, you'll have to provide an Orderingfor that type; or, alternatively, use the sortBymethod, mapping each element to an element of another type for which an Orderingcan implicitly be found:
如果seq1和seq2包含其他类型，则必须Ordering为该类型提供一个；或者，或者，使用该sortBy方法，将每个元素映射到Ordering可以隐式找到的另一种类型的元素：
(seq1 ++ seq2).sortBy(_.toDate)
回答by CaringDev
The following also works for non-interleaved sequences:
以下内容也适用于非交错序列：
def mergeSorted[E: Ordering](x: Seq[E], y: Seq[E]): Seq[E] = {
val ordering = implicitly[Ordering[E]]
@tailrec
def rec(x: Seq[E], y: Seq[E], acc: Seq[E]): Seq[E] = {
(x, y) match {
case (Nil, Nil) => acc
case (_, Nil) => acc ++ x
case (Nil, _) => acc ++ y
case (xh :: xt, yh :: yt) =>
if (ordering.lteq(xh, yh))
rec(xt, y, acc :+ xh)
else
rec(x, yt, acc :+ yh)
}
}
rec(x, y, Seq())
}
Please note that for performance reasons you'd probably use Builders (vs. :+, +:, reverse).
请注意，出于性能原因，您可能会使用 Builders（与 :+、+:、反向）。
回答by Shastick
I was happy to find @CaringDev's solution and to adapt it to use a Builder:
我很高兴找到@CaringDev 的解决方案并将其调整为使用Builder：
def mergeSortedBuilder[E: Ordering](x: Seq[E], y: Seq[E])(implicit ordering: Ordering[E]): Seq[E] = {
@tailrec
def rec(x: Seq[E], y: Seq[E], acc: Builder[E, Seq[E]]): Builder[E, Seq[E]] = {
(x, y) match {
case (Nil, Nil) => acc
case (_, Nil) => acc ++= x
case (Nil, _) => acc ++= y
case (xh :: xt, yh :: yt) =>
if (ordering.lteq(xh, yh))
rec(xt, y, acc += xh)
else
rec(x, yt, acc += yh)
}
}
rec(x, y, Seq.newBuilder).result
}
回答by Shadowlands
To interleave two sequences while maintaining their individual ordering, you can use:
要在保持各自顺序的同时交错两个序列，您可以使用：
scala> seq1.zip(seq2).flatMap(pair => Seq(pair._1,pair._2))
res1: Seq[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)
Note, however, that for sequences of unequal length this loses the extra elements of the longer sequence. That can be sorted out with a bit more effort (find the longer of the two lists, and add longer.drop(shorter.length)).
但是请注意，对于不等长的序列，这会丢失较长序列的额外元素。这可以通过更多的努力来解决（找到两个列表中较长的一个，然后添加longer.drop(shorter.length)）。
回答by Keith Nordstrom
If you want to interleave an arbitrary number of sequences in order, you can use something like
如果要按顺序交错任意数量的序列，可以使用类似
implicit class Interleave[T](input: Seq[Seq[T]]) {
def interleave: Seq[T] = {
input.foldLeft(Seq[Seq[T]]()) { (acc, cur) =>
if (acc.isEmpty) cur.map { m => Seq(m) }
else (acc zip cur).map { case (sequence, m) =>
sequence :+ m
}
}.flatten.toVector
}
}
It may be possible to improve the performance on this, particularly as the toVectoris there primarily to transform the stream into something eager.
有可能在这方面提高性能，特别是因为toVector它主要是为了将流转换为渴望的东西。
Usage looks something like
用法看起来像
Seq(Seq(1,2), Seq(2,3), Seq(3,4)).interleave should be(Seq(1,2,3,2,3,4))
