Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Best way to randomly select from an array without repeating

Author
Message
Deet
16
Years of Service
User Offline
Joined: 15th Mar 2010
Location:
Posted: 9th Mar 2012 23:18
Link
Here's the simplest way I could think to code it, which is what I am using now.



It successfully pulls the data and grows the plants in the game without placing any plants where they shouldn't be, or on top of one another. But I'm concerned with the repeat/until section and getting screwed over by the random number generator, resulting in hiccups while it tries to find a number that hasn't been used.

Is there a better way to pick data from an array without choosing the same data twice?
Back to top
Profile PM
basjak
16
Years of Service
User Offline
Joined: 16th Apr 2010
Location: feel like signing up for mars
Posted: 10th Mar 2012 05:44
Link
that will depend on how big the array is. in general It's better to shuffle the array before generating the plant, this way you will save plenty of time.



I think the swap function exists in matrix1_util pluggin as well.
Back to top
Profile PM Email Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 10th Mar 2012 17:29 Edited at: 10th Mar 2012 17:30
Link
I wouldn't want to use the repeat loop in game, because as you said, you don't know how long it's going to take to exit that loop. That's dangerous ground for a realtime game.

I would be tempted to loop through the array once, finding all the elements that are OK to use (e.g. when Pos(CPOS).act=0), and create a new array with those values in. You can then randomly select an item from that array.

Alternatively, you could:
1. loop through the whole array and count all the valid positions. Call that number "numValidPositions".
2. Choose a valid position by doing a chosenPos = rnd(numValidPositions)
3. loop through the array again, incrementing a position variable for each valid position you get to until you get to "chosenPos".

Hope that makes sense.

Back to top
Profile PM
Deet
16
Years of Service
User Offline
Joined: 15th Mar 2010
Location:
Posted: 10th Mar 2012 18:28
Link
Shuffling the array itself should work. I'll shuffle the order of location data, then pull the first available one. If I wanted to keep the order of the original data I'd put it in a new array, but that's not necessary here. Fallout's method would work too, it will just be a matter of seeing which one is fastest. Thanks for the help!
Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 10th Mar 2012 20:16 Edited at: 10th Mar 2012 20:16
Link
Fastest way is to swap each randomly picked item with the item at the end of the array and then only select from the first N-1 items next time.

ie.
A B C D E F

First random choice: D, so swap D and F:
A B C F E D

Second random choice (from first 5): B, so swap B and E:
A E C F B D

Third random choice (from first 4): C, so swap C and F:
A E F C B D

etc.

[b]
Back to top
Profile PM Email Website
BatVink
Moderator
23
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 10th Mar 2012 22:58
Link
Regarding speed, I wouldn't worry outside of the main game loop, I recently shuffled a 36,000 element array and had to check it actually happened because it was so fast...milliseconds.

Back to top
Profile PM Email
Alien002
15
Years of Service
User Offline
Joined: 25th May 2011
Location:
Posted: 11th Mar 2012 00:27
Link
there is a problem with swaping a rnd position with the last one in the list. The prolem is that rnd position does not give you every posible position. this mean that there will be some that have not been swap.
Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 11th Mar 2012 01:21 Edited at: 11th Mar 2012 01:22
Link
Quote: "there is a problem with swaping a rnd position with the last one in the list. The prolem is that rnd position does not give you every posible position. this mean that there will be some that have not been swap. "


That makes no sense, rnd does give you every possible position (except for the ones which have already been chosen obviously), and I know for a fact that it works perfectly...

[b]
Back to top
Profile PM Email Website
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 11th Mar 2012 02:17
Link
Quote: "there is a problem with swaping a rnd position with the last one in the list. The prolem is that rnd position does not give you every posible position. this mean that there will be some that have not been swap. "


I think you mean that if you shuffle a deck of cards you get repeats, but that's just bad programming, you can program a true deck of cards using rnd, it is just a matter of how you program it.

Back to top
Profile PM Email Website
Alien002
15
Years of Service
User Offline
Joined: 25th May 2011
Location:
Posted: 11th Mar 2012 16:12
Link
Here is a snippet to test what i mean by not every position and what you should use insted of rnd swap with last one.

Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 11th Mar 2012 17:37 Edited at: 11th Mar 2012 17:38
Link
This is all you need and it works fine...



[b]
Back to top
Profile PM Email Website
JRNTexas
15
Years of Service
User Offline
Joined: 24th May 2011
Location: Austin, Texas
Posted: 11th Mar 2012 20:50
Link
@Diggsey

I'm just curious. Why did you put the double sync in the code?

Quote: ""sync : sync""


