斯卡拉：拆分列表成多個部分

Question

假設我有一個元組列表...

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

......這個名單被按日期排序...

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

，現在我想將這個排序的列表分成多個列表。拆分應該在日期差異大於3天的元組之間發生。什麼是一個好的和高性能的方式來做到這一點？

感謝和問候！

編輯：

下面是一個例子： 輸入（已排序）：

列表（（ 「A1」， 「B1」， 「2016年1月30日」）， （「a2」，「b2」，「2016-02-01」），（「a3」，「b3」， 「2016-02-20」），（「a4」，「b4」，「2016-02 -23 「），（」 A5" ， 「B5」， 「2016年2月25日」））

預期輸出：

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 「）））

Answer 1

嘖嘖，如果這是派對，我可能會把我的2分錢左右。

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 
} 

Answer 2

我簡化了一下類型，代碼只是說明了這個概念。如果沒有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) 

Answer 3

爲了方便，我已經爲取代的INTS的日期，但prinicpal是一樣的。

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

這樣做什麼是單次通過排序列表，建立由累加器（當前組中的項目列表，已完成組列表，最後添加項目的Int [日期]）。這是播種兩個空列表和列表中的第一個項目的日期。

對於源列表中的每個項目，如果它接近前一個項目，則將其添加到當前組，如果它遠離前一項目，則當前組將關閉並添加到已完成的gorups列表中，並且當前項目變成新列表中的第一項，並且當前項目的日期成爲下一次檢查的參考日期。如果你想打破日期不同於當前組中最早的日期，很容易改變else分支來傳遞ld而不是nt._3。

最後，您需要將任何未完成的組添加到組的最終集合中。

這兩個'.reverse'是必需的，因爲這些列表在典型的功能風格中是倒退的（因爲它更便宜），並在完成時倒過來。

Answer 4

這是一個非常乾淨的線性時間（單通）的方法：

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分開。