In some applications we need random numbers, which are all different. There is a simple method to generate them one by one: compare each new random number to all previously generated- and in a list stored- numbers. If no collision is found, attach the new number to the list. You can see that the running time grows at least quadratically with the length of the list, n.
Using priority queues, heaps or other complicated data structures speeds this up to n log(n). Similar expected running time can be achieved if we generate more numbers than needed, sort the list (with attached indices), so the equal numbers get next to each other. A simple scan now finds and removes repetitions. If enough numbers are left, just sort the list, now according to the original indices and we get a random sequence without repetitions. Unfortunately, we either have to write very complicated scripts or use external programs, like SORT.
But there is a way around. Hopefully, AHK uses internally those fancy data structures to find variables. Even if not, the internal search is done by compiled code, not by an interpreted script. We should achieve a great speedup by taking advantage of the variable naming capabilities of AHK. Here is how:
As the firs number is generated, say R_1 = 10, we create a variable called Index_10. We assign the index of the generated number (1 from R_1) to it. At a later stage, if we encounter the same value again, like R_8 = 10, we check Index_10. Now it exists and contains an index: 1. So, we found a repetition. We have to try generating a new R_8. If R_8 is now 9, and this is the first time the value 9 occurs, there will be no Index_9 defined, so we create it, and store the index 8 of R_8 in there.
Is there a problem here? (Think a bit before you read further.) What happens if there is an Index_9 environment variable already defined by some Windows process or by our own script, in a previous run? It is quite slow to clear all possible Index_x values before the script runs. But is it necessary?
NO! To protect ourselves from a leftover Index_9 variable, with some wrong value j in it, we check if j is a number, if it is between 1 and the current index of the generated random number (8 from R_8) and if it really points to an R_j, which has the value 9. If all these are true, we know that Index_9 is not garbage, we can safely use it.
Here is the script, which should generate unique random integers really fast.
Code:
MIN = 0
MAX = 99
N = 10
If (Max - Min + 1 < N)
{
MsgBox Cannot have %N% different numbers between %MIN% and %MAX%
return
}
Loop %N%
{
i := A_Index
loop
{
Random R, %MIN%, %MAX% ; R = random number
j := Index_%R% ; get value from Indexes
If j is number
If j between 1 and % i - 1
If (R_%j% = R)
continue ; repetition found, try again
Index_%R% := i ; store index
R_%i% := R ; store in R_1, R_2...
break ; different number
}
}
MsgBox %R_1%`n%R_2%`n%R_3%`n%R_4%`n%R_5%`n%R_6%`n%R_7%`n%R_8%`n%R_9%`n%R_10%
Login
Register
FAQ
Search
