Я изучаю реализацию общего исключения подвыражений (CSE) для графов выражений, соответствующих большим математическим выражениям (миллионы узлов).
Какие алгоритмы подходят для этого? Я искал в Интернете простой в реализации алгоритм, но ничего не нашел. Если возможно, алгоритм должен иметь линейную сложность по количеству узлов полного графа выражения.
Это выражения без побочных эффектов? Тогда проще всего разбить деревья для каждого подвыражения на сегменты, чтобы определить кандидатов на удаление подвыражения. Это особый случай CSE, где все выражения находятся в одном (огромном) "базовом блоке". (Я использую эту идею как основу для обнаружения дубликата кода.)
Если выражения имеют порядок и побочные эффекты, вы можете рассмотреть возможность нумерации значений.
