Применение деревьев для представления строковой информации Абдрашитов Д. С. (гр. 6538) Руководитель Корнеев Г. А., к.т.н., доцент кафедры КТ

2 Применение деревьев для представления строковой информации Операции со строками Получение длины Получение подстроки Получение символа Конкатенация Вставка Удаление Замена

3 Применение деревьев для представления строковой информации Существующие методы ОперацияЧасть строки Изменяемые строки Неизменяемые строки Циклические очереди Двусвязные списки Функциональные строки Получение подстроки O(m)O(1)O(m)O(n + m) Конкатенация O(n + m) O(m)O(1)O(n) ИндексацияконцыO(1) серединаO(1) O(n) Вставка символа началоO(n) O(1) серединаO(n) конецO(1)O(n)O(1) O(n) Удаление символа началоO(n)O(1) серединаO(n) конецO(1) O(n) Замена символаO(1)O(n)O(1)O(n)

4 Применение деревьев для представления строковой информации Конкатенация строк Текст1Текст2Текст1Текст2 +=

5 Применение деревьев для представления строковой информации Конкатенация связок Текст1Текст2 Текст1Текст2 += +

6 Применение деревьев для представления строковой информации Пример связки СПбГУ + ИТМО +

7 Применение деревьев для представления строковой информации Связки с буферами префикссуффикс середина Связка Стек 0 … log n ~n

8 Применение деревьев для представления строковой информации Связки реального времени Связки Стек log n … 2 log n~nlog n … 2 log nlog n

9 Применение деревьев для представления строковой информации Сравнение оценок времени ОперацияЧасть строкиНеизменяемые строкиСвязки с буферамиФункциональные деки реального времени с конкатенацией Получение подстрокиконцыO(1)O(min(m, log n))O(m) серединаO(1)O(log n)н/дн/д КонкатенацияO(n + m)O(min(m, log n))O(1) ИтерированиеO(1) ИндексацияконцыO(1) серединаO(1)O(log n)н/д Вставка символаконцыO(n)O(1) серединаO(n)O(log n)н/д Удаление символаконцыO(1) серединаO(n)O(log n)н/д Замена символа на символконцыO(n)O(1) серединаO(n)O(log n)н/д Вставка строкиконцыO(n + m)O(min(m, log n))O(1) серединаO(n + m)O(log n)н/д

10 Применение деревьев для представления строковой информации Практическая реализация Замена класса String сбалансированными связками с использованием декартовых деревьев Замена класса StringBuilder с использованием идеи буферов логарифмического размера

11 Применение деревьев для представления строковой информации Результаты эксперимента Суммарное время Стандартные строки: 405 сек Сбалансированные связки: 647 сек Время без индексации Стандартные строки: 301 сек Сбалансированные связки: 286 сек

12 Применение деревьев для представления строковой информации Полученные результаты Метод представления строк с амортизированными оценками Метод представления строк с гарантированными оценками Хронологическая структура данных для деков с операцией конкатенации

13 Применение деревьев для представления строковой информации Благодарю за внимание