効率的にオーバーラップするJodaTimeインターバルを見つける

Question

私はSeqのインターバルを持っており、オーバーラップしたもの同士を互いに崩壊させたいと思っています。 私はこれを書いた：

val today = DateTime.now() 
val a: Seq[Interval] = Seq(
    new Interval(today.minusDays(11), today.minusDays(10)), //1 day interval ending 10 days ago 
    new Interval(today.minusDays(10), today.minusDays(8)), //2 day interval ending 8 days ago, overlaps with above 
    new Interval(today.minusDays(7), today.minusDays(5)), //2 day interval ending 5 days ago, DOES NOT OVERLAP 
    new Interval(today.minusDays(4), today.minusDays(1)), //3 day interval ending 1 day ago, DOES NOT OVERLAP above 
    new Interval(today.minusDays(4), today) //4 day interval ending today, overlaps with above 
) 
val actual = a.sortBy(_.getStartMillis).foldLeft(Seq[Interval]())((vals, e) => { 
    if (vals.isEmpty) { 
    vals ++ Seq(e) 
    } else { 
    val fst = vals.last 
    val snd = e 
    if (snd.getStart.getMillis <= fst.getEnd.getMillis) /*they overlap*/ { 
     vals.dropRight(1) ++ Seq(new Interval(fst.getStart, snd.getEnd)) //combine both into one interval 
    } else { 
     vals ++ Seq(e) 
    } 
    } 
}) 
val expected = Seq(
    new Interval(today.minusDays(11), today.minusDays(8)), 
    new Interval(today.minusDays(7), today.minusDays(5)), 
    new Interval(today.minusDays(4), today) 
) 
println(
    s""" 
    |Expected: $expected 
    |Actual : $actual 
    """.stripMargin) 
assert(expected == actual) 

これは働いています。私の最初の懸念は、私がdropRightがO(n - m)どこn = |vals|この場合のm = 1である疑いがある行 vals.dropRight(1) ++ Seq(new Interval(fst.getStart, snd.getEnd))

していました。

|a|が数十万以上のオーダーの場合、この実装は高価になります。実際にvals ++ Seq(e)も、それぞれa[i]に対してn + 1の場合に問題になります。

まず、私の評価は正しいですか？

第2に、変更可能なデータ構造なしでこれを書くより効率的な方法がありますか？

実際のアプリケーションが使用されている文脈からこれを書きましたが、実際のアプリケーションはSparkジョブにあります（foldLeftはRDD[MyType]に折りたたまれます）。

EDIT：完全RDDにはfoldLeftはありません忘れてしまった（スパークを無視し、私は別の方法を考える必要がありますが、私はまだこの答えに興味があり、マイナスの事実は、それはスパークに動作しません。 ）

Answer 1

spire math libraryのIntervalSeq [A]とIntervalTrie [A]データ構造を見てください。 IntervalTrie [A]は、重複しない区間の集合の組合や交差などのブール演算を非常に高性能で実行できます。 joda DateTimeの場合、要素タイプをロスに変換する必要があります。

まず、あなたは右の依存関係を持っていることを確認してください。ここでは

あなたは尖塔を使用してこの問題を解決する方法です。あなたのbuild.sbtに尖塔のエキストラに依存関係を追加します。

libraryDependencies += "org.spire-math" %% "spire-extras" % "0.12.0" 

次に、あなたがorg.joda.time.DateTimeためIntervalTrie.Element型クラスのインスタンスを定義する必要があります。

implicit val jodaDateTimeIsIntervalTrieElement: IntervalTrie.Element[DateTime] = new IntervalTrie.Element[DateTime] { 
    override implicit val order: Order[DateTime] = Order.by(_.getMillis) 
    override def toLong(value: DateTime): Long = value.getMillis 
    override def fromLong(key: Long): DateTime = new DateTime(key) 
} 

ここで、IntervalTrieを使用すると、DateTime間隔でブール演算を実行できます（Intervalはここではjoda間隔ではなく、汎用間隔タイプspire.math.Intervalを参照）。

// import the Order[DateTime] instance (for spire.math.Interval creation) 
import jodaDateTimeIsIntervalTrieElement.order 

// create 100000 random Interval[DateTime] 
val r = new scala.util.Random() 
val n = 100000 
val intervals = (0 until n).map { i => 
    val ticks = r.nextInt(1000000000) * 2000L 
    val t0 = new DateTime(ticks) 
    val t1 = new DateTime(ticks + r.nextInt(1000000000)) 
    val i = IntervalTrie(spire.math.Interval(t0, t1)) 
    i 
} 

//compute the union of all of them using IntervalTrie 
val t0 = System.nanoTime() 
val union = intervals.foldLeft(IntervalTrie.empty[DateTime])(_ | _) 
val dt = (System.nanoTime() - t0)/1.0e9 
println(s"Union of $n random intervals took $dt seconds!") 

これは非常に高速です。私のマシンで：

Union of 100000 random intervals took 0.045001056 seconds! 

ウォームアップで適切なベンチマークを実行すると、これはさらに高速になります。