From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Re: What is Object Oriented Programming? Is C doomed?
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
Date: Mon, 28 Dec 1992 01:53:33 GMT

In article <1992Dec23.134325.27585@netcom.com> erc@netcom.com (Eric Smith) writes:
>In article <1992Dec23.092700.2450@ucc.su.OZ.AU> maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
>>>
>>>As proof that you have to allocate the maximum size in advance, the time
>>>it takes to change the allocation and access one element is more than the
>>>time it takes to access one element without changing the allocation.  The
>>>originally stated requirement for it to be considered random access was
>>>that any element could be accessed as fast as any other.  Therefore it is
>>>not random access by that definition in that case.  QED.
>>
>>	You proof depends on the statment that the time taken
>>to access one element is less than the time taken to reallocate
>>and access one element. This need not be so. Whats to stop
>>me counting off exactly one second on all operations,
>>then your original requirement of equal access time would
>>be satisfied and your proof invalid.
>
>
>The purpose of counting off one second is to waste time to hide the
>fact that it isn't random access.
>
	Irrelevant. A single couterexample, no matter how
stupid, invalidates a statement, and thus shows any proof
was incorrect.

>>
>>	Suppose I use a linked list with a preallocated cache.
>>It provides O(1) access and only wastes a fraction of the space
>>of a completely preallocated array (unless the whole array is used
>>up, in which case it wastes a bit more). It is somewhat slower,
>>of course, and that preallocated cache *is* an array of course :-)
>
>Each cache miss causes a delay, and therefore it is not random access.

	Doesnt follow at all. You miss the point.
You stated that equal time was required for each access.
This condition is the wrong condition, what you should have
said was that there exists some period such that all accesses
are LESS than that period.

	I showed that if the above condition is met, your
condition is trivial to meet by simply delaying any access
that was faster than this maximum access time by
adding a useless delay.

	I then proceed to accept my condition in place of yours,
since if mine is met, your can also be met.

	Since for any fixed size collection, in any reasonable
piece of code, such a maximum access time for any element
always exists (just take the longest access time for any element),
I then proceeded to show, or at least attempt to show,
that what you really should have said was that

	"There exists some period 
	FOR ANY SIZED COLLECTION
	such that all accesses are less than this period"

In other words, access is O(1), known as constant access time.

	Whats an access? If you only include read and write,
a cached linked list can easily satify the requirement.
Itsot hard to see why .. the cache itself can be
constructed just like an array :-)

	So you must include 'insert' or 'append' in your
requirements for the word 'access'.

>>computer, without the huge overhead incurred by preallocting
>>all memory to one array.
>
>I said nothing about preallocating all memory to one array.  My point
>was that if you want bidirectional random access you have to predict
>the maximum size in advance and allocate that much memory in advance.

	And my point is that you cant sensibly do this in most
situations, and you dont need to.

	As soon as you talk about 'preallocating' the array,
you have to allow me to 'preallocate' the cache of
my linked list.

	Then: BOTH our methods provide random read, write
and append operations. The cache is a bit slower, but only
by a constant factor. The cached list uses memory in proportion
to the number of elements in the 'actual' array plus
a constant amount. At maximum size, it uses more than the
preallocated array.

	The point of using something OTHER than an actual
preallocated array is: what happens if you need MANY of them,
and you know they wont ALL be full at once?

	Your method wastes HUGE amounts of memory. 

	An example: You have heard of the Tower of Hanoi?
(Three spikes with different sized disks you have to move about)

	Your system requires 3 x spike length records.

	My system needs 1 x spike length records. 

	Because the number of disks is fixed at spike length.

	But the maximum length of EACH spike is still spike length.

>
>To clarify what I mean by random access, consider a program whose
>access is literally random.  I.e., every access is driven by a
>random number, such that any item is as likely to be retrieved as
>any other.  Now consider moving the implementation from a fixed
>array to a linked list, and calculate the performance hit.  No
>amount of cache will help much unless it comes close to being on
>the same order of magnitude as the entire size of the storage,
>because, for example, if the cache is 10% of the storage size, 90%
>of all accesses will be cache misses.

	You dont understand, see my attempt at explaining above.
A suitable cache which is 1% the size of the list guarrantees
random read and write. End of story.

>
>But even for just random retrieval, it is hard to see how you could do
>it with a linked list.  Linked lists are for sequential access.  They
>are of course very handy, but that is because the majority of data
>retrieval applications only need sequential access, not random.

Use a array as a cache of course!

-- 
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------
Newsgroups: alt.amateur-comp,comp.org.eff.talk,soc.culture.usa,alt.activism