[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: common-lisp-object-system@SAIL.STANFORD.EDU*Subject*: Elaboration on the Non-intuitiveness of New Flavors Algorithm...*From*: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>*Date*: Thu, 29 Jan 87 01:10 EST*In-reply-to*: The message of 27 Jan 87 21:01 EST from Dick Gabriel <RPG@SAIL.STANFORD.EDU>

I agree with your [Dick's] analysis of the behavior of the New Flavors algorithm. This funny behavior when multiple passes are required is the same thing that has been bothering me. The New Flavors algorithm produces an "intuitive" result in many cases, but in this complex case it loses. I think we are likely to support some variant of the Gabriel or Bobrow proposed algorithms instead; so far the Bobrow one seems to produce the most consistently intuitive results. I fixed its performance problem that I mentioned yesterday by changing compute-must-precedes-closure; in place of (pushnew precede closure) (walk precede (cons element path)) do (unless (member precede closure) (push precede closure) (walk precede (cons element path))) The case that I gave up on after waiting a minute takes 0.23 seconds now, just about the same as the others (although Bobrow conses 3 times as much). None of the algorithms I've been comparing have been coded with speed paramount. I don't know whether the Bobrow algorithm is easy to explain, though. I also tried a variant of the Bobrow algorithm where the initial elimination of duplicates preserves the first occurrence of each class instead of the last. It's interesting but not really better. I don't think any topological sort tie-breaker based on non-local considerations such as preorder or postorder treewalk is going to produce intuitive results in all cases, because intuition depends on local considerations. I've been trying various tie-breakers but no good results yet. The advantage of the Bobrow algorithm is that it is preorder when that works, and when it doesn't, it moves things the minimum distance required to make them work. It usually produces the same result as the Gabriel-postorder algorithm, but here is an example that shows that the last-visit disambiguation of topological sort is not the same as the Bobrow-Kiczales algorithm. (DEFCLASS A (B C D E F)) (DEFCLASS B (F X)) (DEFCLASS C (F Y)) (DEFCLASS D (F X)) (DEFCLASS E ()) (DEFCLASS F ()) (DEFCLASS X ()) (DEFCLASS Y ()) Flavors, Gabriel-pre, Bobrow produce A B C D E F X Y Gabriel-post produces A B C D E F Y X It's hard to say which is intuitive in this case, so I mention this example only to show that Bobrow and Gabriel-post are not equivalent. I want to continue thinking about a better tie-breaker for topological sort.

- Prev by Date:
**Progress is Our Most Important Problem** - Next by Date:
**CPL Tiebreaker** - Previous by thread:
**Re: Elaboration on the Non-intuitiveness of New Flavors Algorithm...** - Next by thread:
**Complexity of Topological Sort + single-pass treewalk tiebreaker** - Index(es):