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

This article mainly introduces the relevant knowledge of "how C++ realizes data forgery". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "how to achieve data forgery on C++" can help you solve the problem.

The general requirement is to know the number of a batch and the number of occurrences of each number, and then write an API. Each call can return a certain number of known data, and the probability of return is the same as that of each number in the original data. The topic is somewhat roundabout. Let's give a practical example.

Taking the above input as an example, the required interface must return 5 with a probability of 11.96% and 91 with a probability of 18.10%. 16.55% probability returns 98, of course, my requirement is not only these numbers, but maybe 10 ^ 5. Don't look down so fast. I'll give you a few minutes to think about it.

In fact, various languages have built-in random functions, which can randomly return random numbers of int or long. Let's not consider the problem of overflow here. For ease of explanation, suppose we already have n numbers in num [n], and the frequency of their occurrence is stored in fre [n]. With the help of the existing random (), we can easily generate a random number I between 0murn, but if we return Num [I] directly, the probability of each number returning is the same, which obviously does not meet our needs.

In fact, the solution is also very simple. We map each number into different interval sizes according to the frequency of each number. The greater the probability of occurrence, the greater the interval. Imagine that these data divide a darts tray into different parts according to different interval sizes. when we generate numbers, we take a dart and stab it randomly.

Of course, we can directly use a straight line interval to describe the above two-dimensional darts model. You only need to randomly generate a number between 0 and 100%. Suppose that the randomly generated number is 0.65 (65%), and we calculate that it corresponds to the interval corresponding to the number 58, so just return 58 this time, and we can start writing code.

Int [] num; / / Digital int [] fre; / / Frequency of occurrence double [] pro; / / probability of occurrence int n; / / data volume void init () {int sum = 0; for (int I = 0; I)

< n; i++) { sum += fre[i]; } for (int i = 0; i < n; i++) { pro[i] = fre[i]/sum; // 计算出每个数出现的概率 } } int getRandom() { double rp = random.getNextDouble(); double sum = 0; for (int i = 0; i < n; i++) { if (sum >

= r & & sum + pro [I] > rp) {/ / find the hit interval return num [I];} sum + = pro [I];} return Num [n-1];}

Everything seems to be perfect, but each time the time complexity of getRandom () is O (n), and the performance of a large number of uses is not very good. Is there a better way to achieve it? Now that it is written here, there must be some.

In the above code loop, there is a sum + = pro [I]; each calculation has to be accumulated, can we add it in init () in advance? Then you will find that because each cumulative number is only positive, pro is an increasing sequence, so finding dichotomy for ordered sequences must be the first choice. At this point, we can rewrite the above code with two points.

Int [] num; / / Digital int [] fre; / / Frequency of occurrence double [] pro; / / probability of occurrence int n; / / data volume void init () {int sum = 0; for (int I = 0; I)

< n; i++) { sum += fre[i]; } for (int i = 0; i < n; i++) { pro[i] = fre[i]/sum; // 计算出每个数出现的概率 if (i != 0) { pro[i] += pro[i-1]; } } } int getRandom() { double rp = random.getNextDouble(); int l = 0; int r = n-1; while (l != r) { // 二分查找确定区间位置 int mid = (l + r) >

> 1; if (pro [mid] < rp) {l = mid + 1;} else {r = mid;}} return Num [n-1];} that's all for "how C++ implements data forgery". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.