This is kind of difficult to explain, so bear with me.
I'm looking for a way to generate a unique but random ID number in a narrow range of possible values, so that the numbers are evenly distributed, most, if not all, of the numbers in the range are used, and the process of generating the numbers isn't too slow as the available pool of values shrinks.
I want to populate a database with a unique random number for use as a key, within certain limits (pseudo-random, not truly random.) The key should fall within a range of values, for example between 1,000 and 10,000, and it must be unique of course.
This doesn't seem too difficult, but here's where I am having trouble: When I generate an ID, I will need to check to see if it has been used previously, and if it has, I will need to pick another one, try it again, repeating the process until an unused ID is found.
As the number of generated IDs increases, the available pool of IDs will shrink, and the time it takes to find the next available random number within the range will increase, and eventually, it will get bogged down searching thousands of records for the few remaining unused values. Checking an id against the existing data is expensive, so I want to minimize the number of times I have to do this.
At some point, the process will take too long, and that point, I will then change the range of possible values so as to start a new set of numbers.
To put this another way, I want to generate random IDs that are evenly distributed within a range, until it becomes inefficient to do so, at which point the range is altered to make it efficient once more. The goal is to keep the maximum range of numbers to be used as small as possible, and as densely populated with IDs as possible, while not becoming ridiculously slow. This process needs to be implementable in a fairly simplistic scripting language without complicated data structures, arrays, or pointers.
I guess I have three questions: 1) Is there an efficient way to identify possible "gaps" in the range where a number might be available? 2) At what point does it become worthwhile to add a new range of numbers? For example, statistically, how many collisions would I need to have in a row before I should conclude that a range of values is "used up" and no longer worth trying to search? Or is there a better way to make that determination? 3) Is there some sort of deterministic way to generate such a sequence of IDs that LOOKS random? (It needn't be cryptographically unpredictable or anything like that, just non-obvious.
I'm looking for ideas and maybe algorithms, maybe some pseudocode?
With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.
The Grade of the Solution
The Zone Rank of the Expert Providing the Solution
The Number of Author and Expert Comments
The Number of Experts Contributing
The Feedback of the Community
Your Input Matters Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.
If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.