Thanks!
Back to top
Profile PM Email Website
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 11th Mar 2012 22:39 Edited at: 11th Mar 2012 22:41
Link
Ah, there was a bug/feature in an old version of DBPro (may even have been DBC, can't remember) where you needed to call "sync" twice to display the result of 2d drawing commands on the screen in certain circumstances (presumably there was an extra layer of buffering). It didn't matter if you were in a loop, but if you were just printing some stuff out and then pausing it required an extra sync or you'd get a black screen.

[b]
Back to top
Profile PM Email Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 12th Mar 2012 00:26
Link
Quote: "Ah, there was a bug/feature in an old version of DBPro (may even have been DBC, can't remember) where you needed to call "sync" twice to display the result of 2d drawing commands on the screen in certain circumstances (presumably there was an extra layer of buffering). It didn't matter if you were in a loop, but if you were just printing some stuff out and then pausing it required an extra sync or you'd get a black screen."


I remember doing that. Them were the days. I'm pretty sure it works as expected now though.

Back to top
Profile PM
JRNTexas
15
Years of Service
User Offline
Joined: 24th May 2011
Location: Austin, Texas
Posted: 12th Mar 2012 07:31 Edited at: 12th Mar 2012 07:36
Link
@Diggsey,

Thanks for the reply and the info!

====

The code you posted works great and I appreciate it! Although I have a slight but significant problem with the numbers generated.

Calling rnd(maxSeed), directly, causes the random generator to create logic problems. The first is that it will generate one more possible number than the maxSeed. That number is zero. Since it generates one more possible number than you've asked, you have to set "maxSeed" to one number less (51 in the case of a deck of cards) but set your for/next loop to generate 52 numbers and add "1" to each to get the set of numbers you desire.

My solution is to not call rnd but to call a user function that generates numbers between two given numbers. In my code I call this function, "makeRandom(minSeed, maxSeed)".

Although it uses a while loop, (that theoretically could run for a long time) I have never seen it take very long (milliseconds) to execute.

It makes a complimentary addition to your code.

Back to top
Profile PM Email Website
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 12th Mar 2012 15:00 Edited at: 12th Mar 2012 15:00
Link
Ah, I see what you mean, but if you do what you've done you waste one element of the array (array indices start from zero, not one. In DBPro "dim myarr(51)" creates an array with 52 elements).

Also, you can avoid the loop in makeRandom like so:


Also, you shouldn't use "randomize timer()" in the makeRandom function, it should only be called once at the start of your code (and DBPro does this automatically, so in fact you don't need it at all!)
Repeatedly calling randomize() will make the results less random because the number returned by rnd() will be directly related to the timer() value.

[b]
Back to top
Profile PM Email Website
Pincho Paxton
23
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 12th Mar 2012 19:09
Link
Well yes.. 10 random numbers looks like this...

r = rnd(9) + 1

Back to top
Profile PM Email Website
Deet
16
Years of Service
User Offline
Joined: 15th Mar 2010
Location:
Posted: 12th Mar 2012 19:28
Link
Just to conclude, here's my new plant selector.



As TotalPlants goes from 0 to MaxPlants, plants grow in the cracks of outdoor floor tiles at randomly chosen positions. Then you spray the plants with weed killer, which the brand brags it will prevent weeds from growing back, hence the non-repeating requirement.

I like this method of randomly choosing elements, since it's easy to read and consistent with timing since the loop will be in-game. CPOS should never be able to exceed MaxPlants, but I put in the check for it anyway.
Back to top
Profile PM
JRNTexas
15
Years of Service
User Offline
Joined: 24th May 2011
Location: Austin, Texas
Posted: 13th Mar 2012 05:31
Link
@Diggsey, Pincho Paxton,

I like your solutions better than mine, no lag.
Back to top
Profile PM Email Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 13th Mar 2012 09:43 Edited at: 13th Mar 2012 09:51
Link
I've been continuing to read what others have said. That solution looks like it'll work a treat, but seems inefficient. I don't think shuffling an array just to select 1 item is efficient. It only makes sense if you want to extract all the items and only shuffle once.

Simply selecting the data you want makes more sense to me, and I would imagine is faster.



That's my preferred method anyway.

Back to top
Profile PM
Millenium7
21
Years of Service
User Offline
Joined: 13th Dec 2004
Location:
Posted: 13th Mar 2012 11:05
Link
whilst it may be slightly inefficient, keep in mind we aren't running on 266mhz pentium2's anymore. Unless you are running that sort of loop in the magnitude of 100,000+ per second, I highly doubt you'll see a drop of even 1fps at a typical 60fps rate.

