Comments 16
так где все эти изменения? уже в BC2 ?
Хмммм. Так как это перевод, задавать вопросы тут довольно нелогично. Но из текста следует, что "ускорили" это разработчики VSCode путем размещения кода раскрасчика в той куче, которой нативно доступен токенайзер, как следствие, вся основная вычислительная работа, которую расширение делало по факту в дополнение к самому редактору, а именно поиск пар в документе как списке символов, а не токенов, оказалась ненужной, но в результате внедрения раскрасок побочным эффектом стало перепиливание токенайзера под более удобный формат хранения данных (относительные смещения против абсолютных, и те только внутри элемента). Второе ценно, но заголовок оказывается кликбейтом, так как ускорение достигнуто недоступным для разработчика расширения VSCode способом.
Круто, но сразу начинаешь хочется поиграть в "хакера в столовой" и спросить "а Си с макросами как?" :-)
А у меня он вообще, почему-то не работает.
Странная проблема. Зачем после вставки скобки в начало документа перекрашивать уже существующие скобки? Или конкретный цвет скобок означает конкретный уровень вложенности? Я бы ушел от конкретного цвета. И тогда проблема ушла бы сама собой.
Например, где-то в середине документа была закрывающая скобка без пары (закрывающих больше, чем открывающих). Тогда новая открывающая в начале станет парной к закрывающей.
Что-то я не пойму, чем нам мало линейного алгоритма со стеком? Не выспался, по ходу.
У него сложность вроде как О(N) где N — длина документа. Тут гонятся хотя бы за O(log^2N), что сильно быстрее на больших документах. Плюс маета с синтаксисом, так как "{" и "}" это совсем не те скобки, которые надо подсвечивать, равно как и // {blabla} }{ и тому подобное не должны влиять на подсветку. Плюс гонятся за изменениями, чтобы если воткнул скобку в середину, не надо было перечитывать весь документ, то же с комментированием и снятием комментария со строки/блока. В общем и целом алгоритма в самом деле маловато стало.
Что-то странное - накручивали-накручивали деревья поверх списков, а в итоге получили асимптотику O(N +E) - и чем же она лучше тривиального алгоритма с линейным проходом слева направо?
Уверен, что если ре-парсинг не нужен, то задачу можно решить за log N + E - есть много структур данных, которые умеют прибавление на отрезке и вставку/удаление элементов в середине. Например, декартовы деревья. А если ре-парсинг нужен, то ведь и смысла нет оптимизировать поиск скобок быстрее стандартного линейного алгоритма?
P.S. Немного напоминает мне, как во время одного собеседования разработчик из Индии хвалился своим "знанием" алгоритмов и рассказывал, как он оптимизировал запросы к базе данных путём создания сбалансированных двоичных деревьев *во время обработки каждого запроса*. Т. е. база данных отвечает списком объектов, которые надо пофильтровать каким-то простым критерием вроде "мин. элемент >= X", и они для этого пихали весь ответ из базы в дерево, чтобы потом спуститься по дереву и найти нужный элемент. В общем, главное - прикрутили умный алгоритм, а что толка от него нет, поскольку перед этим всё равно линейный алгоритм работает - не важно.
Вижу, что на грабли со скобками в комментариях наступили, и что решили их игнорировать. Но не вижу, как решен вопрос о внезапном раскомментировании куска когда, с кучей скобок, которые "портят" уровень вложенности и код за раскомментированным участком. Есть оценки, насколько такой случай "нехорош" для вашего алгоритма?
Ну, грубо говоря (для C):
int foo() {
/*
if (cancerWhistles())
{
if foo2() return 0;
*/
}
Увлекательная история о раскрашивании парных скобок — как VSCode ускорил раскраску в 10,000 раз