Geniş matematiksel ifadelere (milyonlarca düğüm) karşılık gelen ifade grafikleri için ortak alt-ifade eleme (CSE) uygulamak için arıyorum.Ortak alt ifade eliminasyonu gerçekleştirme
Bunu yapmak için hangi algoritmalar uygundur? Kullanımı kolay bir algoritma için interneti araştırıyordum ama hiçbir şey bulamadım. Mümkünse, algoritma tam ifade grafiğinin düğüm sayısında doğrusal bir karmaşıklığa sahip olmalıdır.
Bunlar yan etki içermeyen ifadelerdir. Sonra yapılacak en kolay şey, alt ifadenin ortadan kaldırılması için adayları belirlemek için her alt ifadenin ağaçlarını kovalara ayırmaktır. Bu, tüm ifadelerin tek bir (büyük) "temel blokta" bulunduğu CSE özel bir durumudur. (Bu fikri duplicate code algılamak için temel olarak kullanıyorum.)
İfadelerin sıralı ve yan etkileri varsa, Value Numbering'u düşünebilirsiniz.
Doğru, hiçbir yan etkisi yoktur. Önerinizi doğru bir şekilde anladığım takdirde, bağımlılık sırasına göre ifadenin düğümleri üzerinde döngü yapmalı ve her adımda bir özet haritasının bir karma haritada bulunup bulunmadığını kontrol etmeliyim. Varsa, o zaman karma haritasına eklemezseniz, bu alt ifadeyi kullanın. Bu doğru anlaşıldı mı? – Joel
Yep. "Bağımlılık sırasına göre", her ağaç için aşağıya doğru anlamına gelir. –
Aslında bu stratejiyi düşünüyordum. Ne tür bir karmaşayı kullanırdınız? – Joel
Bu sunum size yardımcı olabilir: http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html –