So whilst it may make you feel all warm and fuzzy inside, the reality is it's going to be a massive waste of time to even think twice about it. Choose the most effective and easy method and run with it. I personally would rather get 3x more work done, than spend time and mental energy to squeeze out 0.0001% more performance
Back to top
Profile PM Email
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 13th Mar 2012 12:27
Link
Quote: "So whilst it may make you feel all warm and fuzzy inside, the reality is it's going to be a massive waste of time to even think twice about it. Choose the most effective and easy method and run with it. I personally would rather get 3x more work done, than spend time and mental energy to squeeze out 0.0001% more performance"


I totally agree 100% and it's a good point. Don't waste your time thinking about efficiency unless it's in a complex area of code that may have an effect on performance. It is far better to realise that the quick bit of code you've done is 'good enough' than to waste time finding the perfect solution.

Having said that, here it's all good learning to see all the different possibilities, and learn about your options for future coding problems. In this example, with my personal coding style, I feel more comfortable reading through a data structure to find the data I want, rather than sorting it. That probably comes from my expectation that there would be many instances where sorting a data structure may mess up something else I've done, which relies on it's order. The bug avoidance radar in my coding brain tells me to leave my data alone unless absolutely necessary.

Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 13th Mar 2012 17:06 Edited at: 13th Mar 2012 17:07
Link
Quote: "I don't think shuffling an array just to select 1 item is efficient."


Did you see my solution? It only does one swap for each item picked, equivalent to three variable assignments. Although micro-optimisation is not very useful and a waste of time, when dealing with large arrays it's very important to consider the time complexity of the algorithms you use.

Any solution which involves looping through the array requires at least O(n) time to pick each item, while a constant time solution such as mine will run in O(1) to pick each item. Even if there are only 100 items in the array, it can make a big difference if you're doing it many times each frame.

[b]
Back to top
Profile PM Email Website
Deet
16
Years of Service
User Offline
Joined: 15th Mar 2010
Location:
Posted: 13th Mar 2012 18:38
Link
My newest version of this code has the array shuffle taking place only once at the beginning of each round, and then the elements of the array are chosen in order. Works like a dream and I can remove a lot of things from the code.
Back to top
Profile PM
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 13th Mar 2012 20:18
Link
Quote: "Did you see my solution? It only does one swap for each item picked, equivalent to three variable assignments."


Missed that. That does indeed make sense.

Quote: "My newest version of this code has the array shuffle taking place only once at the beginning of each round, and then the elements of the array are chosen in order. Works like a dream and I can remove a lot of things from the code."


And that sounds like the best solution also.

Back to top
Profile PM
Mr Kohlenstoff
20
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Germany
Posted: 14th Mar 2012 13:35 Edited at: 14th Mar 2012 13:36
Link
Quote: "Diggsey: Ah, I see what you mean, but if you do what you've done you waste one element of the array (array indices start from zero, not one. In DBPro "dim myarr(51)" creates an array with 52 elements)."


That's true obviously, but I personally tend to use the 0-element as default-element for certain operations. For instance, functions that are meant to return an array index may return 0 if they fail instead of -1. This way I don't need to check whether the returned array index is valid all the time and may just continue, in this case working with the default value element 0 has.
Consequently I also usually use the "1+rnd(arraySize-1)"-kind of selection because 0 is handled as special case.
Well what I'm trying to say is that this solution is not necessarily a wastage of memory but can indeed be intended and useful, if done consciously.

Quote: "Any solution which involves looping through the array requires at least O(n) time to pick each item, while a constant time solution such as mine will run in O(1) to pick each item. Even if there are only 100 items in the array, it can make a big difference if you're doing it many times each frame."


Good point, but you're still messing up the array's order of content (even though not completely but one element at a time). In case there are references to this array using indices, you will certainly run into problems.
I'd like to note that I discussed a similar problem in this thread and praised permutations to be the best solution.
However, it's probably depends on the specific case whether those permutations are faster than your solution. First of all, with your random selection, you have to execute it an unknown number of times given that there's a selection-precondition (such as "Pos(CPOS).act = 0"), and this number might depend on n (which again depends on the specific case, i.e. how the array was set up and what 'act' stands for), resulting in O(n) once again.
On top of that, swapping elements by exchanging their individual values gets quite complex when using complex user defined types for that array. With permutations, all you have to do is "swap indices".

In the example posted by Deet the optimal solution might be found now, but as Fallout said:

Quote: "Having said that, here it's all good learning to see all the different possibilities, and learn about your options for future coding problems."


...hence this post.

Back to top
Profile PM Email
basjak
16
Years of Service
User Offline
Joined: 16th Apr 2010
Location: feel like signing up for mars
Posted: 14th Mar 2012 14:48
Link
@Mr Kohlenstoff: this thread has showed 2 way of shuffling. my one (on the top), second one by diggsey. I believe my way of shuffling is easier to understand but both do the same job.

