Path: utzoo!attcan!uunet!hsi!stpstn!andyk
From: andyk@stpstn.UUCP (Andy Klapper)
Newsgroups: comp.software-eng
Subject: Re: recap so far
Message-ID: <5332@stpstn.UUCP>
Date: 5 Jul 90 13:50:43 GMT
References: <30852@cup.portal.com> <102100011@p.cs.uiuc.edu> <31097@cup.portal.com> <1568@oravax.UUCP> <8488@jpl-devvax.JPL.NASA.GOV> <81688@tut.cis.ohio-state.edu> <8529@jpl-devvax.JPL.NASA.GOV> <5312@stpstn.UUCP> <8581@jpl-devvax.JPL.NASA.GOV>
Reply-To: andyk@stpstn.UUCP (Andy Klapper)
Organization: The Stepstone Corporation, Sandy Hook, CT 06482
Lines: 43

In article <8581@jpl-devvax.JPL.NASA.GOV> kandt@AI-Cyclops.JPL.NASA.GOV writes:
>I've used these languages before -- having a basic set of objects is not
>the issue.  The issue is that the implementation of a "type" can be done
>in a variety of ways, where each implementation has certain advantages
>and disadvantages in terms of time and space.  A set, for example, can
>be implemented as a bit array, a simple array, a linked list, a hash
>table, and so on.  Smalltalk, Objective-C, etc. generally provide only
>one implementation of an "abstract type".  This one implementation is
>chosen because it works reasonably well for all cases, but it may not be
>optimal for a specific data set; in fact, it may be orders of magnitude
>slower than one tailored for the characteristics of the data set. 
>Automatic data structure selection was a hot topic in the 70s because
>people realized that there were tremendous pay-offs (in terms of
>efficiency) by optimizing data storage and manipulation algorithms for
>the expected data.

This is true.  I can think of two possible 'solutions',
1)	Have 1 class (say Set) that either automatically selects an algorithm
	based on the data.  (Each object in the set would respond to some
	message, say, optimizeFor, that would return how it wants to be
	optimized.  Above some mixture of requests the class would revert
	to the basic method (you wouldn't want to de-optimize because 1 out
	of a hundred objects in the set disagreed over how to optimize).)
	The other option is to tell the class how to optimize and leave it
	to the programmer to know what is best.  Personally I'd do both,
	but I always want every option :)

2)	Create a number of classes (say of Set), each one optimized in
	some way.  Our ICpak201(TM) product comes with a class called 
	HashSet for exactly the reasons you stated above.  The default
	implementation was too slow because it was designed to given
	good performance over most cases.  The designers of ICpak201(TM)
	needed a faster set for a limited case.

In Brad's world you could buy different Set classes from different venders
from a software catalogue and have all of the protocols the same, but the 
implementation differ.

-- 
The Stepstone Corporation                    Andy Klapper
75 Glen Rd.                                  andyk@stepstone.com
Sandy Hook, CT 06482                         uunet!stpstn!andyk
(203) 426-1875    fax (203)270-0106