From: swillden@news.ccutah.edu (Shawn Willden)
Newsgroups: alt.amateur-comp,comp.lang.c,comp.lang.c++,comp.misc
Subject: Re: What is Object Oriented Programming? Is C doomed?
Date: 29 Dec 92 21:12:56 GMT
Organization: University of Utah Computer Center
X-Newsreader: Tin 1.1 PL3

maxtal@extro.ucc.su.OZ.AU (John MAX Skaller) writes:
: 	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.

This seemed like a pretty strong statement to me, but after thinking
about it for a while I came up with the following:

Consider an array of k pointers (k = n/100, n = # of items in the
list).  Let p = n / ( 1 + n/100 ) and let the ith pointer ( 1 <= i <=
k ) of the cache point to the (i*p)th node of the linked list.  Any
item in the list can be accessed by traversing < p nodes of the list.
For example: If the list contains 200 items (n=200) then the cache
contains only two pointers, one to the 66th element of the list and
one to the 132nd element of the list.  Since we always have the "head"
pointer that points to the 1st element of the list, any element in the
list can be accessed by traversing < 66 nodes.  Similarly, if the list
has 10000 items, our cache contains 100 pointers to the items whose
indices are multiples of 99 and any element in the list can be
accesses by traversing < 99 nodes.  

This looks good, but p depends on n, and access time depends on p, so
access time could be O(n) and we want O(1).  Taking the limit


                        n                100 n
              lim    -------  =  lim    -------  =  100
              n->oo       n      n->oo  100 + n
                     1 + ---
                         100

So there *is* an upper bound on random access time in an
arbitrary list and the actual access time improves as the list gets
smaller (as seen in the examples).  Notice also that the upper bound
depends on the size of the cache.  A cache with n/m elements requires
< m nodes to be traversed for any access.

A more intuitive explanation is this:  If your cache has n/100
elements, you can break the list up into n/100 + 1 pieces and know
easily which piece a given element is in.  Then, to find the element
you want you need only traverse the appropriate piece.  Since there is
1 element of the cache for every 100 elements of the list, the longest
any piece need be is 100 elements.  If you have 1 cache entry for
every m elements of the list, the longest a piece need be is m.

This technique allows random access (read/write) in known time and
also allows easy insertions and deletions.  Insertions and deletions
can require major changes to the cache (which could require traversal
of a large part of the list) but a reasonable algorithm could minimize
these, only adjusting the cache when, for example, some access
required 150 nodes to be traversed.  This would, of course, require
the cache to contain indices as well as pointers.

In addition, other optimizations could allow for even faster access
when the elements are accessed in common ways, such as sequentially.

John:

	Is this scheme similar to the one you had in mind?  If yours
is better, please share it (or provide references, I suppose I ought
to check Knuth to see if he has anything like this).

In any case, I like the idea well enough that I think I'm going to
start using it.

: -- 
: ;----------------------------------------------------------------------
:         JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
: 	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
: ;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

--
Shawn Willden
swillden@icarus.weber.edu
Newsgroups: alt.amateur-comp,comp.lang.c,comp.lang.c++,comp.misc