生成随机唯一数据耗时太长，占用 100% CPU [英] Generating random unique data takes too long and eats 100% CPU

问题描述

警告:CPU 使用率达到 100%，小心.

WARNING: CPU Usage goes to 100%, be careful.

jsFiddle链接

编写此脚本是为了设计动态蛇梯板.每次刷新页面时都会创建一个新板.大多数情况下，所有背景图像都不会出现，CPU 使用率高达 100%.但有时它们都会出现并且CPU使用率是正常的.

This script has been written to design a dynamic snake and ladder board. Everytime the page is refreshed a new board is created. Most of the time all of the background images do not appear, and the CPU usage goes up to 100%. But on occasion all of them appear and the CPU usage is normal.

Opera 显示一些背景图片，Firefox 滞后并询问我是否要停止脚本.

Opera shows some of the background images, Firefox lags and asks me if I wish to stop the script.

我认为问题出在这些代码行上:

I believe that the problem is with these lines of code:

        for(var key in origin)      // Need to implement check to ensure that two keys do not have the same VALUES!
        {
            if(origin[key] == random_1 || origin[key] == random_2 || key == random_2)   // End points cannot be the same AND starting and end points cannot be the same.
            {
                valFlag = 1;
            }
            console.log(key);
        }

推荐答案

你的算法效率很低.当数组几乎填满时，您实际上会进行数百万次无用的迭代，直到您走运并且 RNG 不小心选择了丢失的数字.将其重写为:

Your algorithm is very ineffective. When array is almost filled up, you literally do millions of useless iterations until you're in luck and RNG accidentally picks missing number. Rewrite it to:

1. 生成一个包含所有可能数字的数组 - 从 1 到 99.
2. 当你需要一个随机数时，在这个数组的当前边界、拼接元素和这个随机位置中生成一个随机索引，将它从数组中移除并使用它的值作为你想要的随机数.
3. 如果生成的数字不符合您的某些条件(minDiff?)，请将它们返回到数组.请注意，如果保留在数组中的所有内容都无法满足您的条件，您仍然可以永远停止循环.

您以这种方式从数组中提取的每个值都保证是唯一的，因为您最初用唯一的数字填充它并在使用时删除它们.

Every value you pull from array in this way is guaranteed to be unique, since you originally filled it with unique numbers and remove them on use.

我已经剥离了绘图并将生成的数字放入了您可以在控制台中检查的数组中.放回您的绘图，它应该可以工作 - 现在立即生成数字:

I've stripped drawing and placed generated numbers into array that you can check in console. Put your drawing back and it should work - numbers are generated instantly now:

var snakes = ['./Images/Snakes/snake1.png','./Images/Snakes/snake2.jpg','./Images/Snakes/snake3.gif','./Images/Snakes/snake4.gif','./Images/Snakes/snake5.gif','./Images/Snakes/snake6.jpg'];
var ladders = ['./Images/Ladders/ladder1.jpg','./Images/Ladders/ladder2.jpg','./Images/Ladders/ladder3.png','./Images/Ladders/ladder4.jpg','./Images/Ladders/ladder5.png'];


function drawTable()
{
    // Now generating snakes.
    generateRand(snakes,0);
    generateRand(ladders,1);

}

var uniqNumbers = []
for(var idx = 1; idx < 100; idx++){ uniqNumbers.push(idx) }

var results = []

function generateRand(arr,flag)
{
    var valFlag = 0;
    var minDiff = 8;        // Minimum difference between start of snake/ladder to its end.
    var temp;

    for(var i = 0; i< arr.length; ++i) {

        var valid = false

        // This is the single place it still can hang, through with current size of arrays it is highly unlikely
        do {
            var random_1 = uniqNumbers.splice(Math.random() * uniqNumbers.length, 1)[0]
            var random_2 = uniqNumbers.splice(Math.random() * uniqNumbers.length, 1)[0]
            if (Math.abs(random_1 - random_2) < minDiff) {
                // return numbers
                uniqNumbers.push(random_1)
                uniqNumbers.push(random_2)
            } else {
                valid = true
            }
        } while (!valid);


        if(flag == 0)     // Snake
        {
            if(random_1 < random_2)        // Swapping them if the first number is smaller than the second number.
            {
                var temp = random_1; random_1 = random_2; random_2 = temp
            }
        }
        else         // Ladders
        {
            if(random_1>random_2)        // Swapping them if the first number is greater than the second number.
            {
                var temp = random_1; random_1 = random_2; random_2 = temp
            }
        }
        // Just for debug - look results up on console
        results.push([random_1, random_2])
    }
}

drawTable()

这篇关于生成随机唯一数据耗时太长，占用 100% CPU的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！