[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
:zz: Great hack I just learned for linked lists
- To: zzdev@xxxxxxxxxx
- Subject: :zz: Great hack I just learned for linked lists
- From: Ted Nelson <ted@xxxxxxxxxx>
- Date: Sat, 19 Dec 1998 19:57:13 -0800
- Cc: ted@xxxxxxxxxx
- Reply-to: zzdev@xxxxxxxxxx
Hi folks--
(I still won't be reading email for a couple more days)--
At the reception after the Dougfest last week (the 30th
anniversary of Engelbart's great presentation),
a game programmer told me a great efficiency hack for
linked lists. He said it's well known among game programmers
but not otherwise. (Some of you no doubt know it already,
but hey, if I can light just one candle ...)
Two items point at each other mutually. Stored with each
is the same number:
A series of items need to be chained for fast doubly-linked
retrieval. This can be stored as a list, in which each item
is the XOR of the addresses of two consecutive items.
Since it is assumed that you have one of the two addresses
in hand, the other one you want is the XOR of the one
you already have.
(This doesn't help a lot with the insertion and deletion of items,
but that we somehow do differently.)
THIS MAY NOT HELP US, of course, since the problem is that
each cell is potentially on numerous linked lists (ranks),
and WHETHER it participates in a dimension is not yet
immediately known. This is why we currently use hash
databases. However, maybe we could figure some way
to crank this up for greater efficiency ...
(Mark-Jason, I may be way behind you, I know you said
it could be done with (I think) three columns, this whole
chunk of info could be superfluous.)
Ciao for niaow, T
________________________________________________________
Theodor Holm Nelson, Visiting Professor of Environmental Information,
Keio University, Shonan Fujisawa Campus, Fujisawa, Japan _____
http://www.sfc.keio.ac.jp/~ted/ ______
Permanent Address: Project Xanadu, 3020 Bridgeway #295, Sausalito CA 94965
_____ World Wide Fax +1-415-332-0136 World Wide Voicemail:
+1-415-331-4422 _____ PERMANENT E-MAIL: ted@xxxxxxxxxx
_________________________________________________________
Quotation of the day, 19 December 98:
"Denial is the longest river in the world." TN94