Участник:Vid1525/Дерево отрезков: различия между версиями

Версия 15:14, 15 октября 2022

Алгоритм нахождения суммы чисел на отрезке с помощью одномерного "Дерево отрезков"
Последовательный алгоритм
Последовательная сложность	[math]O(qlog(n))[/math]
Объём входных данных	[math]n[/math]
Объём выходных данных	[math]q[/math]

Авторы: И.Д. Васенков

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Дерево отрезков - это упорядоченная древовидная структура данных для хранения списка точек. Эта структура позволяет эффективно сообщать результаты некоторых запросов на отрезках данного списка точек (сумма / минимум) и обычно используется в двух или более измерениях. Деревья отрезков были введены Джоном Луисом Бентли в 1979 году. Аналогичные структуры данных были обнаружены независимо Лукером, Ли и Вонгом. Дерево отрезков является альтернативой дереву k-d. По сравнению с деревьями k-d, деревья диапазонов обеспечивают более быстрое время запроса (в обозначении Big O) [math]O(log ^ dn)[/math], но худшее хранение [math]O(nlog^{d-1}n)[/math], где n - количество точек, сохраненных в дереве, d - размерность дерева. В данной работе будет рассматриваться одномерное дерево отрезков.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

При отсутствии изменяющих запросов в дереве отрезков можно считать, что все запросы к дереву могут быть выполнены параллельно (если количество потоков выполнения запросов не ограничено). При построении дерева необходимо учитывать, что более высокие слои дерева невозможно построить без предыдущих более низких слоев, поэтому строить дерево лучше всего снизу вверх (запускать несколько потоков суммирования значений на одном уровне, после чего переходить к следующему).

1.9 Входные и выходные данные алгоритма

Входные данные: - Массив чисел длины n (в данном примере считаем, что элементы массива - 64-битные целые беззнаковые числа, суммирование происходит по модулю [math]2^{64}[/math])

- q запросов, каждый из которых состоит из пары чисел [math]l_{i}[/math] и [math]r_{i}, l_{i}, r_{i} \in [0, n-1][/math] и [math]l \leq r[/math]; числа l и r задают границы отрезка, на котором будет происходить суммирование чисел (индексация массива начинается с нуля, [math]i = 1, ..., q[/math] - номер запроса)

Выходные данные: - Массив сумм на отрезках [math][l_{i}, r_{i}], i = 1, ..., q[/math] (размер массива - q)

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

Sqlite https://www.sqlite.org/

SciPy https://scipy.org/

Sklearn https://scikit-learn.org/stable/

3 Литература

1. Bentley, J. L. (1979). "Decomposable searching problems".

2. Lueker, G. S. (1978). "A data structure for orthogonal range queries". 19th Annual Symposium on Foundations of Computer Science (sfcs 1978).

3. Lee, D. T.; Wong, C. K. (1980). "Quintary trees: A file structure for multidimensional database systems". ACM Transactions on Database Systems.

@@ Строка 22: / Строка 22: @@
 === Ресурс параллелизма алгоритма ===
-При отсутствии изменяющих запросов в дереве отрезков можно считать, что все запросы к дереву можно выполнить параллельно.
+При отсутствии изменяющих запросов в дереве отрезков можно считать, что все запросы к дереву могут быть выполнены параллельно (если количество потоков выполнения запросов не ограничено).
-При построении дерева необходимо учитывать, что более высокие слои дерева невозможно построить без предыдущих более низких слоев, что незначительно затрудняет параллельное выполнение процесса предобработки.
+При построении дерева необходимо учитывать, что более высокие слои дерева невозможно построить без предыдущих более низких слоев, поэтому строить дерево лучше всего снизу вверх (запускать несколько потоков суммирования значений на одном уровне, после чего переходить к следующему).
 === Входные и выходные данные алгоритма ===