[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Proposal #9: Fast testing in PROGV
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...