javascript: speedy Array.contains(otherArray) ?

Question

I have an array of arrays. The inner array is 16 slots, each with a number, 0..15. A simple permutation.

I want to check if any of the arrays contained in the outer array, have the same values as a test array (a permutation of 16 values).

I can do this easily by something like so:

var containsArray = function (outer, inner) {
    var len = inner.length;
    for (var i=0; i<outer.length;  i++) {
        var n = outer[i];
        var equal = true;
        for (var x=0; x<len; x++) {
            if (n[x] != inner[x]) {
                equal = false;
                break;
            }
        }
        if (equal) return true;
    }
    return false;
}

But is there a faster way?

Can I assign each permutation an integral value - actually a 64-bit integer?

Each value in a slot is 0..15, meaning it can be represented in 4 bits. There are 16 slots, which implies 64 total bits of information.

In C# it would be easy to compute and store a hash of the inner array (or permutation) using this approach, using the Int64 type. Does Javascript have 64-bit integer math that will make this fast?

Answer 1

That's just about as fast as it gets, comparing arrays in javascript (as in other languages) is quite painful. I assume you can't get any speed benefits from comparing the lengths before doing the inner loop, as your arrays are of fixed size?

Only "optimizations" I can think of is simplifying the syntax, but it won't give you any speed benefits. You are already doing all you can by returning as early as possible.

Your suggestion of using 64-bit integers sounds interesting, but as javascript doesn't have a Int64 type (to my knowledge), that would require something more complicated and might actually be slower in actual use than your current method.

Answer 2

how about comparing the string values of myInnerArray.join('##') == myCompareArray.join('##'); (of course the latter join should be done once and stored in a variable, not for every iteration like that).

I don't know what the actual performance differences would be, but the code would be more terse. If you're doing the comparisons a lot of times, you could have these values saved away someplace, and the comparisons would probably be quicker at least the second time round.

The obvious problem here is that the comparison is prone to false positives, consider

var array1 = ["a", "b"];
var array2 = ["a##b"];

But if you can rely on your data well enough you might be able to disregard from that? Otherwise, if you always compare the join result and the lengths, this would not be an issue.

Answer 3

Are you really looking for a particular array instance within the outer array? That is, if inner is a match, would it share the same reference as the matched nested array? If so, you can skip the inner comparison loop, and simply do this:

var containsArray = function (outer, inner) {
    var len = inner.length;
    for (var i=0; i<outer.length;  i++) {
        if (outer[i] === inner) return true;
    }
    return false;
}

If you can't do this, you can still make some headway by not referencing the .length field on every loop iteration -- it's an expensive reference, because the length is recalculated each time it's referenced.

var containsArray = function (outer, inner) {
    var innerLen = inner.length, outerLen = outer.length;
    for (var i=0; i<outerLen;  i++) {
        var n = outer[i];
        var equal = true;

        for (var x=0; x<innerLen; x++) {
            if (n[x] != inner[x]) {
                equal = false;
            }
        }
        if (equal) return true;
    }
    return false;
}

Also, I've seen claims that loops of this form are faster, though I haven't seen cases where it makes a measurable difference:

var i = 0;
while (i++ < outerLen) {
   //...
}

EDIT: No, don't remove the equal variable; that was a bad idea on my part.

Answer 4

the only idea that comes to me is to push the loop into the implementation and trade some memory for (speculated, you'd have to test the assumption) speed gain, which also relies on non-portable Array.prototype.{toSource,map}:

var to_str = function (a) {
    a.sort();
    return a.toSource();
}
var containsString = function (outer, inner) {
    var len = outer.length;
    for (var i=0; i<len;  ++i) {
        if (outer[i] == inner)
            return true;
    }
    return false;
}

var found = containsString(
    outer.map(to_str)
  , to_str(inner)
);

Answer 5

While numbers in Javascript occupy 64 bits, it does support 32 bit integer math.

function Bitmap () {
  this.size = 0;
  this.arr = [];
}

Bitmap.prototype = {
    constructor: Bitmap

  , toString: function () {
      return "[object Bitmap]";
    }

  , clear: function (/*pos1, ...*/) {
      for (var i = 0; i < arguments.length; ++i) {
        var pos = arguments [i];
        this.size = Math.max (this.size, pos + 1);
        var idx = Math.floor (pos / 32);
        this.arr [idx] = this.arr [idx] & ~(1 << pos % 32);
      }
      return this;
    }

  , set: function (/*pos1, ...*/) {
      for (var i = 0; i < arguments.length; ++i) {
        var pos = arguments [i];
        this.size = Math.max (this.size, pos + 1);
        var idx = Math.floor (pos / 32);
        this.arr [idx] = this.arr [idx] | 1 << pos % 32;
      }
      return this;
    }

  , get: function (pos) {
      this.size = Math.max (this.size, pos + 1);
      var idx = Math.floor (pos / 32);
      return (this.arr [idx] & 1 << pos % 32) > 0;
    }

  , getAll: function () {
      var rs = [];
      for (var pos = 0; pos < this.size; ++pos) {
        rs [i] = this.get (i);
      }
      return rs;
    }

  , getPositions: function (/*pos1, ...*/) {
      var rs = [];
      for (var i = 0; i < arguments.length; ++i) {
        rs [i] = this.get (arguments [i]);
      }
      return rs;
    }

  , toggle: function (/*pos1, ...*/) {
      for (var i = 0; i < arguments.length; ++i) {
        var pos = arguments [i];
        if (this.get (pos)) {
          this.clear (pos);
        }
        else {
          this.set (pos);
        }
      }
    }
};

Answer 6

var containsArray = function (outer, inner) {
    var innerLen  = inner.length, 
        innerLast = inner.length-1, 
        outerLen  = outer.length;

    outerLoop: for (var i=0; i<outerLen;  i++) {
        var n = outer[i];

        for (var x = 0; x < innerLen; x++) {
            if (n[x] != inner[x]) {
                continue outerLoop;
            }
            if (x == innerLast) return true;
        }
    }
    return false;
}