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.
Uint8Array.prototype.indexOfMulti = function(searchElements, fromIndex) {
    fromIndex = fromIndex || 0;

    var index = Array.prototype.indexOf.call(this, searchElements[0], fromIndex);
    if(searchElements.length === 1 || index === -1) {
        // Not found or no other elements to check
        return index;
    }

    for(var i = index, j = 0; j < searchElements.length && i < this.length; i++, j++) {
        if(this[i] !== searchElements[j]) {
            return this.indexOfMulti(searchElements, index + 1);
        }
    }

    return (i === index + searchElements.length) ? index : -1;
};

It works fine but I wonder if I missed any important case or if anyone sees a way to optimize this.

share|improve this question
add comment

1 Answer 1

First things first. This code is fairly difficult to read. indexOfMulti could mean

  • You're searching for any one of multiple values.
  • You're searching for all occurrences of a value (less likely -- might be indicesOf or findAll).
  • You're searching for the first occurrence of a sequence.

I'd name this something like find, findSequence, findSubstring. I'd also rename searchElements to something like needle, targetSequence.


You have two different efficiency issues here.

First, if this code is running in an implementation without tail-call optimization (I can't tell if any do, much less whether it's common), your memory usage may blow up whenever the first part of needle is common in your haystack but the full needle isn't found, because you'll blow up the stack. Better to implement this non-recursively.

Second, you've chosen the naive string search algorithm (see http://en.wikipedia.org/wiki/String_searching_algorithm). It will work fine when needle and haystack are small, or when prefixes of needle are rare in haystack, but it will be quite slow on the following example:

haystack = "aaaaaaaaaaaaaaaaaaaaab";
needle = "aaaab";
haystack.findSequence(needle);

You'd be better off selecting one of the other algorithms in that wikipedia article; a good choice is Boyer-Moore.

share|improve this answer
add comment

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.