Tôi đang xem xét việc thực hiện loại bỏ biểu hiện chung (CSE) cho biểu đồ biểu thức tương ứng với các biểu thức toán học lớn (hàng triệu nút).Thực hiện loại trừ biểu hiện chung phổ biến
Thuật toán nào phù hợp để thực hiện việc này? Tôi đã tìm kiếm trên Internet cho một thuật toán dễ thực hiện nhưng tôi không thể tìm thấy bất cứ điều gì. Nếu có thể, thuật toán phải có độ phức tạp tuyến tính trong số các nút của biểu đồ biểu thức hoàn chỉnh.
Đây là những biểu thức không có phản ứng phụ? Sau đó, điều dễ nhất để làm là băm cây cho mỗi biểu thức con thành các nhóm để xác định các ứng cử viên cho việc loại trừ biểu thức phụ. Đây là trường hợp đặc biệt của CSE trong đó tất cả các biểu thức nằm trong một khối cơ bản (lớn) duy nhất. (Tôi sử dụng ý tưởng này làm cơ sở để phát hiện duplicate code.)
Nếu các biểu thức có trật tự và tác dụng phụ, bạn có thể muốn xem xét Value Numbering.
Phải, không có phản ứng phụ. Nếu tôi hiểu chính xác đề xuất của bạn, tôi nên lặp qua các nút của biểu thức, theo thứ tự các phụ thuộc, và tại mỗi bước kiểm tra xem một biểu thức đã có trong bản đồ băm chưa. Nếu nó có mặt, sau đó sử dụng subexpression này thay vào đó, nếu không thêm nó vào bản đồ băm. Điều này có được hiểu đúng không? – Joel
Đúng. "Theo thứ tự phụ thuộc" có nghĩa là đáy cho mỗi cây. –
Tôi đã thực sự nghĩ về chiến lược này. Bạn sẽ sử dụng loại băm nào? – Joel
Đại diện này có thể giúp: http://www.masonchang.com/blog/2010/8/9/sea-of-nodes-compilation-approach.html –