Магистрант СПИНТех повысил эффективность работы с кодом благодаря новой структуре данных
Студент магистратуры Института СПИНТех Кирилл Долбилов (ПИН-21М) в рамках практики в НПК «Технологический центр» адаптировал модель структуры данных текстового редактора для языка Verilog, что привело к значительному повышению скорости выполнения операций.
Традиционные редакторы кода используют линейные структуры данных для хранения исходного кода, что приводит к линейной асимптотике при выполнении операций вставки, удаления и изменения текста. Это означает, что время выполнения таких операций напрямую зависит от размера текста, что может вызывать существенные задержки при работе с большими файлами.
В отличие от этого, предложенная модель Piece tree представляет собой гибридную структуру, которая разбивает текст на небольшие фрагменты и организует их в древовидную структуру. Это позволяет эффективно управлять изменениями, так как операции редактирования выполняются на уровне отдельных фрагментов, а не всего текста целиком.
Благодаря переходу от линейной к древовидной структуре данных асимптотика операций вставки и удаления значительно улучшилась. В частности, время выполнения операций вставки сократилось с линейного O (n) до логарифмического O (log n). Это стало возможным благодаря тому, что Piece tree позволяет быстро находить нужные места для вставки или удаления фрагментов текста, минимизируя количество необходимых операций перемещения и копирования данных.
Валентина Алешина, ведущий инженер-программист НПК «Технологический центр», отмечает: «После внедрения изменений проведенные бенчмарки показали увеличение скорости выполнения операций вставки, удаления и поиска в 3-5 раз по сравнению с традиционным строковым представлением. Кроме того, время открытия больших файлов (более 1 млн строк) сократилось в среднем на 35%».
В настоящее время авторская модель находится на стадии реализации и планируется к внедрению в кроссплатформенное российское программное обеспечение САПР «Ковчег», которое используется для проектирования микросхем.
Желаем Кириллу дальнейших успехов в научной и профессиональной деятельности!