NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/alt/amateur/398

Internet Message Format | 1992-12-23 | 4.4 KB

Xref: sparky alt.amateur-comp:398 comp.lang.c:18821 comp.lang.c++:18343 comp.misc:4691
Newsgroups: alt.amateur-comp,comp.lang.c,comp.lang.c++,comp.misc
Path: sparky!uunet!spool.mu.edu!umn.edu!csus.edu!netcom.com!erc
From: [e-mail] (Eric Smith)
Subject: Re: What is Object Oriented Programming? Is C doomed?
Message-ID: <[e-mail]>
Organization: Netcom - Online Communication Services (408 241-9760 guest)
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Wed, 23 Dec 1992 13:43:25 GMT
Lines: 90

In article <[e-mail]> [e-mail] (John MAX Skaller) writes:
>>>>But if you need bidirectional random access, you have to allocate the
>>>>entire maximum size in advance.
>>>
>>>    There are NO 'you have to .. ' cases surely, even if
>>>I give some myself now and then :-) And allocating fixed maximums
>>>is one of the things we want to avoid completely except in truly
>>>extreme cases.
>>
>>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.


>
>    This sort of analysis is usually done using
>dependencies on the sizes, for example the time
>taken to scan a linked list is O(n) for n elements,
>and no amout of delaying will fix this.
>
>    So what you should have said was that
>if you want constant, i.e. O(1) access you have to
>preallocate the array, because reallocation is O(n).
>This proves nothing, however: you have to show
>indexed access to contiguous storage is the only
>O(1) access method.


My proof did not mention indexed access nor contiguous storage.


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


>
>    In practice, more advanced techniques can yield only
>slightly slower performance than the array that are close
>enough to being constant time over the usable memory of your
>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.

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.

There are lots of ways to implement random access storage, not just
fixed arrays, but you do have to allocate the entire maximum size in
advance if you want bidirectional random access.

Fortunately, applications that need bidirectional random access are rare.
Random retrieval is much easier that random bidirectional access because
there is no need to allocate the maximum size in advance.

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.