Поиск подможеств на Scala
Формулировка задачи
Для заданого множества повторяющихся чисел найти количество поддиапазонов, содержащее столько же уникальных элементов, сколько и в исходном множестве.
Пример: исходный ряд “1 2 2 1 1”. Пусть номера позиций начинаются с 1 и оканчиваются 5. Ответом будет число 8 — и вот эти поддиапазоны:
- [1,2]
- [1,3] (в понимании с 1 по 3 включительно)
- [1,4]
- [1,5]
- [2,4]
- [2,5]
- [3,4]
- [3,5]
Решение этой задачи “в лоб” не представляет интереса,обо превышает время O(n²) ввиду перебора каждого элемента и поиска всех множеств с заданым числом уникальных элементов. Имея ввиду, что это задача линейного поика, мы можем лучше.
Можно предложить разные методы решения, но наша цель, помимо финального результата — показать баланс:
- точности
- сложности модели решения
- сложности алгоритма
- сложности кода
Точность
В общем случае, исходя их постановки, задача пожет быть решена либо точно — либо одним из приближённых алгоритмов. При правильном подборе параметров приближённого алгоритма можно свести вероятность отклонения к практически нулевой. Особенно популярны игры с параметрами Bloom filter и HyperLogLog.
В мире BigData такой подход особенно популярен. Так поступает современная MPP Impala при выполнении операций типа Join распределённо — bloom-фильтр, построенные на ключах присоединения на каждом узле, позволяет заранее обрезать часть записей на этапе чтения с диска, до начала сопоставлений, уменшая домен операции join. Дальнейшие этапы используют функции точного рассчёта.
В нашем случае есть соблазн использовать что-то из минимальных (Bit Mask, Hash Buckets) или приближённых структур (Bloom fitlers, LSH, Count-Distinct, SpaceSaver).
Но попробуем решить задачу точными методами.
Модель решения
Чем более точно мы описываем модель задачи, тем проще нам описать алгоритм. Модель мы можем построить, как минимум основываясь на:
- очевидных фактах (диапазон данных, размерность…)
- наблюдениях
- аксиомах
- теоремах
Попробуем записать наши наблюдения:
- Пусть NDV — это количество уникальных элементов исходного множества, а Size — размер исходного множества
- Длина искомого диапазана не может быть меньше чем NDV
- Для любого найденого подходящего диапазона минимального размера, содержащего все NDV, можно легко определить количество диапазонов бОльшего размера, включающих его. Строго говоря, оно равно количеству этих элементов справа, если мы двигаемся вправо, обрезая после поиска элементы слева — это легко видеть для множества [1,2] — справа 3 элемента и соотвественно 3 множества — [1,3], [1,4], и [1,5], удовлетворяющих условию NDV
- Из 1–3 мы могли бы сказать, что задача сводится к последовательному поиску минимального диапазона для каждого элемента и прибавлению к нему остатка справа в понимании количества подмножеств
Алгоритм
Исходя из наблюдений, можно было бы рассмотреть варианты
- Формирование Set/HashSet справа от каждого элемента до достижения NDV — и далее применять формулу наблюдения 4. Увы такой вариант, при своей максимальной прозрачности приближается к O(n²)
- Построить обратный индекс для входных данных и для каждого элемента расширять окно поиска в индексе от NDV и далее пока не будет найден поддиапазон — и далее снова формулу наблюдения 4. Увы, но процедура расширения окна не намного лучше в оценке.
- То же, но логарифмический поиск, когда мы окно сначала в два раза расширяем, а потом — пропроционально степени 2 сужаем/расятгиваем пока не дойдём до диапазона. Это улучшает оценку, делая её между O(n * logN) и O(n²)
- Использовать приоритетную очередь — PriorityQueue — для каждого из NDV уникальных значений создать свою очередь. Приоритет каждой очереди — по возрастанию индекса элементов. Для каждого элемента данных изимаем низы очереди и отбираем среди них максимальный. Это решение min-max задачи представляет из себя индекс правой части минимального окна поддиапазона содержащего NDV уникальных элементов. Повторяем пока не исчерпается хотя-бы одна очередь. Минус решения в затратах на компарацию в очередях при больший NDV и Size. На скрине профайлера можно увидеть, что компарации забирают более 80% процессорного времени

5. Оптимизация предыдущей идеи — использовать простую FIFO очередь при условии что структура обратных индексов построена так, что для каждого из NDV элементов, список его индексов отсортирован по-возрастанию. Этот вариант будет считать конечным, ибо множество в 100,000 элементов при реализации на Scala без глубинных оптимизаций (включая native, multicore, distribution) выполняет за 1 секунду на современном ноутбуке.
Код
Полученный код обладает достаточной краточтью и прозрачностью, что бы его можно было
- понять
- улучшить
Репозиторий вы можете посмотреть тут
import scala.collection.mutable
import scala.util.control.Breaks._
object NormalTypeQueue {
def nextRight(r: Long): Long = r + 1
def main(args: Array[String]): Unit = {
val szLine = scala.io.StdIn.readLine()
val dataLine = scala.io.StdIn.readLine()
val sz = szLine.toLong
var data = dataLine.split(" ").map(_.toLong)
val iData = data.zipWithIndex
val grp = iData.groupBy { case (v, i) => v }
var cnt = 0L
val heapMap = new mutable.HashMap[Long, mutable.Queue[Int]]()
grp
.map { case (v, ilst) => (v, ilst.map(_._2)) }
.foreach { case (v, ilst) => {
if (!heapMap.isDefinedAt(v))
heapMap.put(v, mutable.Queue.empty[Int])
heapMap(v).enqueue(ilst: _*)
}
}
breakable{
(0L to sz - 1) foreach (i => {
val n = data.apply(i.toInt)
try {
val minMax = heapMap.map(_._2.head).max
heapMap(n).dequeue()
cnt = cnt + 1 + sz - 1 - minMax
}catch {
case e:Exception => break()
}
})
}
println(cnt)
}
}