CODEWITHSUNDEEP
javascriptjqueryarrayssortingloops
Willem
Willem

Reputation: 723

alternatives for excessive for() looping in javascript

Situation

I'm currently writing a javascript widget that displays a random quote into a html element. the quotes are stored in a javascript array as well as how many times they've been displayed into the html element. A quote to be displayed cannot be the same quote as was previously displayed. Furthermore the chance for a quote to be selected is based on it's previous occurences in the html element. ( less occurrences should result in a higher chance compared to the other quotes to be selected for display.

Current solution

I've currently made it work ( with my severely lacking javascript knowledge ) by using a lot of looping through various arrays. while this currently works ( !! ) I find this solution rather expensive for what I want to achieve.

What I'm looking for

The Code

var quoteElement = $("div#Quotes > q"),
    quotes = [[" AAAAAAAAAAAA ", 1],
              [" BBBBBBBBBBBB ", 1],
              [" CCCCCCCCCCCC ", 1],
              [" DDDDDDDDDDDD ", 1]],
    fadeTimer = 600,
    displayNewQuote = function () {

                        var currentQuote = quoteElement.text();
                        var eligibleQuotes = new Array();
                        var exclusionFound = false;
                        for (var i = 0; i < quotes.length; i++) {
                            var iteratedQuote = quotes[i];
                            if (exclusionFound === false) {
                                if (currentQuote == iteratedQuote[0].toString())
                                    exclusionFound = true;
                                else
                                    eligibleQuotes.push(iteratedQuote);
                            } else
                                eligibleQuotes.push(iteratedQuote);
                        }
                        eligibleQuotes.sort( function (current, next) {
                            return current[1] - next[1];
                        } );

                        var calculatePoint = eligibleQuotes[0][1];
                        var occurenceRelation = new Array();
                        var relationSum = 0;
                        for (var i = 0; i < eligibleQuotes.length; i++) {
                            if (i == 0)
                                occurenceRelation[i] = 1 / ((calculatePoint / calculatePoint) + (calculatePoint / eligibleQuotes[i+1][1]));
                            else
                                occurenceRelation[i] = occurenceRelation[0] * (calculatePoint / eligibleQuotes[i][1]);
                            relationSum = relationSum + (occurenceRelation[i] * 100);
                        }

                        var generatedNumber = Math.floor(relationSum * Math.random());
                        var newQuote;
                        for (var i = 0; i < occurenceRelation.length; i++) {
                            if (occurenceRelation[i] <= generatedNumber) {
                                newQuote = eligibleQuotes[i][0].toString();
                                i = occurenceRelation.length;
                            }
                        }

                        for (var i = 0; i < quotes.length; i++) {
                            var iteratedQuote = quotes[i][0].toString();
                            if (iteratedQuote == newQuote) {
                                quotes[i][1]++;
                                i = quotes.length;
                            }
                        }

                        quoteElement.stop(true, true)
                                    .fadeOut(fadeTimer);
                        setTimeout( function () {
                            quoteElement.html(newQuote)
                                        .fadeIn(fadeTimer);
                        }, fadeTimer);

                    } 

if (quotes.length > 1) 
    setInterval(displayNewQuote, 10000);

Alternatives considered

jsFiddle reference

http://jsfiddle.net/P5rk3/

Update

Rewrote my function with the techniques mentioned, while I fear that these techniques still loop through the entire array to find it's requirements, at least my code looks cleaner : )

References used after reading the answers here:

Upvotes: 1

Views: 301

Answers (5)

unclenorton
unclenorton

Reputation: 1625

If, for some reason, you are not comfortable with splice or filter methods, there is a nice (outdated, but still working) method by John Resig: http://ejohn.org/blog/javascript-array-remove/

Upvotes: 0

Halcyon
Halcyon

Reputation: 57703

You can write functions that explicitly define what you're trying to do with the loop.

Your first loop is a filter. Your second loop is a map + some side effect. I don't know about the other loops, they're weird :P

A filter is something like:

function filter(array, condition) {
    var i = 0, new_array = [];
    for (; i < array.length; i += 1) {
        if (condition(array[i], i)) {
            new_array.push(array[i]);
        }
    }
    return new_array;
}

var numbers = [1,2,3,4,5,6,7,8,9];
var even_numbers = filter(numbers, function (number, index) {
    return number % 2 === 0;
});
alert(even_numbers); // [2,4,6,8]

You can't avoid the loop, but you can add more semantics to the code by making a function that explains what you're doing.

Upvotes: 0

Alnitak
Alnitak

Reputation: 339917

Alternative methods of removing an array element from an array

With ES5's Array.filter() method:

Array.prototype.without = function(v) {
    return this.filter(function(x) {
        return v !== x;
    });
};

given an array a, a.without(v) will return a copy of a without the element v in it.

less occurrences should result in a higher chance compared to the other quotes to be selected for display

You shouldn't mess with chance - as my mathematician other-half says, "chance doesn't have a memory".

What you're suggesting is akin to the idea that numbers in the lottery that haven't come up yet must be "overdue" and therefore more likely to appear. It simply isn't true.

Upvotes: 1

SJuan76
SJuan76

Reputation: 24895

The answer that you want:

Create an integer array that stores the number of uses of every quote. Also, a global variable Tot with the total number of quotes already used (i.e., the sum of that integer array). Find also Mean, as Tot / number of quotes.

Chose a random number between 0 and Tot - 1.

For each quote, add Mean * 2 - the number of uses(*1). When you get that that value has exceeded the random number generated, select that quote.

In case that quote is the one currently displayed, either select the next or the previous quote or just repeat the process.

The real answer:

Use a random quote, at the very maximum repeat if the quote is duplicated. The data usages are going to be lost when the user reloads/leaves the page. And, no matter how cleverly have you chosen them, most users do not care.

(*1) Check for limits, i.e. that the first or last quota will be eligible with this formula.

Upvotes: 2

davin
davin

Reputation: 45545

I suggest array functions that are mostly supported (and easily added if not):

[].splice(index, howManyToDelete); // you can alternatively add extra parameters to slot into the place of deletion
[].indexOf(elementToSearchFor);
[].filter(function(){});

Other useful functions include forEach and map.

I agree that combining all the work into one giant loop is ugly (and not always possible), and you gain little by doing it, so readability is definitely the winner. Although you shouldn't need too many loops with these array functions.

Upvotes: 3

Related Questions