[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...