Fractional Cascading

Fractional cascading - техника, позволяющая ускорить серию бинарных поисков в связных структурах данных. Одной из задач, где может применяться Fractional Cascading, является поиск в ациклическом графе с ограничениями на ребрах, в вершинах которого хранятся списки данных. Запросы состоят из искомого значения x и пути в графе. Необходимо для каждой вершины, лежащей на пути, найти среди элементов ее списка такой минимальный y, что x <= y. Предположим, что путь состоит из k вершин. Тогда применение Fractional Cascading позволяет обрабатывать такие запросы за O(k + log n).

Реализация

Основным является класс Cascade. Каждый экземпляр этого класса соответствует некоторой вершине графа. В нем содержатся:

1. ссылка на comparator, который был использован при каскадировании и будет использован для поиска;
2. val — список элементов, среди которых осуществляется поиск. Он содержит все значения соответствующей вершины, а так же часть элементов из списков потомков, добавленных при каскадировании. Значения val отсортированы с помощью comparator.
3. next — список, элементами которого являются экземпляры класса Cascade, соответствующие вершинам детей;
4. cascadeIndex — список индексов в списке next, указывающих какому потомку принадлежит соответствующий элемент из val;
5. innerIndexes — список номеров элементов, в списке из того каскада, которому он соответствует;
6. selfLinks — список ссылок на следующий элемент из списка текущей вершины;
7. nextLinks — список ссылок на следующий элемнт из списка потомка;
8. loadFactor — параметр, от которого зависит число элементов из списков потомков, добавляемых в val. Предположим loadFactor равен i. Тогда каждый i-й элемент из списка потомка добавляется в список val родителя.

При создании каскада для некоторой вершины необходимы каскады для всех детей. В первую очередь значения из вершины сортируются с помощью comparator. Затем они сливаются с каждым loadFactor(ребенка) значением из каскада ребенка. При этом сохраняются innerIndexes и cascadeIndex. Затем расчитываются selfLinks и nextLinks. В качестве собственного loadFactor используется 2 * (число родителей).

При обработке запроса сначала выполняется бинарный поиск в каскаде, соответствующем первой вершине в пути. Затем спускаемся к каскаду соответствующего ребенка. Для этого, используя cascadeIndex и nextLinks, находим ближайший элемент соответствующего каскада. Ответ для каскада ребенка с точностью до loadFactor ребенка сохранен в innerIndexes. Значение loadFactor ограничено константой, т.к. работаем с графом с ограничениями на ребрах. Тогда за О(1) находим точный ответ.

Для поиска в каскаде, соответствующем началу пути, необходимо O(log n) операций. Для поиска в каждом следующем каскаде требуется O(1). Спуск к следующему каскаду происходит k раз. Таким образом, на ответ на запрос требуется O(k + log n) операций.