current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

How can I optimize checking a value in recursion before operating on it? I'm using Array.indexOf (this is Javascript)

var nums = [], lengths = [];
function findNumLength(n) {
    //preliminary check to see if 
    //we've done this number before
    var indexOf = nums.indexOf(n);
    if(indexOf !== -1) {
        return lengths[indexOf];
    }
    function even (n2) { return n2%2===0; }
    if(n===1) {
        return 1;
    }
    if(even(n)) {
        l = findNumLength(n/2) + 1;
        if(indexOf===-1) { 
            lengths.splice(0,0 ,l);
            nums.push(n);
        }
        return l;
    }
    else {
        l = findNumLength(3*n + 1) + 1;
        if(indexOf===-1){
            lengths.splice(0,0,l);
            nums.push(n);
        }
        return l;
    }
}

(note: I've answered my own question with one solution I've found; it is by no means the only solution (though it may be the best. I don't know). Please, still answer.)

share|improve this question
    
Can you include more complete code? What you have so far isn't making sense to me. You check to see if the number is in the array and if it's not, you return 1. If it is in the array, you add it again. Are you sure that's the logic you meant? –  jfriend00 Mar 18 '12 at 3:55
    
@jfriend00 the code was just a mockup; the idea is that I'm passing a number to a function and, as long as I haven't performed on that number yet, I keep going. Once I hit a number I have done before, I stop. You can see an example here on lines 5-8 –  Thomas Shields Mar 18 '12 at 4:01
    
@jfriend00 oh, my bad. Just realized I had === -1 instead of !== –  Thomas Shields Mar 18 '12 at 4:02
    
On Code Review we expect real code, not mockups. I'd suggest posting that entire piece of code you link as a request for review. That would be more appropriate for this site. –  Winston Ewert Mar 18 '12 at 4:39
    
@WinstonEwert i've edited in the real code; does it look okay or should I add some clarification to the question as well? –  Thomas Shields Mar 18 '12 at 4:41

3 Answers 3

up vote 1 down vote accepted 
var nums = [], lengths = [];
function findNumLength(n) {

This function name would do better to actually mention collatz.

    //preliminary check to see if 
    //we've done this number before
    var indexOf = nums.indexOf(n);
    if(indexOf !== -1) {
        return lengths[indexOf];
    }

indexOf is going to search through the entire list to find the correct number. That's going to be slow. Instead, I'd suggest that you use an array large enough each number n could be an index into it. Leave the default undefined for any entries you haven't calculated yet.

    function even (n2) { return n2%2===0; }

Functions are going to be somewhat expensive, and you only use this one once. It might be better just to stick this in the if.

    if(n===1) {
        return 1;
    }
    if(even(n)) {

I'd make this else if, just to be more explicit

        l = findNumLength(n/2) + 1;
        if(indexOf===-1) {

If this wasn't true, we'd have returned above. So why are you testing it here?

            lengths.splice(0,0 ,l);
            nums.push(n);

I'm not really following what you are doing here. Shouldn't you be pushing on both arrays?

        }
        return l;
    }
    else {
        l = findNumLength(3*n + 1) + 1;
        if(indexOf===-1){
            lengths.splice(0,0,l);
            nums.push(n);
        }
        return l;
    }

There's a lot of common logic between both sides of the if. Most of it should be move after if and run in either case.

}
share|improve this answer
    
Thanks, great answer! I've already incorporated some of the ideas in my final version, but this is great. The reason I did lengths.splice(0,0,1); was that the recursion meant that lengths got added in backwards, so they didn't match up to their numbers in the nums array. –  Thomas Shields Mar 18 '12 at 13:01
    
@ThomasShields, ok by why doesn't the same logic apply to nums? –  Winston Ewert Mar 18 '12 at 15:34
    
you know what, you're right. What happened was that originally I was pushing to nums, then recursing, then adding to lengths - hence the splice, since the recursion happened first. Eventually I rewrote it to push to both arrays. Apparently I posted a sort of hybrid between the two versions. Either way, you're right: thanks for catching that. –  Thomas Shields Mar 18 '12 at 16:52
up vote 1 down vote

The faster way to know if a number is already in a data structure is to use an object, not an array. So, if you don't have to have the numbers in an array, then this would be a lot faster, particular when the number of items gets big because the object look up is massively faster than the linear search of .indexOf():

var numbers = {};
function recurse(newNumber) {
    if(newNumber in numbers) {
        return newNumber;
    }
    //do stuff to number
    numbers[newNumber] = true;
    return recurse(modified_number);
}

You can then iterate through the items in numbers like this:

for (var num in numbers) {
    if (numbers.hasOwnProperty(num) {
        // process num here
    }
}

FYI, if speed is really your goal here, recursion is not the fastest way to do this (because functions calls are kind of slow in javascript), particularly if you don't have much or any local state in the function so you could just use a while loop of sorts.

share|improve this answer
    
thanks! this is really interesting; do you have a link to anything on object lookup vs. linear array search? (I suppose I could always find something via Google, but I prefer something someone else already read/found helpful) –  Thomas Shields Mar 18 '12 at 4:25
1  
@ThomasShields - see this jsperf: jsperf.com/object-index-vs-array-search that I just found with Google. The object is always faster, even if the matched array element is in the first slot of the array and this is with only 10 items in the array/object - it goes even more in favor of the object the more items there are. If you understand how an object property lookup works (via a hashtable), you would see why it's so much faster than a linear search of the array. The differences are most pronounced when the object is not in the array at all or is near the end of the array. –  jfriend00 Mar 18 '12 at 4:29
    
awesome; thanks. I particularly like this because it retains the logic of "have we done x yet?" much better than my answer did. –  Thomas Shields Mar 18 '12 at 4:34
    
@ThomasShields - FYI, that jsperf shows the object access to be almost 10x faster for every case except the one where the object you're looking for happens to be in the first array element and then it's only a little faster. But, since that would rarely happen in the real world, the object is a lot faster on average. –  jfriend00 Mar 18 '12 at 4:34
    
yeah, especially since speed is only going to matter when the array gets > 10K els in size, and the event of the object being first only happens out of ~10K times. –  Thomas Shields Mar 18 '12 at 4:38
up vote 0 down vote

Array.indexOf loops through the entire array, which hurts speed, especially when the array gets big and the recursion enters several levels. One way to optimize would be to do:

//set up the array as normal
var numbers = []; 
function recurse(number) {
    //if numbers doesn't have an element
    //mapped to number yet, create it:
    if(!numbers[number]) numbers[number] = false; 
    if(numbers[number])
    {
         return number;
    }
    //do stuff to number
    numbers[number] = true;
    recurse[modified_number];
}

Also, instead of setting numbers[number] to false, you could set it to some useful value to help keep track.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.