Эффективно найти перекрывающиеся интервалы 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) 

, который работает. Моя первая забота была с линией vals.dropRight(1) ++ Seq(new Interval(fst.getStart, snd.getEnd))

Я подозреваю, dropRight является O(n - m) где n = |vals| и m = 1 в этом случае.

Эта реализация становится дорогой, если |a| находится в порядке сотен тысяч и более. Фактически vals ++ Seq(e) также является проблемой, если он n + 1 для каждого a[i].

Во-первых, моя оценка правильная?

Во-вторых, есть ли более эффективный способ написать это без изменяемых структур данных?

Я написал это из контекста, в котором он используется, фактическое приложение находится в работе Spark (так что foldLeft будет складываться на RDD[MyType]).

EDIT: Совсем забыл нет foldLeft на RDD (игнорировать искру мне придется придумать другой способ, но я по-прежнему заинтересован в ответ на это, минус тот факт, что не будет работать в Спарк)

Answer 1

Посмотрите на структуры данных IntervalSeq [A] и IntervalTrie [A] в spire math library. IntervalTrie [A] позволяет выполнять логические операции, такие как объединение и пересечение множеств неперекрывающихся интервалов с чрезвычайно высокой производительностью. Это требует, чтобы тип элемента был без потерь конвертируемым в длинный, что имеет место для joda DateTime.

Вот как вы бы решить эту проблему с помощью шпиля:

Во-первых, убедитесь, что у вас есть правильные зависимости. Добавить зависимость к шпиля статистов к вашему build.sbt:

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

Далее необходимо определить IntervalTrie.Element класс типов, например, для org.joda.time.DateTime:

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 здесь относится к общему типу интервала spire.math.Interval, а не joda 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! 

Выполнение надлежащего теста с разминкой сделает это еще быстрее.