pdbain@wateng.UUCP (Peter Bain) (01/28/85)
Say I had a set of records, which I represented as a vector of pointers.
Suppose further that I wanted to test for set membership by comparing
pointers. If I keep the vector sorted by increasing pointer value,
I can do the test in O(lg(N)), using a binary search, but I need
< and > on pointers. If all I have is == and !=, it takes O(N) time.
--
- peter bain
...!{allegra|decvax|clyde|ihnp4 }!watmath!wateng!pdbain
hard mail: CCNG, CPH-2369A, University of Waterloo,
Waterloo, Ont. Canada N2M 5G4
telephone: (519) 885-1211 x2810gvcormack@watdaisy.UUCP (Gordon V. Cormack) (01/29/85)
> Say I had a set of records, which I represented as a vector of pointers. > Suppose further that I wanted to test for set membership by comparing > pointers. If I keep the vector sorted by increasing pointer value, > I can do the test in O(lg(N)), using a binary search, but I need > < and > on pointers. If all I have is == and !=, it takes O(N) time. > - peter bain If one could get the representation of the pointer (say, as an integer) one could test for membership in O(1) time using hashing. -- Gordon V. Cormack CS Department, University of Waterloo gvcormack@watdaisy.uucp gvcormack%watdaisy@waterloo.csnet
ndiamond@watdaisy.UUCP (Norman Diamond) (01/29/85)
> > Say I had a set of records, which I represented as a vector of pointers. > > Suppose further that I wanted to test for set membership by comparing > > pointers. If I keep the vector sorted by increasing pointer value, > > I can do the test in O(lg(N)), using a binary search, but I need > > < and > on pointers. If all I have is == and !=, it takes O(N) time. > > - peter bain > > If one could get the representation of the pointer (say, as an integer) > one could test for membership in O(1) time using hashing. > -- Gordon V. Cormack Of course, one could compare the "pointees", or some component of the pointees. Or, one could hash on some component of the pointees. If only one component is compared, then the test slows down to compare the remaining components. Hey, we've found another "methodology" bug in the datatypes provided by Pascal. Still, the problem is not only that the language doesn't "want" to let you do < and > on pointers. On some machines, an address requires more bits than an integer, and a comparison requires several machine instructions. Also, Pascal run-time support might incorporate a suggestion someone published a few years ago, to check for dereferencing nil or "disposed" pointers; then a comparison might require even more instructions to mask out the extra information. If that's not enough, extending this technique a little bit would make automatic garbage collection feasible (with no change to the source language). Comparisons other than == and != do not provide you with any useful information, unless you take advantage of machine and compiler dependencies. -- Norman Diamond UUCP: {decvax|utzoo|ihnp4|allegra|clyde}!watmath!watdaisy!ndiamond CSNET: ndiamond%watdaisy@waterloo.csnet ARPA: ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa "Opinions are those of the keyboard, and do not reflect on me or higher-ups."
crs@lanl.ARPA (02/01/85)
Oops! Sorry.
russell@muddcs.UUCP (Russell Shilling) (02/09/85)
I may be full of blue mud, but I think the original question which
prompted the mass of 'pointer' articles was actually about comparing the
*values pointed to* rather than the *pointer value*. For example, the
question contained:
if p < q ...
I think the solution might be to recode as:
if p^ < q^ ...
This compares the items pointed to, rather than the address. Anyway, I think
that's what was meant.
--
Russell Shilling
UUCP: { allegra, ihnp4, seismo }!scgvaxd!muddcs!russell
ARPA: muddcs!russell@ucla-cs
Always eat from the four basic food groups:
Beer, Ice Cream, Chips and Salsa