Fastest way to loop through this array in Javascript on Chrome 36

Question

I have a very big array which looks similar to this

var counts = ["gfdg 34243","jhfj 543554",....] //55268 elements long

this is my current loop

var replace = "";
var scored = 0;
var qgram = "";
var score1 = 0;
var len = counts.length;

function score(pplaintext1) {
    qgram = pplaintext1;
    for (var x = 0; x < qgram.length; x++) {
        for (var a = 0, len = counts.length; a < len; a++) {
            if (qgram.substring(x, x + 4) === counts[a].substring(0, 4)) {
                replace = parseInt(counts[a].replace(/[^1-9]/g, ""));
                scored += Math.log(replace / len) * Math.LOG10E;
            } else {
                scored += Math.log(1 / len) * Math.LOG10E;
            }
        }
    }
    score1 = scored;
    scored = 0;
} //need to call the function 1000 times roughly

I have to loop through this array several times and my code is running slowly. My question is what the fastest way to loop through this array would be so I can save as much time as possible.

@Qantas94Heavy is telling you that unless this portion of the code is the one that actually slows down the program as a whole, you should not care about it and go for the obvious way. — Stefano Sanfilippo
– Stefano Sanfilippo, Commented Jul 26, 2014 at 10:34
Show use the code inside loop, there is probably a problem with performance. You could try with sorting array to get better results. — Mateusz Nowak
– Mateusz Nowak, Commented Jul 26, 2014 at 10:34
@user3184807: a "bottleneck" means something that slows down a process or activity. — Qantas 94 Heavy
– Qantas 94 Heavy, Commented Jul 26, 2014 at 10:35
so the first element seems like a key, and the number as an associated value. Are the keys unique ? — GameAlchemist
– GameAlchemist, Commented Jul 26, 2014 at 11:16

Alnitak · Accepted Answer · 2015-12-22 15:28:10Z

3

Your counts array appears to be a list of unique strings and values associated with them. Use an object instead, keyed on the unique strings, e.g.:

var counts = { gfdg: 34243, jhfj: 543554, ... };

This will massively improve the performance by removing the need for the O(n) inner loop by replacing it with an O(1) object key lookup.

Also, avoid divisions - log(1 / n) = -log(n) - and move loop invariants outside the loops. Your log(1/len) * Math.LOG10E is actually a constant added in every pass, except that in the first if branch you also need to factor in Math.log(replace), which in log math means adding it.

p.s. avoid using the outer scoped state variables for the score, too! I think the below replicates your scoring algorithm correctly:

var len = Object.keys(counts).length;

function score(text) {
    var result = 0;
    var factor = -Math.log(len) * Math.LOG10E;

    for (var x = 0, n = text.length - 4; x < n; ++x) {
        var qgram = text.substring(x, x + 4);
        var replace = counts[qgram];
        if (replace) {
            result += Math.log(replace) + factor;
        } else {
            result += len * factor;  // once for each ngram
        }
    }
    return result;
}

edited Dec 22, 2015 at 15:28

answered Jul 26, 2014 at 10:51

Alnitak

341k72 gold badges420 silver badges503 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Alnitak Over a year ago

@user3184807 because the object key lookup is O(1) instead of O(n), and because it avoids the need to use substr on the count values.

David Barker Over a year ago

Because you don't need to substring the array value in the if clause everytime. Branch prediction will not be good when trying to analyse this array anyway, having it run computation on the values will slow it down more. The object is the way to go. (What Alnitak said)

Alnitak Over a year ago

@user3184807 I've realised there's a discrepancy in my algorithm compared to yours - in your code for each qgram in the original string you add the found score or your 1/n factor in the inner loop for every word in the counts list. In mine I'm only adding len * 1/n if the qgram isn't found in the counts list at all, so if the qgram is found it's missing factor * (len - 1) / n

user3856543 Over a year ago

anyway... thanks for telling me about the object lookup it helped so much

Collectives™ on Stack Overflow

Fastest way to loop through this array in Javascript on Chrome 36

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related