[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- To: common-lisp-object-system@SAIL.STANFORD.EDU
- Subject: CPL Computation
- From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Wed, 28 Jan 87 01:30 EST
- In-reply-to: The message of 27 Jan 87 15:07 EST from Dick Gabriel <RPG@SAIL.STANFORD.EDU>
Date: 27 Jan 87 1207 PST
From: Dick Gabriel <RPG@SAIL.STANFORD.EDU>
Finally, my algorithms wizard and I studied the New Flavors CPL
computation description and think there is a performance problem with the
algorithm it describes. Consider the following graph of 4n+1 classes:
(defclass Ai (Bi Ci) ())
(defclass Bi (Di Ai+1) ())
(defclass Ci (Di) ())
(defclass Di () ())
for 0 <= i < n.
The New Flavors algorithm, as described, seems to take n+1 passes, though
there is exactly one total order possible.
This is true. I'm not sure that it's significant. Does topological sort run
in linear time?
Given ... that there is no intuition to any order beyond what the
topological sort gives you ...
I agree with Danny's disagreement with this. I'm interested in continuing
the search for an algorithm that is acceptable to your algorithms wizard
and at the same time provides the intuitive behavior. It's getting late for
me, but I'll follow up on this tomorrow.