Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Eotha

How do I generate random unique identifiers?

This topic is 6086 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a system where I am generating unique 32 bit identifiers for items. At the moment my unique numbers are very simple, the first item to be created gets ID 1, the second ID 2 and so on. However, due to the number of items, I want to put them into a tree sorted on the ID to perform a search. Of course, a tree with a linearly generated ID becomes a list ... I could rebalance the tree occasionally in some way to avoid this problem. However, this could be fairly time consuming. So, I was wondering if anyone had any great ideas about how to generate a pseudo random unique 32 bit ID based upon a linearly increasing number? This should mean that adding the new items into the tree should keep it relatively well balanced. Thanks

Share this post


Link to post
Share on other sites
Advertisement
At a guess you could start the ID at a prime number P this number would be about 28/29/30 bits in size, than add this to the ID every time thus:

start:
ID = P

ID = (ID + P) % ((2^31) - 1)

this should 'balance' the values across the ID value space without generating duplicates.

This is off the top of my head.I used to do something similar to 'fade in' and 'fade out' bitmaps on the Spectrum, circa 1983.

The fade would be even across the image, implying that the points added and removed were about the same distance from the previous point as the next fade point. In english, smooth.


Here is a dry run, using 4 bit ID space (0 - 15) and a Prime of 5

Key values generated would be:
5
10
15
4
9
14
3
8
13
2
7
12
1
6
11

It isn't perfect but it should allow you to have a balanced search tree.



D.V.

Carpe Diem

Edited by - DeltaVee on November 19, 2001 2:08:15 PM

Share this post


Link to post
Share on other sites
I was having a similar problem with wanting to build a binary tree where the values of the IDs themselves were meaningless, but must scattered enough so my tree would remain balanced without me having to re-sort the tree while inserting. This is what I came up with (forgive me, it's in Java):

  
public class IDGen {

private static final int CAP = 1073741824;
private static final int MAX = CAP + 1;

private int parent;
private int step;
private int value;

/** Creates new IDGen */
public IDGen ()
{
step = 0;
value = MAX;
}

public int genID ()
{
value += step;
if (value == MAX)
{
step = parent = value = CAP >> 1;
}
else if (value >= CAP)
{
step = parent;
parent = value = parent >> 1;
}
return value;
}
}


This code generates a sequence of numbers that are ideal for inserting into a binary tree. Check out the output if you set CAP to 16 and generate 15 ids.

  
8
4
12
2
6
10
14
1
3
5
7
9
11
13
15


If every new node's id is sequentially generated by the same generator object, the tree is guaranteed to remain balanced without sorting.

The CAP variable must be a power of 2 and must be capable of fitting in the number of bits in your datatype - 1 (in Java everything is signed, so I use 2 ^ 30). It will produce all of the numbers in (1,CAP] before wrapping and producing the same sequence again.

// EDIT: I was playing with it and made it a bit more efficient.

"So crucify the ego, before it's far too late. To leave behind this place so negative and blind and cynical, and you will come to find that we are all one mind. Capable of all that's imagined and all conceivable."
- Tool



Edited by - wayfarerx on November 19, 2001 4:26:53 PM

Edited by - wayfarerx on November 19, 2001 5:27:13 PM

Share this post


Link to post
Share on other sites
It looks like both of these options will do a good enough job. I''ll give them a try and see what happens.

Thanks for your help.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!