I wanted to visually see what was happening whilst randomly filling a Python list or dict with a value. For these examples, I used (mainly) identical code to produce the visuals, but changed the main loop method.
I created the the first program with what I thought was the best method, but was quickly disappointed
The First Attempt
I started by creating an empty dict of 100 key/value pairs; this will be my working space. I felt 100 was a nice round number to use, and it easily fits within the confines of a terminal.
Using a loop, I randomly choose a number between 0 – 99 and change the corresponding dict value to “x” resembling a change.
If the dict value had already been changed, it loops over until a new unchanged value is picked. The program stops when all values have been changed.
The whole process took little time to execute, so decided to slow down the program with the sleep method to clearly see the changes.
In the video, the end result was a total of 415 conflicting random picks and 100 successful picks. This really surprised me as I have used this method in some programs before, but never realised how inefficient it actually was.
This approach essentially uses brute-force to change the values, without any control. I needed control.
The Second Attempt
Thinking about the problem, control was key. Infact, the key is control. With every filled dict value, the probability of getting an unchanged value goes down.
Ideally, the probability of getting an unchanged value should be (or as close to) 100% to be efficient.
I decided to create a new list, based on the dicts’ keys. From there, I could randomly select a value from the list, change the value of the corresponding dict key, and then remove the key from the list. I will be left with a list of dict keys which are yet to be populated. This means that every random pick will always be an empty value. I gave it a go and it worked really well!
As you can see, 0 conflicts; there can’t be a conflict. The only downside to this might arguably be the overhead of manipulating the list and storing the list, especially if the dict key is a string rather then an integer. However I am certain that the likelihood of the first example picking 100/100 keys on the first 100 loop iterations is really low.
In the examples above, I used dicts as the data medium. Obviously with some tweaking, you could use lists. Infact, if you use the first method especially, you SHOULD use a list/index (unless the dict key is indexed by an integer)
Secondly, you will need to pre-allocate the desired length in the list in order to prevent list index exceptions!