Re: Algorithm for inserting numbers in a list?

Martin Knoblauch Revuelta wrote:
On 8 abr, 18:36, Chris <spam_me_...@xxxxxxxxxx> wrote:
I have a list of N elements. Each element needs to be assigned an
ascending number, such that the number assigned to the first element is
less than the one for the second, which is less than the third, ... The
number assigned to an element can never change.
[..]

Does it have to be a number? Could it be something else?

You might use pointers to the nodes of the trees. Balancing the tree
doesn't change them. They are not "ascending numbers", but they refer
ascending positions within the in-order traversal of the tree. That
is, using the tree, you can check whether one is lesser or greater
than other one in terms of their positions in the sequence (in
logarithmic time). Of course, this is valid only while you have the
tree... But if you don't, you can map some unique identifiers to the
pointers...

Could you give some more details? Why do you need such a structure?

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. The difficulty is that the other structures are so large (hundreds of gigabytes) that they can't be rewritten when word numbers change.

I've come to the conclusion that using word numbers is not a good idea because of the difficulties pointed out by multiple people above -- the keys could get very long. The words themselves are the best keys available. So what this means is that each word needs to be duplicated -- once in the main structure, and once in each secondary structure. This will be space-inefficient, but not extremely so. Key prefix compression will help.

I can get away with this because the words won't be extremely long. If each word was much bigger, then I'd have to go with one of the surrogate key schemes described above.

Thanks, everyone, for the suggestions.
.

Relevant Pages