Efficient Two-Dimension Object Lattices

有效率之二維物件格形結構

謝文恭(Wen-Gong Shieh)

《華岡工程學報》 9期 (1995/07) Pp. 49-63

https://doi.org/10.29987/CCUHKJE.199507.0004

摘要

爲支援偏序化組織的物件結構（如繼承層屬結構或類層屬結構），一個編譯階段之緊縮調節編碼技術（簡稱緊縮調節）已經被發展來促成執行階段高效率之最大下界（如最大共同次類）及最小上界（如最小共同上類）之運算，若該偏序結構得以完美的調節。然而，並非所有的偏序結構在緊縮調節中都能完美的調節。此外，我們察知大多數實用物件結構爲二維偏序。因此，本文提出另一種替代編碼技術，稱爲N格編碼，本文並且展示，N格編碼對大多數實用之極大型二維物件格形結構比緊縮調節有更佳之效果。

並列摘要

To support object structures organized as partial orders (e.g. inheritance hierarchies or class hierarchies), a compilation-time partial order encoding technique, called compact encoding with modulation (CEM for short), has previously been developed to enable efficient computations of greatest lower bound (e.g. greatest common subclass) and least upper bound (e.g. least common superclass) at run time, provided that the partial order can be perfectly modulated. However, ”perfect” modulation in CEM may not be possible for some partial orders. Besides, we observe that most practical object structures are two-dimension partial orders. Therefore, this paper proposes a different encoding technique, called N-grid encoding as an alternative. The N-grid encoding is shown to outperform CEM for most practical two-dimension object lattices of extremely large size.