Shulou(Shulou.com)06/03 Report--

Knuth efficient shuffle algorithm example analysis, I believe that many inexperienced people do not know what to do, so this paper summarizes the causes of the problem and solutions, through this article I hope you can solve this problem.

Today, I encountered a problem when I was doing a game. The problem is very simple. Given 75 balls, numbered 1-75, I need to make sure that the initialization position is random.

Obviously, we can initialize an array A, put 75 numbers in it, and then do a shuffle function to randomly exchange the elements in it, which is random.

I'm going to do a shuffle like this, but I also want to see if there is such an interface in golang to get the result directly. This function is rand.Perm (n), which returns an array. For example, when I pass 75, it returns a random array of 0-74.

Arr: = rand.Perm (75)

Curiosity drove me to find out how golang would implement Perm functions.

Open the source code of golang and find this function in the rand.go file:

The implementation is very simple, but I was a little confused at first glance, because I didn't use shuffle, but solved the problem in a traversal. What's going on?

After careful analysis, it is found that the algorithm is very ingenious, and each traversal exchanges the current number I with a random number m [j] that is already in the array, and finally achieves the function of fairly random the whole array. Although there are only three lines of code, it makes people feel shocked.

Immediately feel that golang is very NB, and it is really very efficient.

The above code has 4 lines of comments, which probably means that 0 cannot be omitted, which seems useless, but in order to take care of the random sequence in the machine, it still has to be added, otherwise it may have a negative effect. This is related to random seeds and subsequent random sequences. In order not to affect the random sequence to ensure fairness, 0 can not be omitted.

After searching for an efficient shuffling algorithm on the Internet, I found that there is also such a function in python, which reads as follows:

For (int I = N-1; I > = 0; I--)

Swap (arr [I], arr [rand (0, I)]) / / rand (0, I) generates random integers between [0, I]

And the origin of this algorithm actually comes from TAOCP! The algorithm is the famous Knuth-Shuffle, that is, Knuth shuffle algorithm.

A seemingly simple question unexpectedly comes up with Knuth, carelessness.

A person who can do a small thing to the extreme can be called an artist. Knuth lives up to the name.

Finally, I would like to share with you one sentence from Knuth:

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.

After reading the above, have you mastered the method of example analysis of Knuth efficient shuffle algorithm? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.