logo标签列表

Scala：将列表分成多个部分

listscala
3

假设我有一个元组列表...

val l: List[(String, String, Date)]

...这个列表按日期排序...

val sorted = l.sortWith((a, b) => a._3 < b._3 )

现在我想把这个已排序的列表分成多个列表。拆分应该发生在日期差大于3天的元组之间。有什么好的和高效的方法来做到这一点呢？
谢谢和问候！
编辑：
以下是一个示例： 输入（已排序）：
List(("a1", "b1", "2016-01-30"), ("a2", "b2", "2016-02-01"), ("a3", "b3", "2016-02-20"), ("a4", "b4", "2016-02-23"), ("a5", "b5", "2016-02-25"))
期望输出：
List(List(("a1", "b1", "2016-01-30"), ("a2", "b2", "2016-02-01")), List(("a3", "b3", "2016-02-20"), ("a4", "b4", "2016-02-23"), ("a5", "b5", "2016-02-25")))
1
你能给出不同情况下的预期输出吗？ - undefined
2
使用sortBy(_._3)替代sortWith - undefined
val sorted = List(l.sortBy(_._3))排序完成的列表 - undefined
1
可能是根据相邻元素之间的差异拆分Scala列表的重复问题。 - undefined
4个回答
3

哎呀，如果这是一个聚会，我也可以发表一下我的看法。

sorted.init.foldRight(List(List(sorted.last))){ (tup,acc) => 
  if (acc.head.head._3 - tup._3 > /*test for time-gap here*/) 
    List(tup)::acc  // gap too big, start new sub-List
  else
    (tup::acc.head)::acc.tail  // prepend to current sub-List
}
非常感谢您提供这个非常简洁而优雅的解决方案！ - undefined
0

我稍微简化了类型，代码只是为了说明概念。性能可能会更好，不使用 toList 转换。

type MyTuple = (String, Int)

val sorted: List[MyTuple] = List(
    ("a", 1),
    ("a", 2),
    ("a", 3),
    ("b", 7),
    ("b", 9),
    ("c", 13),
    ("c", 15),
    ("c", 16)
)

def test(a: MyTuple, b: MyTuple): Boolean = b._2 - a._2 > 3

// We prepend the head so that the first sliding pair will have distance 0
val lists = (sorted.head :: sorted)
  .sliding(2)
  .map { case List(a, b) => (b, test(a, b)) }
  .toList

def split(list: List[(MyTuple, Boolean)]): List[List[MyTuple]] = list match {
  case Nil => Nil
  case head :: tail => {
    val (l1, l2) = tail.span(!_._2)
    (head :: l1).map(_._1) :: split(l2)
  }
}

val splitLists = split(lists).map(_.map(_._1))
println(splitLists.mkString("\n"))

输出：

List(a, a, a)
List(b, b)
List(c, c, c)
0

为了方便起见，我用整数代替日期，但原理是相同的。

   val data = List(
      ("a","a", 10),
      ("a","b", 30),
      ("a","b", 11),
      ("a","b", 33),
      ("s","c", 37),
      ("a","c", 26),
      ("a","d", 22),
      ("m","a", 18),
      ("t","a", 15)
    )
    val sortedData = data.sortWith ((a,b)=> a._3 < b._3)
    println(s"$sortedData")
    val splitPass = sortedData.foldLeft(List[(String, String,Int)](), List[List[(String, String,Int)]](), sortedData.head._3){
      case ((cl, acc, ld),nt) =>
        if (nt._3-ld>3)
          (List(nt), cl.reverse ::acc, nt._3)
        else
          (nt:: cl, acc, nt._3)
    }
    val (fl, fa, _) = splitPass
    val res = (if (fl.isEmpty) fa else fl :: fa).reverse
    println(s"$res")

这将返回已排序的列表：
List((a,a,10), (a,b,11), (t,a,15), (m,a,18), (a,d,22), (a,c,26), (a,b,30), (a,b,33), (s,c,37))

和结果列表：

List(List((a,a,10), (a,b,11)), List((t,a,15), (m,a,18)), List((a,d,22)), List((a,c,26)), List((a,b,30), (a,b,33)), List((s,c,37)))

这个程序的作用是对排序后的列表进行一次遍历，构建一个累加器，其中包括（当前组中的项目列表、已完成组的列表、最后添加项目的日期）。初始时，累加器包含两个空列表和列表中第一个项目的日期。
对于源列表中的每个项目，如果它与前一个项目接近，则将其添加到当前组；如果它与前一个项目相距较远，则关闭当前组并将其添加到已完成组的列表中，并将当前项目成为新列表中的第一个项目，当前项目的日期成为下一次检查的参考日期。如果您想在日期与当前组中最早日期不同时中断，只需将else分支更改为传递ld而不是nt._3。
最后，您需要将任何未完成的组添加到最终的组合集中。
两个“.reverse”是必要的，因为列表按照典型的函数式风格是反向构建的（因为这样更便宜），并在完成后被反转。
使用foldRight而不是foldLeft可以避免需要反转任何东西的需求。 - undefined
@Jubobs，不完全是这样，只是将reverse发生的位置移动了一下。override def foldRight[B](z: B)(op: (A, B) => B): B = reverse.foldLeft(z)((right, left) => op(left, right))（来自 https://github.com/scala/scala/blob/v2.11.8/src/library/scala/collection/immutable/List.scala#L1） - undefined
0
这里是一个非常干净的线性时间（一遍扫描）方法：
type Date = Int  // For simplicity in the example

val sorted: List[(String,String,Date)] = List(("a1", "b1", 1),
                                              ("a1", "b1", 2),
                                              ("a1", "b1", 6),
                                              ("a1", "b1", 8),
                                              ("a1", "b1", 10),
                                              ("a1", "b1", 15),
                                              ("a1", "b1", 16))

val result = sorted.sliding(2).foldLeft(Vector(Vector(sorted.head))) { 
  case (z, List(t1, t2)) => 
    if (t2._3 - t1._3 > 3) z :+ Vector(t2)
    else                   z.init :+ (z.last :+ t2)
}

result.foreach(println)
// Vector((a1,b1,1), (a1,b1,2))
// Vector((a1,b1,6), (a1,b1,8), (a1,b1,10))
// Vector((a1,b1,15), (a1,b1,16))

你可以分别处理 sorted.length() < 2 的特殊情况。

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