however, if you're worried about keeping array in order, you can create another one, so you have main array and shuffling array. or you can sort this array everytime you shuffle it, using you own coding or by using Ian's matrix1_util pluggin. where you have more arrays commands including sorting.

don't worry much about the time of shuffling and sorting as your computer can sort and shuffle 1000s of elements in a fraction of a second.
Back to top
Profile PM Email Website
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 14th Mar 2012 16:28
Link
@basjak
Mine doesn't shuffle the array, it just swaps a single pair of items. If you keep picking items until the end it has the effect of shuffling the array, but an individual selection does not perform a shuffle.


Quote: "On top of that, swapping elements by exchanging their individual values gets quite complex when using complex user defined types for that array. With permutations, all you have to do is "swap indices"."


No it's exactly the same because DBPro supports assigning UDTs directly:



Quote: "Good point, but you're still messing up the array's order of content (even though not completely but one element at a time). In case there are references to this array using indices, you will certainly run into problems."

In this case, I would reference array elements by an ID given to each element rather than by index. However, it is unusual to have all three requirements for a single array of:
- Referencing items
- Selecting random items without replacement
- Reordering items
And if any of those is not required then there are more efficient solutions.

[b]
Back to top
Profile PM Email Website
Mr Kohlenstoff
20
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Germany
Posted: 14th Mar 2012 19:15 Edited at: 14th Mar 2012 19:18
Link
Quote: "however, if you're worried about keeping array in order, you can create another one, so you have main array and shuffling array."


This is just what the permutation library I mentioned in my post is doing.


Quote: "No it's exactly the same because DBPro supports assigning UDTs directly:"




Oh. I always wrote terribly long functions copying every single value of an UDT. Thanks for this important bit of information.

However - copying all those values will need more time than changing a single integer-value, doesn't it?


Quote: "In this case, I would reference array elements by an ID given to each element rather than by index."


How does this work? Wouldn't this require a search through the whole array for each access using a reference?

Quote: "However, it is unusual to have all three requirements for a single array of:
- Referencing items
- Selecting random items without replacement
- Reordering items"


When I worked on Dangerground I ran into a problem requiring just that. Imagine a zombie that is AI-controlled and currently without attack target. Every few loops it checks whether a human unit is in reach (e.g. within a distance of 20 meters) - if that's the case, it stores a reference to this unit as new attack target (->referencing items in the unit-array is required).
The condition of the potential attack unit to be 1. human and 2. within an area of 20 meters around the zombie usually applies to very few of all existing units, mostly to none, hence the whole array or a serious part of it has to be checked when looking for a new attack target. However, it is necessary to check those units in random order, because otherwise humans with low array-index would be attacked much more often than those with high index, which is not fair and leads to unbalanced gameplay. Consequently it is necessary to access a part or even the complete unit array in random order.

There may be a better solution than the permutation kind of thing, but the way I see it the three cases you mentioned above all need to be considered here.

Back to top
Profile PM Email
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 14th Mar 2012 19:51
Link
Quote: "No it's exactly the same because DBPro supports assigning UDTs directly:"


I've been using DBP since Lee drooled onto a napkin, saw an abstract stain of spittle, and gained inspiration for it's creation ... and I never knew you could do that! Since you can't have an array within a UDT, I always assumed UDTs were 'bare bones' implementations, and therefore I've never tried anything other than a basic use of them.

Thanks for pointing that one out! Should save me some lines of code in the future.

Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 14th Mar 2012 22:09
Link
Quote: "How does this work? Wouldn't this require a search through the whole array for each access using a reference?"


Usually, the usefulness of being able to reorder and resize the array outweighs the cost of a linear search, but in the cases that it doesn't, you can create another array which indexes the first and reorder that one instead, this also saves on copying UDTs although it's cost is minimal.

[b]
Back to top
Profile PM Email Website
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 15th Mar 2012 00:02
Link
Why would you need a linear search? Isn't the second, indexing, array just a simple extension of your original swapping suggestion?
Back to top
Profile PM Email
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 15th Mar 2012 00:36
Link
You need a linear search to find an item with a particular ID if you allow reordering. If you use a second array for indexing you don't need to do the linear search because you don't need to reorder the original array, which was what I was trying to say.

[b]
Back to top
Profile PM Email Website
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 15th Mar 2012 01:02
Link
Precisely. Which is why I asked the question.
Back to top
Profile PM Email
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 15th Mar 2012 22:43
Link
I've seen this or something like it in several places in this thread (sorry for picking your example Diggsey ):


That can be replaced with the faster:


It does no copying of the array items themselves, it simple swaps the pointers of the items.

Get the latest Matrix1Utility plug-ins (11-SEPT-2011)
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2026-07-10 09:48:18
Your offset time is: 2026-07-10 09:48:18