c++怎么實現數據偽造

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

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

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

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

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

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

    int[] num; // 數字
    int[] fre; // 出現的頻次
    double[] pro;  // 出現的概率
    int n;  // 數據量
    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) {  //找到命中的區間
                return num[i]; 
            }
            sum += pro[i];
        }
        return num[n-1];
    }

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

上面代碼循環中有個sum += pro[i]; 每次計算都要累加，我們是不是可以提前在init()中累加好？然后你會發現因為每次累加的數都只正數，所以pro是個遞增序列，對于有序序列的查找 二分必然是首選。這時候我們可以用二分重寫上面代碼。

    int[] num; // 數字
    int[] fre; // 出現的頻次
    double[] pro;  // 出現的概率
    int n;  // 數據量
    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];
    }

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