c++怎么實(shí)現(xiàn)數(shù)據(jù)偽造

這篇文章主要介紹“c++怎么實(shí)現(xiàn)數(shù)據(jù)偽造”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“c++怎么實(shí)現(xiàn)數(shù)據(jù)偽造”文章能幫助大家解決問題。

大致需求是已知一批數(shù)和每個(gè)數(shù)出現(xiàn)的次數(shù)，然后寫個(gè)接口，每次調(diào)用都能返回已知數(shù)據(jù)中的某個(gè)數(shù)，且返回的概率和原始數(shù)據(jù)中每個(gè)數(shù)出現(xiàn)的概率一致，題目描述起來有些繞口，我們來舉個(gè)實(shí)際的例子。

以上面的輸入為例，要求實(shí)現(xiàn)的接口必須以11.96%的概率返回5、18.10%的概率返回91……16.55%的概率返回98，當(dāng)然我的要求不僅僅是這幾個(gè)數(shù)，而是可能有10^5個(gè)數(shù)。 先別急著往下看，給你幾分鐘先思考下。

各種語言其實(shí)都內(nèi)置了random函數(shù)，可以隨機(jī)返回int或者long型的隨機(jī)數(shù)，這里我們先不考慮溢出的問題。為了方便講解，假設(shè)我們已有n個(gè)數(shù)存在在num[n]中，其出現(xiàn)的頻次存放在fre[n]中。 借助已有的random()，我們很簡單就可以生成0-n之間的一個(gè)隨機(jī)數(shù)i，但是如果直接返回num[i]的話，每個(gè)數(shù)返回的概率是一致的，明顯不滿足我們的需求。

其實(shí)解決方案也很簡單，我們按照每個(gè)數(shù)出現(xiàn)的頻次大小，將其映射成不同的區(qū)間大小，出現(xiàn)的概率越大，區(qū)間越大。想象下，這些數(shù)據(jù)按不同的區(qū)間大小把一個(gè)飛鏢盤分成不同的部分，我們生成數(shù)的時(shí)候就是拿個(gè)飛鏢隨機(jī)扎，扎到哪個(gè)算哪個(gè)。
 

當(dāng)然我們可以直接用一位直線區(qū)間描述上面的二維飛鏢盤模型。只需要隨機(jī)生成0-100%之間的數(shù)即可，假設(shè)某次隨機(jī)生成的數(shù)是0.65(65%)，我們算一下 正好對應(yīng)在數(shù)字58對應(yīng)的區(qū)間上，所以這次直接返回58就是了，我們可以開始寫代碼了。

    int[] num; // 數(shù)字
    int[] fre; // 出現(xiàn)的頻次
    double[] pro;  // 出現(xiàn)的概率
    int n;  // 數(shù)據(jù)量
    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; // 計(jì)算出每個(gè)數(shù)出現(xiàn)的概率 
        }
    }
    
    int getRandom() {
        double rp = random.getNextDouble();
        double sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum >= r && sum + pro[i] > rp) {  //找到命中的區(qū)間
                return num[i]; 
            }
            sum += pro[i];
        }
        return num[n-1];
    }

似乎一切都很完美，但每次getRandom()的時(shí)間復(fù)雜度是O(n)，大量的使用性能也抗不太住。有沒有更好的實(shí)現(xiàn)方式？既然寫到這里了，必然是有的。

上面代碼循環(huán)中有個(gè)sum += pro[i]; 每次計(jì)算都要累加，我們是不是可以提前在init()中累加好？然后你會發(fā)現(xiàn)因?yàn)槊看卫奂拥臄?shù)都只正數(shù)，所以pro是個(gè)遞增序列，對于有序序列的查找 二分必然是首選。這時(shí)候我們可以用二分重寫上面代碼。

    int[] num; // 數(shù)字
    int[] fre; // 出現(xiàn)的頻次
    double[] pro;  // 出現(xiàn)的概率
    int n;  // 數(shù)據(jù)量
    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; // 計(jì)算出每個(gè)數(shù)出現(xiàn)的概率
            if (i != 0) {
                pro[i] += pro[i-1];
            }
        }
    }

    int getRandom() {
        double rp = random.getNextDouble();
        int l = 0;
        int r = n-1;
        while (l != r) {   // 二分查找確定區(qū)間位置  
            int mid = (l + r) >> 1;
            if (pro[mid] < rp) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return num[n-1];
    }

關(guān)于“c++怎么實(shí)現(xiàn)數(shù)據(jù)偽造”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。