Поиск определенного узла в абстрактном синтаксисе Дерево

Question

Я пытаюсь найти определенные узлы в AST (Abstract Syntax Tree). Основная идея заключается в следующем:

• Существует АСТ, проанализированный из исходного кода, который содержит около 10000 узлов.
• Существует список из 50 наименований, которые я хотел бы найти в АСТ.

Вопрос: Каков наилучший способ поиска этих 50 предметов в AST?

Прямо сейчас, я думаю об использовании Arraylist, содержащего эти 50 предметов. Затем, пройдя AST и сравните каждый узел с Arraylist, используя цикл. Это хорошая идея с точки зрения производительности? Я хочу, чтобы операция выполнялась быстро. Есть ли другие способы решения этой проблемы?

Answer 1

Я бы не использовал Arralylist, так как он требует, чтобы вы просматривали его каждый раз, и это просто накладные расходы. Вы можете написать 50 предикатов как «p1 или p2 или ...» так же легко.

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

Если вы выполняете поиск один раз, вам нужно «или» вместе ответы из 50 предикатов, которым требуется 49 ors, поэтому дополнительная стоимость составляет 49 * [стоимость OR] [количество узлов]. Если вы ищете 50, дополнительная стоимость составляет 49 [стоимость посещения узла дерева] * [количество узлов]. Итак, вопрос в том, стоит ли стоимость «или» меньше стоимости «узла дерева посещений». «Или» довольно быстро работает на большинстве машин, потому что он использует регистры и значения, которые, вероятно, уже находятся в кеше. Посещение узла дерева может быть довольно быстрым, но, вероятно, несколько инструкций; хуже, это касается памяти. Если ваше дерево достаточно велико, чтобы не вписываться в кеш, ваши затраты на поиск-50, скорее всего, будут доминировать по времени доступа к памяти, если предикаты дешевы.

Теперь мы можем «обмануть» несколько интересных способов. Во-первых, это могут быть предикаты, имеющие некоторые отношения; если предикат A подразумевает предикат B, я могу сначала проверить B, а если false, мне не нужно проверять A. Это может сократить число «или», но не помогает при посещении деревьев. Во-вторых, может быть, что предикаты совместно используют подтесты, например, предикат А действительно «a1 и a2», а B фактически «a1 и a2»; в этом случае вы можете определять предикаты и оценивать субпредикаты меньше раз; вам нужно только оценить «a1» один раз за узел. Это не так просто сделать с помощью технологии сканирования. Возможно, что сбой предиката подразумевает, что поддерево не нужно искать; здесь 50 поисковых запросов могут оказаться более быстрыми, так как каждый поиск будет проверять только нужные поддеревья, где поисковый запрос в значительной степени потребует поиска до узла, который все предикаты согласны, является точкой остановки.

Однако, вполне вероятно, что для каждого предиката ваша программа захочет реагировать по-разному. Таким образом, ваша структура программы действительно представляет собой набор «если p1 (узел), то a1 (узел)». Если предикаты дешевы и триггера с относительно высокой частотой, действия, вероятно, будут доминирующей стоимостью (более дорогостоящей, чем переход к узлу дерева), и тогда любой из этих методов будет хорош с точки зрения производительности.

Наконец, если предикаты и действия сложны, вы просто не сможете угадать, какая из них дешевле, легко. Хорошо, код и поиск (не , что трудно) и измерить его на реалистичные данные.