Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!spool.mu.edu!uunet!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Heaps and other data structures (was: interesting exercise)
Message-ID: <4790@goanna.cs.rmit.oz.au>
Date: 19 Feb 91 12:09:16 GMT
References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <17853@cs.utexas.edu>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 64

In article <17853@cs.utexas.edu>, turpin@cs.utexas.edu (Russell Turpin) writes:
> As a simple
> example, consider a tree each data node of which contains (1) a
> person's name (and associated data), and (2) a pointer to the
> node of that person's spouse.  The goal is to support a search
> through the tree for a named individual, and to then retrieve the
> data for the spouse in constant time. 

The answer when presented with a problem like this is to refuse to do
it.  Take a step back.  Ask "what is this useful for?"  Do something
else that is clean and fast and solves the problem.

Imagine, then, that we are given as our raw data, two lists:
a list of Person-Info pairs	People
a list of Person-Person pairs	Matings
and we want to have a data structure supporting both
	person_info(Person, Collection, Info)
	person_and_spouse_info(Person, Collection, PersonInfo, SpouseInfo)

"search for a named individual and retrieve the data for the spouse in
constant time".

Step 1:	sort People
Step 2: make Matings symmetric (so X-Y and Y-X are both present)
	and sort it.
Step 3: merge the sorted People and Matings, producing a new
	Mated list, holding Person-mating(Spouse,PersonInfo,SpouseInfo)
	pairs.
Step 4:	build a fast access structure for People, PeopleIndex
	(say a binary tree)
Step 5: build a fast access structure for Matings, MatingsIndex	
	(say a binary tree)
Step 6:	represent the entire collection by a pair
	collection(PeopleIndex,MatingsIndex)

	person_info(Person, collection(PeopleIndex,_), Person-Info) :-
		lookup(Person, PeopleIndex, Info).

	person_and_spouse_info(Person, collection(_,MatingsIndex),
 			Person-PersonInfo, Spouse-SpouseInfo) :-
		lookup(Person, MatingsIndex,
			mating(Spouse,PersonInfo,SpouseInfo)).

You don't have cross-links *within* the structure.  Instead you have
multiple index structures *above* your raw data.

No, this doesn't do it the *way* that the poster demanded.
So?  In a real application, you shouldn't *care*.  You should
care about correctness and efficiency, but not how it's done.

What's more, in a real application, it's not clear to me why it is
so all-fired important to get to the spouse (which one?) in constant
time.  If it takes O(f(N)) time to get to the first person and find
there the spouse's name, then it'll take O(f(N)) time to get to the
spouse, so the total will be O(f(N)) + O(f(N)) which is still O(f(N)).

Bottom line:
    Yes, some *ways* of doing things *are* slow in Prolog.
    If you want a language that'll let you hack arbitrary data
    structures any way you want, use C++ (and *some* day they'll
    tell you what it means, maybe).  

-- 
Professional programming is paranoid programming