1
\$\begingroup\$
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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Regarding Boyer-Moore: https://gist.github.com/etrepum/6235082

Click here for a cleaner typescript implementation

function asUint8Array(input) {
  if (input instanceof Uint8Array) {
    return input;
  } else if (typeof(input) === 'string') {
    // This naive transform only supports ASCII patterns. UTF-8 support
    // not necessary for the intended use case here.
    var arr = new Uint8Array(input.length);
    for (var i = 0; i < input.length; i++) {
      var c = input.charCodeAt(i);
      if (c > 127) {
        throw new TypeError("Only ASCII patterns are supported");
      }
      arr[i] = c;
    }
    return arr;
  } else {
    // Assume that it's already something that can be coerced.
    return new Uint8Array(input);
  }
}
function boyerMoore(patternBuffer) {
  // Implementation of Boyer-Moore substring search ported from page 772 of
  // Algorithms Fourth Edition (Sedgewick, Wayne)
  // http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html
  /*
  USAGE:
     // needle should be ASCII string, ArrayBuffer, or Uint8Array
     // haystack should be an ArrayBuffer or Uint8Array
     var search = boyerMoore(needle);
     var skip = search.byteLength;
     var indexes = [];
     for (var i = search(haystack); i !== -1; i = search(haystack, i + skip)) {
       indexes.push(i);
     }
  */
  var pattern = asUint8Array(patternBuffer);
  var M = pattern.length;
  if (M === 0) {
    throw new TypeError("patternBuffer must be at least 1 byte long");
  }
  // radix
  var R = 256;
  var rightmost_positions = new Int32Array(R);
  // position of the rightmost occurrence of the byte c in the pattern
  for (var c = 0; c < R; c++) {
    // -1 for bytes not in pattern
    rightmost_positions[c] = -1;
  }
  for (var j = 0; j < M; j++) {
    // rightmost position for bytes in pattern
    rightmost_positions[pattern[j]] = j;
  }
  function boyerMooreSearch(txtBuffer, start, end) {
    // Return offset of first match, -1 if no match.
    var txt = asUint8Array(txtBuffer);
    if (start === undefined) start = 0;
    if (end === undefined) end = txt.length;
    var pat = pattern;
    var right = rightmost_positions;
    var lastIndex = end - pat.length;
    var lastPatIndex = pat.length - 1;
    var skip;
    for (var i = start; i <= lastIndex; i += skip) {
      skip = 0;
      for (var j = lastPatIndex; j >= 0; j--) {
        var c = txt[i + j];
        if (pat[j] !== c) {
          skip = Math.max(1, j - right[c]);
          break;
        }
      }
      if (skip === 0) {
        return i;
      }
    }
    return -1;
  };
  boyerMooreSearch.byteLength = pattern.byteLength;
  return boyerMooreSearch;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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