Reputation: 10551

Why is this javascript so slow? Is it simply down to lag?

Be so kind to look at http://www.jhurleydesign.com/uniquerandom/

Basically, what I've created is a script that randomly turns those white stars green. It works by generating unique random numbers, and using each number as an eq selector to apply the 'green' class.

Before I ran this code, I assumed the rate at which the stars were turned green would increase, because the number of potential eq selectors gets steadily smaller and smaller. (Remember how I said they're unique numbers that are generated?"

However, the opposite happens. As you'll see when you visit that link, stars change green relatively quickly, but towards the end, the script starts to get so, so, so slow. On my machine, the final star takes around 3 minutes to change to green!

Is it this down to lag? If so, how I can get around it? This script does something very, very simple, so I doubt lag is a game-stopper here. I think I've just done a stupid error!

You can copy and paste the source code (it's all on one page) from http://www.jhurleydesign.com/uniquerandom/ but it's also posted below:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>Greenstars</title>
<script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<script type="text/javascript">
$(document).ready(function () {
    var limit = $('span'),
        unr = [];
    setInterval(function () {
        {
            var random_number = Math.round(Math.random() * limit.length);
            if (unr.indexOf(random_number) == -1) {
                unr.push(random_number);
                limit.eq(random_number).addClass('green');
                if (limit.length < unr.length) {
                    alert('Finished!');
                };
            }
        }
    }, 0);
});
</script>
<style>
.green {
    color: #0F0;
}
#container {
    background-color: #000;
    color: #FFF;
}
</style>
<div id="container">
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
<span>*</span>
</div>

Thanks for your time!

Upvotes: 2

Answers (8)

codefactor

Reputation: 1656

The problem is that your function is doing this

do this over and over again forever {
  Generate a random number
  if (random number has not been checked before) {
    mark random number as checked
    make the span at this random index green
    if (all spans are green) {
      show a message "finished"
    }
  }
}

So as time goes on it is less and less likely that your randomly generated number will not be found before - so it can run the function many many times before it finds one.

When it gets down to 2 or 3 left over numbers, the loop will probably run a very very long time before it happens to randomly fall upon one of the 2 left over numbers.

You need to reformulate your algorithm - it is probably best to just randomly shuffle an array of each number you want and then make the stars green in that order but separated by a fixed amount of time.

Another possible algorithm is to remove the stars that you make green from an array and then generate the random number between 1 - new length (which is previous length minus 1)

Upvotes: 5

Liangliang Zheng

Reputation: 1785

Personally I like this approach - http://jsfiddle.net/Y6xZG/2/

$(document).ready(function () {
    var limit = $('span').toArray();
    limit.sort( function() { return Math.random() > 0.5 } );

    var intv = setInterval(function () {
        if(!limit.length) {
            alert('Finished!');
            clearInterval(intv);
            return;
        }
        var $star = $(limit.pop());
        $star.addClass('green');
    }, 0);
});

Upvotes: 0

fedmich

Reputation: 5371

Try this approach.

All your spans initially have class "loading". <span class="loading">*</span>
Remove the classes upon each run
Pick random item and removeClass loading, and do whatever you want
Count how many is still remainng with "loading" class
Dont forget to clearInterval to prevent it from running again.

Demo http://jsfiddle.net/fedmich/QTy7G/

var objCont;
$(document).ready(function () {
    objCont = $('#container');

    function asteriks(){
        var items = objCont.find('.loading');
        if(items.length==0){
            //FINISHED
            alert('Finished!');

            clearInterval(interval_id);
            return false;
        }

       //pick random element, remove loading then addClass green
        var random = Math.round(Math.random()* items.length );
        items.eq(random).removeClass('loading').addClass('green');

    }
    var interval_id = setInterval( asteriks, 500);  
});

Some more things to note:

I'm storing $('#container') into variable objCont so it on queried by JQ once
ClearInterval so the function finishes
I'm using 500ms, so half a second. do you really need it to be 0 (from your example?)
There is another possible improvement here, which only uses removeClass('loading') and no AddClass('green') technique, but that is another story/case

Upvotes: 1

j08691

Reputation: 208002

You've seen from several of these posts the reason why your method seems to slow down. Here's a fairly linear example: jsFiddle example.

It works by building an array of the span elements, and then randomly selecting one and removing it from the array, essentially shrinking the pool (array length) to pick from the each time until the length is zero.

var limit = $('span'),
    ary = [];
for (var i = 0; i <= limit.length; i++) ary.push(i);
function foo() {
    var random_number = Math.round(Math.random() * ary.length);
    limit.eq(ary[random_number]).addClass('green');
    ary.splice(random_number, 1);
    if (ary.length < 1) {
        alert('Finished!');
    } else {
        setTimeout(foo,5);   
    }
}
foo();

Upvotes: 0

Scott Mermelstein

Reputation: 15397

Not to dismiss all the good suggestions for how you can improve your efficiency, but why it takes so long at the end is simply a matter of probability.

I don't know how many * you have on the screen. Let's say 1000, because it's a nice easy number. On your first case, you have a 1000 in 1000 chance of turning one green. On your 500th success, you only have a 500 in 1000 each time you come up with a number. On your 900th success, you only have a 100 in 1000 chance of finding a new match. On your last one, you keep choosing random numbers until your 1 in 1000 chance happens.

Essentially, storing the value in the array at all is currently useless, because it doesn't impact the next number you select - it only impacts whether you turn the value green. In probability terms, this is "draw with replacement", not "draw without replacement", as you intended. You can completely remove your array, and you'll just be turning something that's green back to green, and still waiting a long time, because the odds of finding a non-green are diminishing. jfriend00's answer is one that will let you do "draw without replacement" - once you do that, yes, it will speed up toward the end.

Upvotes: 3

jfriend00

Reputation: 708046

It will get slower and slower because you're generating a random number for the entire set of objects, but testing for ones that are already done. So, once there are only a few left, it takes a lot of random numbers to find one that hasn't already been turned. Plus searching a longer and longer array of items that has been turned gets slower and slower too, though the random number misses are probably the bigger deal.

It would be much better to create an array of all the stars initially and when you turn one, remove it from that array. Then create your random number on the shortened array. You won't have to check if it's already turned and your stars will turn at a uniform pace from first to last.

Here's one way the code could be written like that:

// get array of DOM elements to operate on
var items = $('span').get();

var interval = setInterval(function() {
    var random_number = Math.floor(Math.random() * items.length);
    // add the class to the selected random item
    $(items[random_number]).addClass('green');

    // remove element we just processed from the array
    // so our random generator no longer includes it
    items.splice(random_number, 1);

    // if there are no more to do, stop the interval
    if (items.length === 0) {
        clearInterval(interval);
    }
}, 50);

FYI, I've also changed the timer interval to 50ms since you probably want a measured animation effect rather than just flip them all as fast as can be done. You can adjust that time value to whatever you want. If you wanted to just flip them all as fast as possible, you would just do:

$('span').addClass('green');

But, I assume you actually want some sort of animation which should have a more specific measured time set on the interval.

Upvotes: 9

maerics

Reputation: 156632

The problem is that you are storing your unique random numbers in an array and doing a linear search in that array.

Moreover you are executing your function constantly setInterval(..., 0).

Upvotes: 1

Pointy

Reputation: 413976

You've set up your interval timer with 0 milliseconds between invocations. That means that the browser will essentially be spending all its time running your function. What in the world were you expecting?

Upvotes: 0

Why is this javascript so slow? Is it simply down to lag?

Answers (8)

Related Questions