[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Proposal #9: Fast testing in PROGV
- To: Dan Hoey <hoey@NRL-AIC.ARPA>, jbarnett@NRTC.ARPA, common-lisp@SU-AI.ARPA
- Subject: Proposal #9: Fast testing in PROGV
- From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>
- Date: Fri, 1 Aug 86 08:36 EDT
- In-reply-to: <8607312211.AA13507@nrl-aic>
Date: Thu, 31 Jul 86 18:11:20 edt
From: Dan Hoey <hoey@nrl-aic>
From: Jeff Barnett <jbarnett@nrtc>
It was assumed in this and a previous message that looking for
duplicate names in the variable-list argument of a PROGV is an
N**2 operation.... It can be done in N*log N time.
You can put a mark on the property lists of the variables
for a linear algorithm.
Nit: no you can't. Putting a mark on a property list takes linear time
(length of the property list to see if it is already there), and you
have to do this for N variables. So you are back to N^2 again, and you
are likely consing, and misusing property lists, and...