Szukam implementacji wspólnej eliminacji wyrażeń (CSE) dla wykresów wyrażeń odpowiadających dużym wyrażeniom matematycznym (milionom węzłów).Implementacja wspólnej eliminacji wyrażeń
Jakie algorytmy są odpowiednie do tego celu? Szukałem w Internecie łatwego do wdrożenia algorytmu, ale nie mogłem nic znaleźć. Jeśli to możliwe, algorytm powinien mieć liniową złożoność liczby węzłów pełnego wykresu ekspresji.
Są to wyrażenia bez skutków ubocznych? Najprostszą rzeczą do zrobienia jest zahartowanie drzew dla każdej sub-wypowiedzi w wiadrach w celu określenia kandydatów do eliminacji subekspresji. Jest to specjalny przypadek CSE, w którym wszystkie wyrażenia znajdują się w pojedynczym (ogromnym) "bloku podstawowym". (Używam tego pomysłu jako podstawy do wykrywania duplicate code.)
Jeśli wyrażenia mają kolejność i efekty uboczne, warto rozważyć Value Numbering.
W porządku, nie ma żadnych skutków ubocznych. Jeśli dobrze zrozumiem twoją sugestię, powinienem przejrzeć węzły wyrażenia, w kolejności zależności i na każdym kroku sprawdzić, czy wyrażenie jest już obecne w mapie mieszania. Jeśli jest obecny, użyj tego podwyrażenia zamiast tego, jeśli nie dodaj go do mapy skrótu. Czy to jest właściwie zrozumiałe? – Joel
Tak. "W kolejności zależności" oznacza oddolne dla każdego drzewa. –
Tak naprawdę myślałem o tej strategii. Jakiego rodzaju mieszania użyć? – Joel
Ta reprezentacja może pomóc: http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html –