Hello,

I want to make a fast and an efficient algorithm that will generate massive arrays of unique random numbers(it works fine until 10000 random numbers, after that it gets very slow). Here are my two scripts, please tell me
what can I improve on these scripts

Script #1(Repeatedly tries to generate random numbers and add them if the number does not exist in the list)

define add (how_much) elements in random order
repeat (how_much)
set [new_element v] to (pick random (1) to (how_much))
repeat until <not <[my_elements v] contains (new_element) ?>>
set [new_element v] to (pick random (1) to (how_much))
end
add (new_element) to [my_elements v]
end

Script #2(Uses a list to define what all the unique numbers will be then the new random number will be selected from the list)

define add (how_much) elements in random order
delete (all) of [elements_to_add v]
set [i v] to [0]
repeat (how_much)
change [i v] by (1)
add (i) to [elements_to_add v]
end
set [elements_left_to_add v] to (length of [elements_to_add v] :: list)
repeat (how_much)
set [new_element v] to (item (pick random (1) to (elements_left_to_add)) of [elements_to_add v] :: list)
add (new_element) to [my_elements v]
delete (item # of (new_element) in [elements_to_add v] :: list) of [elements_to_add v]
change [elements_left_to_add v] by (-1)
end

In your first script, why you repeat “how much”?
I have not tested, but i'd say that it will add numbers being the whole range from 1 to “how much”.
Couuld you share a project with such script ?

In the second one don't make Scratch search for the item to delete. Set a variable to the random number so you can refer to it both when copying and when deleting. You could also try just using length of the list for the upper bound for the random block instead of the variable you have - depends how Scratch handles the size of the list whether that will help.

I'm guessing these are running with no screen refresh but if that's the case and the custom block can't run within, I believe, 0.5 seconds it will actually lag badly. If that's the case splitting things up may help - eg add 5000 values in a call to your first version and then call it again to add another 5000. That can also be done in the second case if you move the list creation out of the main block - in fact you could try that anyway; have one custom block to set up the list and another to do the selection.

Oumuamua wrote:

In your first script, why you repeat “how much”?
I have not tested, but i'd say that it will add numbers being the whole range from 1 to “how much”.
Couuld you share a project with such script ?

If you want to generate a list to pick random numbers, all that yo need to do is

Oumuamua wrote:

In your first script, why you repeat “how much”?
I have not tested, but i'd say that it will add numbers being the whole range from 1 to “how much”.
Couuld you share a project with such script ?

Good point - in fact in both cases you're actually just creating a randomised copy of the list which can be done more easily in other ways. Searching for the last few elements in the first script is very inefficient.

thisrunShubhankar wrote:

Hello,
I want to make a fast and an efficient algorithm that will generate massive arrays of unique random numbers(it works fine until 10000 random numbers, after that it gets very slow). Here are my two scripts, please tell me
what can I improve on these scripts

Note 1: The example scripts do not generate random numbers.
They sort a group of numbers up to a maximum into a random order.

They approximate random numbers very well in some situations eg. if you use 100 of the 10000 numbers.

Note 2: My algorithm below, which is similar but shorter than your second example, got slower at list sizes somewhere above 40,000.
Time at 40,000 items showed as 0, 50,000 took 0.52 secs, 100,000 took 2.52 seconds.
So it still slows down a lot!

define add (how_much) elements in random order
delete (all) of [elements_to_add v]
set [i v] to [0]
repeat (how_much)
change [i v] by (1)
insert (i) at (pick random (1 v) to (i)) of [elements_to_add v]
end

Edit: ninja'd by a few posts

Oumuamua wrote:

In your first script, why you repeat “how much”?
I have not tested, but i'd say that it will add numbers being the whole range from 1 to “how much”.
Couuld you share a project with such script ?

Here is the link for the scripts(1 and 2):
https://scratch.mit.edu/projects/400142266/

thisrunShubhankar wrote:

Oumuamua wrote:

In your first script, why you repeat “how much”?
I have not tested, but i'd say that it will add numbers being the whole range from 1 to “how much”.
Couuld you share a project with such script ?

Here is the link for the scripts(1 and 2):
https://scratch.mit.edu/projects/400142266/

Well, for what stuff you need the list?

Oumuamua wrote:

thisrunShubhankar wrote:

Oumuamua wrote:

In your first script, why you repeat “how much”?
I have not tested, but i'd say that it will add numbers being the whole range from 1 to “how much”.
Couuld you share a project with such script ?

Here is the link for the scripts(1 and 2):
https://scratch.mit.edu/projects/400142266/

Well, for what stuff you need the list?

The list is needed for a sorting algorithm I am making.

But are you wanting to randomise a list or select a random subset from a list? These are very different.

Simple example. Say you had a list of 1000 items and you've picked 999 of them. How long do you think it might take to pick the last one by randomly picking between 1 and 1000?

Here is the fastest script I could make:

define add (how many) elements in random order
delete (all v) of [elements v] // Delete all the elements in the list.
set [x v] to [1]
repeat (how many) // Add each number, in order, to the list.
add (v) to [elements v]
change [x v] by (1)
end
set [x v] to [1]
repeat (how many) // For each item in the list...
set [y v] to (pick random (x) to (how many)) // Pick a random item that hasn't been chosen yet.
set [temp v] to (item (y) of [elements v]) // Swap the two items.
replace item (y) of [elements v] with (item (x) of [elements v])
replace item (x) of [elements v] with (temp)
change [x v] by [1]
end

First, it adds each number to the list in order (1, 2, 3, 4…). After that, it looks at each item of the list in order. For each item, it chooses a randomly selected number in the list that hasn't already been looked at, and swaps the two.

You can think of it like this: if it's looking at a certain item in the list, all the items that come after it are those that haven't been ‘chosen yet’, and the items that come before it have already been ‘chosen’. When it ‘chooses’ a number that hasn't been chosen yet, it swaps the two and then looks at the next item, which means that the item that it has just swapped in is now considered to be ‘chosen’, and only the numbers that haven't been ‘chosen’ yet come after that item in the list.

The advantage of this script is that it never needs to insert or delete items in the middle of a big list, which means that Scratch never needs to shift items down or up in the list. This would otherwise be a major cause of slowdown.

Using the above script, generating 50000 randomly ordered items only takes around half a second - and even less without screen refresh!

rdococ wrote:

Here is the fastest script I could make:

define add (how many) elements in random order
delete (all v) of [elements v] // Delete all the elements in the list.
set [x v] to [1]
repeat (how many) // Add each number, in order, to the list.
add (v) to [elements v]
change [x v] by (1)
end
set [x v] to [1]
repeat (how many) // For each item in the list...
set [y v] to (pick random (x) to (how many)) // Pick a random item that hasn't been chosen yet.
set [temp v] to (item (y) of [elements v]) // Swap the two items.
replace item (y) of [elements v] with (item (x) of [elements v])
replace item (x) of [elements v] with (temp)
change [x v] by [1]
end

First, it adds each number to the list in order (1, 2, 3, 4…). After that, it looks at each item of the list in order. For each item, it chooses a randomly selected number in the list that hasn't already been looked at, and swaps the two.

You can think of it like this: if it's looking at a certain item in the list, all the items that come after it are those that haven't been ‘chosen yet’, and the items that come before it have already been ‘chosen’. When it ‘chooses’ a number that hasn't been chosen yet, it swaps the two and then looks at the next item, which means that the item that it has just swapped in is now considered to be ‘chosen’, and only the numbers that haven't been ‘chosen’ yet come after that item in the list.

The advantage of this script is that it never needs to insert or delete items in the middle of a big list, which means that Scratch never needs to shift items down or up in the list. This would otherwise be a major cause of slowdown.

Using the above script, generating 50000 randomly ordered items only takes around half a second - and even less without screen refresh!

Thanks - I will try to implement this algorithm and test it. Do I have to give credit for your script?

rdococ wrote:

Here is the fastest script I could make:

define add (how many) elements in random order
delete (all v) of [elements v] // Delete all the elements in the list.
set [x v] to [1]
repeat (how many) // Add each number, in order, to the list.
add (v) to [elements v]
change [x v] by (1)
end
set [x v] to [1]
repeat (how many) // For each item in the list...
set [y v] to (pick random (x) to (how many)) // Pick a random item that hasn't been chosen yet.
set [temp v] to (item (y) of [elements v]) // Swap the two items.
replace item (y) of [elements v] with (item (x) of [elements v])
replace item (x) of [elements v] with (temp)
change [x v] by [1]
end

First, it adds each number to the list in order (1, 2, 3, 4…). After that, it looks at each item of the list in order. For each item, it chooses a randomly selected number in the list that hasn't already been looked at, and swaps the two.

You can think of it like this: if it's looking at a certain item in the list, all the items that come after it are those that haven't been ‘chosen yet’, and the items that come before it have already been ‘chosen’. When it ‘chooses’ a number that hasn't been chosen yet, it swaps the two and then looks at the next item, which means that the item that it has just swapped in is now considered to be ‘chosen’, and only the numbers that haven't been ‘chosen’ yet come after that item in the list.

The advantage of this script is that it never needs to insert or delete items in the middle of a big list, which means that Scratch never needs to shift items down or up in the list. This would otherwise be a major cause of slowdown.

Using the above script, generating 50000 randomly ordered items only takes around half a second - and even less without screen refresh!

Another good spot. Not changing the size of the list is much more efficient for long lists and, in fact, this method works whether you want a subset or a completely randomised list.

Which method is most efficient always depends on the numbers involved. This would be overkill to create a list of 10 numbers from the range 1 to 1000 for example.

thisrunShubhankar wrote:

rdococ wrote:

-snip-

Thanks - I will try to implement this algorithm and test it. Do I have to give credit for your script?

Not at all, I'm just glad I could help.

Create list:

define create list - length (length)
delete (all v) of [templist v]
set [count1 v] to [0]
repeat (length)
add (count1) to [templist v]
change [count1 v] by (1)
end

Main script:

define random numbers - amount: (amount)
create list - length (amount)
delete (all v) of [randlist v]
repeat (amount)
add (item (pick random (1) to (length of [templist v] :: list)) of [templist v] :: list) to [randlist v]
end

WildTraces wrote:

Create list:

define create list - length (length)
delete (all v) of [templist v]
set [count1 v] to [0]
repeat (length)
add (count1) to [templist v]
change [count1 v] by (1)
end

Main script:

define random numbers - amount: (amount)
create list - length (amount)
delete (all v) of [randlist v]
repeat (amount)
add (item (pick random (1) to (length of [templist v] :: list)) of [templist v] :: list) to [randlist v]
end

Doesn't avoid duplication of values.

Hello everyone,

I came back from my homework task. I will test each of the scripts and compile them into one project. Thanks for helping, it's been a great pleasure!