Я изучаю реализацию общего исключения подвыражения (CSE) для графов выражений, соответствующих большим математическим выражениям (миллионы узлов).Реализация устранения общего подвыражения
Какие алгоритмы подходят для этого? Я искал в Интернете простой алгоритм, но ничего не нашел. Если возможно, алгоритм должен иметь линейную сложность в числе узлов полного графа выражения.
Это выражения без побочных эффектов? Тогда проще всего сделать хэш-деревья для каждого подвыражения в ведрах, чтобы определить кандидатов для исключения суб-экспрессии. Это специальный случай CSE, где все выражения находятся в одном (огромном) «базовом блоке». (Я использую эту идею в качестве основы для определения duplicate code.)
Если выражения имеют порядок и побочные эффекты, вы можете рассмотреть Value Numbering.
Правильно, побочных эффектов нет. Если я правильно понимаю ваше предложение, я должен перебрать узлы выражения в порядке зависимостей и на каждом шаге проверить, присутствует ли выражение в хэш-карте. Если он присутствует, то вместо этого используйте это подвыражение, если не добавить его в хэш-карту. Это правильно понято? – Joel
Да. «В порядке зависимостей» означает снизу вверх для каждого дерева. –
Я действительно думал об этой стратегии. Какое хеширование вы бы использовали? – Joel
Это представление может помочь: http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html –