Re: Algorithm for inserting numbers in a list?

Chris <spam_me_not@xxxxxxxxxx> writes:

Martin Knoblauch Revuelta wrote:
You might use pointers to the nodes of the trees.

I think your solution is right.

Each element in my application is a word. List of words get added in
batches to the structure. Each word needs to point to other data
structures on disk. I had planned to assign numbers to the words, and
then in the other structures merely reference the word numbers.

Word numbers are actually a wonderful solution to many problems,
especially if you *don't* try to sort them. Just assign your word
numbers sequentially in the order you add words to your dictionary.
Then, you can make your main dictionary an array of word records
(indexed by that number). You keep the look-up by spelling
off-to-the-side, but when it finds a match, that match is the word
number/array index.

Note for this case, pointers and word numbers are generally equivalent
(especially since pointers are essentially simply numbers correspond-
ing to addresses in the machine). The advantage of a word number is
that it is generally portable, you can easily write it out to a file
and read it back in and know exactly what it is supposed to mean. The
advantage of a pointer (over a word number that is an array index) is
that it works easily on machines that have problems creating large
arrays.

Finally, just one note on your comment about the words being good
proxies themselves. In most cases that isn't true. My favorite
illustrative example on this is how the King James version of the
Bible is now routinely compressed using word numbers. The space
inhabited by consecutive integers is generally much more dense than
the space occupied by words for most definitions of what a word is.

Again, hope this helps,
-Chris

******************************************************************************
Chris Clark Internet: christopher.f.clark@xxxxxxxxxxxxxxxxxxxxxx
Compiler Resources, Inc. or: compres@xxxxxxxxxxxxx
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

.

Relevant Pages

  • Re: Differance between Array and Pointers
    ... Well, except that arrays tend to be much larger than pointers, and the ... An array is a contiguous region of memory containing N elements of M ... indexing vs. a loop). ...
    (comp.arch.embedded)
  • [RFCv2][PATCH] flexible array implementation
    ... I call it a flexible array. ... storage for pointers to the second level. ... all locking must be provided by the caller. ... make sure to pass in &ptr instead of ptr. ...
    (Linux-Kernel)
  • [RFC][PATCH] flexible array implementation v4
    ... I call it a flexible array. ... so never does an order>0 allocation. ... storage for pointers to the second level. ... all locking must be provided by the caller. ...
    (Linux-Kernel)
  • Re: [RFC][PATCH] flexible array implementation v4
    ... I call it a flexible array. ... so never does an order>0 allocation. ... storage for pointers to the second level. ... all locking must be provided by the caller. ...
    (Linux-Kernel)
  • Re: [RFCv2][PATCH] flexible array implementation
    ... I call it a flexible array. ... storage for pointers to the second level. ... all locking must be provided by the caller. ... make sure to pass in &ptr instead of ptr. ...
    (Linux-Kernel)